1 /**
2 This module defines generic collections.
3 4 Collection_primitives:
5 6 Collections do not form a class hierarchy, instead they implement a
7 common set of primitives (see table below). These primitives each guarantee
8 a specific worst case complexity and thus allow generic code to be written
9 independently of the _collection implementation.
10 11 The following table describes the common set of primitives that collections
12 implement. A _collection need not implement all primitives, but if a primitive
13 is implemented, it must support the syntax described in the `syntax` column with
14 the semantics described in the `description` column, and it must not have a
15 worst-case complexity worse than denoted in big-O notation in the
16 $(BIGOH ·) column. Below, `C` means a _collection type, `c` is a value of
17 _collection type, $(D n$(SUBSCRIPT x)) represents the effective length of value
18 `x`, which could be a single element (in which case $(D n$(SUBSCRIPT x)) is `1`),
19 a _collection, or a range.
20 21 $(BOOKTABLE collection primitives,
22 $(TR
23 $(TH Syntax)
24 $(TH $(BIGOH ·))
25 $(TH Description)
26 )
27 $(TR
28 $(TDNW $(D C(x)))
29 $(TDNW $(D n$(SUBSCRIPT x)))
30 $(TD Creates a _collection of type $(D C) from either another _collection,
31 a range or an element. The created _collection must not be a null
32 reference even if x is empty.)
33 )
34 $(TR
35 $(TDNW $(D c.dup))
36 $(TDNW $(D n$(SUBSCRIPT c)))
37 $(TD Returns a duplicate of the _collection.)
38 )
39 $(TR
40 $(TDNW $(D c ~ x))
41 $(TDNW $(D n$(SUBSCRIPT c) + n$(SUBSCRIPT x)))
42 $(TD Returns the concatenation of `c` and `x`. `x` may be a single element
43 or an input range.)
44 )
45 $(TR
46 $(TDNW $(D x ~ c))
47 $(TDNW $(D n$(SUBSCRIPT c) + n$(SUBSCRIPT x)))
48 $(TD Returns the concatenation of `x` and `c`. `x` may be a single element
49 or an input range type.)
50 )
51 $(LEADINGROWN 3, Iteration
52 )
53 $(TR
54 $(TD $(D c.popFront()))
55 $(TD `1`)
56 $(TD Advances to the next element in the _collection.)
57 )
58 $(TR
59 $(TD $(D c.save))
60 $(TD `1`)
61 $(TD Return a shallow copy of the _collection.)
62 )
63 $(TR
64 $(TD $(D c[]))
65 $(TDNW $(D n$(SUBSCRIPT c)))
66 $(TD Returns a range
67 iterating over the entire _collection, in a _collection-defined order.)
68 )
69 $(TR
70 $(TDNW $(D c[a .. b]))
71 $(TDNW $(D n$(SUBSCRIPT c)))
72 $(TD Fetches a portion of the _collection from key `a` to key `b`.)
73 )
74 $(LEADINGROWN 3, Capacity
75 )
76 $(TR
77 $(TD $(D c.empty))
78 $(TD `1`)
79 $(TD Returns `true` if the _collection has no elements, `false` otherwise.)
80 )
81 $(TR
82 $(TD $(D c.length))
83 $(TDNW `1`)
84 $(TD Returns the number of elements in the _collection.)
85 )
86 $(TR
87 $(TDNW $(D c.length = n))
88 $(TDNW $(D max(n$(SUBSCRIPT c), n)))
89 $(TD Forces the number of elements in the _collection to `n`. If the
90 _collection ends up growing, the added elements are initialized
91 in a _collection-dependent manner (usually with $(D T.init)).)
92 )
93 $(TR
94 $(TD $(D c.capacity))
95 $(TDNW $(D n$(SUBSCRIPT c)))
96 $(TD Returns the maximum number of elements that can be stored in the
97 _collection without triggering a reallocation.)
98 )
99 $(TR
100 $(TD $(D c.reserve(x)))
101 $(TD $(D n$(SUBSCRIPT c)))
102 $(TD Forces `capacity` to at least `x` without reducing it.)
103 )
104 $(LEADINGROWN 3, Access
105 )
106 $(TR
107 $(TDNW $(D c.front))
108 $(TDNW `1`)
109 $(TD Returns the first element of the _collection, in a _collection-defined
110 order.)
111 )
112 $(TR
113 $(TDNW $(D c.front = v))
114 $(TDNW `1`)
115 $(TD Assigns `v` to the first element of the _collection.)
116 )
117 $(TR
118 $(TDNW $(D c.back))
119 $(TDNW $(D log n$(SUBSCRIPT c)))
120 $(TD Returns the last element of the _collection, in a _collection-defined order.)
121 )
122 $(TR
123 $(TDNW $(D c.back = v))
124 $(TDNW $(D n$(SUBSCRIPT c)))
125 $(TD Assigns `v` to the last element of the _collection.)
126 )
127 $(TR
128 $(TDNW $(D c[x]))
129 $(TDNW $(D n$(SUBSCRIPT c)))
130 $(TD Provides indexed access into the _collection. The index type is
131 _collection-defined. A _collection may define several index types (and
132 consequently overloaded indexing).)
133 )
134 $(TR
135 $(TDNW $(D c[x] = v))
136 $(TDNW $(D n$(SUBSCRIPT c)))
137 $(TD Sets element at specified index into the _collection.)
138 )
139 $(TR
140 $(TDNW $(D c[x] $(I op)= v))
141 $(TDNW $(D n$(SUBSCRIPT c)))
142 $(TD Performs read-modify-write operation at specified index into the
143 _collection.)
144 )
145 $(LEADINGROWN 3, Operations
146 )
147 $(TR
148 $(TDNW $(D e in c))
149 $(TDNW $(D n$(SUBSCRIPT c)))
150 $(TD Returns nonzero if e is found in $(D c).)
151 )
152 $(LEADINGROWN 3, Modifiers
153 )
154 $(TR
155 $(TDNW $(D c ~= x))
156 $(TDNW $(D n$(SUBSCRIPT c) + n$(SUBSCRIPT x)))
157 $(TD Appends `x` to `c`. `x` may be a single element or an input range type.)
158 )
159 $(TR
160 $(TDNW $(D c.clear()))
161 $(TDNW $(D n$(SUBSCRIPT c)))
162 $(TD Removes all elements in `c`.)
163 )
164 $(TR
165 $(TDNW $(D c.insert(pos, x)))
166 $(TDNW $(D n$(SUBSCRIPT x)))
167 $(TD Inserts `x` at `pos` in `c`. `x` may be a single element or an input
168 range type.)
169 )
170 $(TR
171 $(TDNW $(D c.insertBack(x)))
172 $(TDNW $(D n$(SUBSCRIPT c) + n$(SUBSCRIPT x)))
173 $(TD Inserts `x` at the back of `c`. `x` may be a single element or an input
174 range type.)
175 )
176 $(TR
177 $(TDNW $(D c.remove()))
178 $(TDNW $(D 1))
179 $(TD Removes the front element of `c`.)
180 )
181 182 $(TR
183 $(TDNW $(D ))
184 $(TDNW $(D ))
185 $(TD )
186 )
187 )
188 189 Source: $(PHOBOSSRC std/experimental/_collection/package.d)
190 191 License: Distributed under the Boost Software License, Version 1.0.
192 (See accompanying file LICENSE_1_0.txt or copy at $(HTTP
193 boost.org/LICENSE_1_0.txt)).
194 195 Authors: Eduard Staniloiu, $(HTTP erdani.com, Andrei Alexandrescu)
196 */197 198 modulestdx.collections;