1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
|
The ti(list) container hi(list container) implements a list data structure.
Before using a tt(list) container the header file tthi(list) must be included.
The organization of a tt(list) is shown in figure ref(listFig).
figure(containers/list)(A list data-structure)(listFig)
Figure ref(listFig) shows that a list consists of separate
list-elements, connected by pointers. The list can be
hi(list: traversal) traversed in two directions: starting at em(Front) the
list may be traversed from left to right, until the 0-pointer is reached at
the end of the rightmost list-element. The list can also be traversed from
right to left: starting at em(Back), the list is traversed from right to left,
until eventually the 0-pointer emanating from the leftmost list-element is
reached.
As a subtlety note that the representation given in figure ref(listFig) is not
necessarily used in actual implementations of the list. For example, consider
the following little program:
verb( int main()
{
list<int> l;
cout << "size: " << l.size() << ", first element: " <<
l.front() << '\n';
})
When this program is run it might actually produce the output:
verb( size: 0, first element: 0)
Its front element can even be assigned a value. In this case the
implementor has chosen to provide the list with a hidden element. The list
actually is a em(circular)
hi(list: circular) list, where the hidden element serves as terminating
element, replacing the 0-pointers in figure ref(listFig). As noted, this is a
subtlety, which doesn't affect the conceptual notion of a list as a data
structure ending in 0-pointers. Note also that it is well known that various
implementations of list-structures are possible (cf.
i(Aho, A.V.), i(Hopcroft J.E.) and i(Ullman, J.D.), (1983)
emi(Data Structures and Algorithms) (Addison-Wesley)).
Both lists and vectors are often appropriate data structures in situations
where an hi(storing data) unknown number of data elements must be
stored. However, there are some hi(rule of thumb) rules of thumb to follow
when selecting the appropriate data structure.
itemization(
it() When most accesses are i(random), a tt(vector) is the preferred data
structure. Example: in a program counting character frequencies in
a textfile, a tt(vector<int> frequencies(256)) is the
datastructure of choice, as the values of the received characters
can be used as indices into the tt(frequencies) vector.
it() The previous example illustrates a second rule of thumb, also
favoring the tt(vector): if the number of elements is known in
advance (and does not notably change during the lifetime of the
program), the vector is also preferred over the list.
it() In cases where i(insertions) or i(deletions) prevail and the data
structure is large the list is generally preferred.
)
At present lists aren't as useful anymore as they used to be (when
computers were much slower and more memory-constrained). Except maybe for
some rare cases, a tt(vector) should be the preferred container; even when
implementing algorithms traditionally using lists.
Other considerations related to the choice between lists and vectors
should also be given some thought. Although it is true that the vector is able
to grow dynamically, the i(dynamic growth) requires data-copying.
Clearly, copying a million large data structures takes a considerable amount
of time, even on fast computers. On the other hand, inserting a large number
of elements in a list doesn't require us to
i(copy non-involved data). Inserting a new element in a list merely
requires us to juggle some pointers. In figure ref(listAdd) this is shown: a
new element is inserted between the second and third element, creating a new
list of four elements.
figure(containers/insertlist)(Adding a new element to a list)(listAdd)
Removing an element from a list is also fairly easy. Starting again
from the situation shown in figure ref(listFig), figure ref(listDel) shows
what happens if element two is removed from our list. Again: only pointers
need to be juggled. In this case it's even simpler than adding an element:
only two pointers need to be rerouted.
figure(containers/dellist)(Removing an element from a list)(listDel)
To summarize the comparison between lists and vectors: it's probably best
to conclude that there is no clear-cut answer to the question what data
structure to prefer. There are rules of thumb, which may be adhered to. But if
worse comes to worst, a i(profiler) may be required to find out what's best.
The tt(list) container offers the following constructors, operators, and
member functions:
itemization(
it() hi(list constructors) Constructors:
itemization(
it() The copy and move constructors are available;
it() A tt(list) may be constructed empty:
verb(list<string> object;)
As with the tt(vector), it is an error to refer to an element of an
empty list.
it() A list may be initialized to a certain number of elements. By
default, if the initialization value is not explicitly mentioned,
the default value or default constructor for the actual data type
is used. For example:
verb(list<string> object(5, "Hello"s); // initialize to 5 Hello's
list<string> container(10); // and to 10 empty strings)
it() A list may be initialized using a two iterators. To initialize a
list with elements 5 until 10 (including the last one) of a
tt(vector<string>) the following construction may be used:
verb(extern vector<string> container;
list<string> object(&container[5], &container[11]);)
)
it() The tt(list) does not offer specialized operators, apart from the
standard operators for containers.
it() The following hi(member function)member functions are available:
itemization(
itht(assign)(void assign(...)):
quote(assigns new content to the list:)
itemization(
itt(assign(iterator begin, iterator end)) assigns the values at
the iterator range rangett(begin, end) to the list;
itt(assign(size_type n, value_type const &val)) assigns tt(n)
copies of tt(val) to the list;
)
ithtq(back)(Type &back())(returns a reference to the last element in
the list. It is the i(responsibility of the programmer) to use
this member only if the list is not empty.)
ithtq(begin)(list::iterator begin())(returns an iterator pointing to
the first element in the list, returning tt(end) if the list is
empty.)
ithtq(clear)(void clear())(erases all elements from the list.)
ithtq(emplace_back)(value_type &emplace_back(Args &&...args))
(a tt(value_type) object is constructed from the member's
arguments, and the newly created element is inserted beyond the
last element of the list, returning a reference to the newly added
element.)
ithtq(emplace_front)(value_type &emplace_front(Args &&...args))
(a tt(value_type) object is constructed from the member's
arguments, and the newly created element is inserted before the
first element of the list, returning a reference to the newly added
element.)
ithtq(empty)(bool empty())(returns tt(true) if the list contains no
elements.)
ithtq(end)(list::iterator end())(returns an iterator pointing beyond
the last element in the list.)
ithtq(erase)(list::iterator erase())(erases a specific range of
elements in the list:)
itemization(
itt(erase(pos)) erases the element pointed to by tt(pos). The
iterator tt(++pos) is returned.
itt(erase(first, beyond)) erases elements indicated by the iterator
range rangett(first, beyond). tt(Beyond) is returned.
)
ithtq(front)(Type &front())(returns a reference to the first element
in the list. It is the responsibility of the programmer to use
this member only if the list is not empty.)
ithtq(get_allocator)(allocator_type get_allocator() const)(returns a
copy of the allocator object used by the tt(list) object.)
ithtq(insert)(... insert())(inserts elements into the list. The return
value depends on the version of tt(insert) that is called:)
itemization(
itt(list::iterator insert(pos)) inserts a default value of type
tt(Type) at tt(pos), tt(pos) is returned.
itt(list::iterator insert(pos, value)) inserts tt(value) at
tt(pos), tt(pos) is returned.
itt(void insert(pos, first, beyond)) inserts the elements in the
iterator range rangett(first, beyond).
itt(void insert(pos, n, value)) inserts tt(n) elements having value
tt(value) at position tt(pos).
)
ithtq(max_size)(size_t max_size())(returns the maximum number of
elements this tt(list) may contain.)
ithtq(merge)(void merge(list<Type> other))(this member function
assumes that the current and other lists are sorted (see below,
the member tt(sort)). Based on that assumption, it inserts the
elements of tt(other) into the current list in such a way that the
modified list remains sorted. If both list are not sorted, the
resulting list will be ordered `as much as possible', given the
initial ordering of the elements in the two
lists. tt(list<Type>::merge) uses tt(Type::operator<) to sort the
data in the list, which operator must therefore be available. The
next example illustrates the use of the tt(merge) member: the list
`tt(object)' is not sorted, so the resulting list is ordered 'as
much as possible'.
verbinclude(-a examples/listmerge.cc)
A subtlety is that tt(merge) doesn't alter the list if the list
itself is used as argument: tt(object.merge(object)) won't change
the list `tt(object)'.)
ithtq(pop_back)(void pop_back())(removes the last element from the
list. The program aborts when called on an i(empty list).)
ithtq(pop_front)(void pop_front())(removes the first element from the
list. The program aborts when called on an i(empty list).)
ithtq(push_back)(void push_back(value))(adds tt(value) to the end of
the list.)
ithtq(push_front)(void push_front(value))(adds tt(value) before the
first element of the list.)
ithtq(rbegin)(list::reverse_iterator rbegin())( returns a
reverse_iterator pointing to the last element in the list.)
ithtq(remove)(void remove(value))(removes all occurrences of tt(value)
from the list. In the following example, the two strings
`tt(Hello)' are removed from the list tt(object):
verbinclude(-a examples/listremove.cc))
ithtq(remove_if)(void remove_if(Predicate pred))(removes all
occurrences from the list for which the predicate function or
function object tt(pred) returns tt(true). For each of the objects
stored in the list the predicate is called as tt(pred(*iter)),
where tt(iter) represents the iterator used internally by
tt(remove_if). If a function tt(pred) is used, its prototype
should be tt(bool pred(value_type const &object))).
ithtq(rend)(list::reverse_iterator rend())(this member returns a
reverse_iterator pointing before the first element in the list.)
ithtq(resize)(void resize())(alters the number of elements that are
currently stored in the list:) itemization( itt(resize(n, value))
may be used to resize the list to a size of tt(n). tt(Value) is
optional. If the list is expanded and tt(value) is not provided,
the extra elements are initialized to the i(default value) of the
used data type, otherwise tt(value) is used to initialize extra
elements.)
ithtq(reverse)(void reverse())(reverses the order of the elements in
the list. The element tt(back) becomes tt(front) and em(vice
versa).)
ithtq(size)(size_t size())(returns the number of elements in the
list.)
ithtq(sort)(void sort())(sorts the list. An example of its use is
given at the description of the tt(unique) member function
below. tt(list<Type>::sort) uses tt(Type::operator<) to sort the
data in the list, which must therefore be available.)
ithtq(splice)(void splice(pos, object))(transfers the content of
tt(object) to the current list, starting the insertion at the
iterator position tt(pos) of the object using the tt(splice)
member. Following tt(splice), tt(object) is empty. For example:
verbinclude(-a examples/listsplice.cc)
Alternatively, tt(argument) may be followed by an iterator of
tt(argument), indicating the first element of tt(argument) that
should be spliced, or by two iterators tt(begin) and tt(end)
defining the iterator-range rangett(begin, end) on tt(argument)
that should be spliced into tt(object).)
ithtq(swap)(void swap())(swaps two lists using identical data types.)
ithtq(unique)(void unique())(operating on a sorted list, this member
function removes all consecutively identical elements from the
list. tt(list<Type>::unique) uses tt(Type::operator==) to identify
identical data elements, which operator must therefore be
available. Here's an example removing all multiply occurring
words from the list: verbinclude(-a examples/listunique.cc))
)
)
|
