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
|
bf(C++) offers several predefined datatypes, all part of the
link(Standard Template Library)(STL),
which can be used to implement solutions to frequently occurring problems. The
datatypes discussed in this chapter are all
hi(container) em(containers): you can put stuff inside them, and you can
retrieve the stored information from them.
The interesting part is that the kind of data that can be stored inside these
containers has been left unspecified at the time the containers were
constructed. That's why they are spoken of as em(abstract) containers.
Abstract containers rely heavily on em(templates), covered in chapter
ref(TEMPLATES) and beyond. To use abstract containers, only a minimal grasp of
the template concept is required. In bf(C++) a template is in fact a recipe
for constructing a function or a complete class. The recipe tries to abstract
the functionality of the class or function as much as possible from the data
on which the class or function operates. As the data types on which the
templates operate were not known when the template was implemented, the
datatypes are either inferred from the context in which a function template is
used, or they are mentioned explicitly when a class template is used (the term
that's used here is em(instantiated)). In situations where the types are
explicitly mentioned, the em(angle bracket notation) is used to indicate
which data types are required. For example, below (in section ref(PAIR)) we'll
encounter the hi(pair container)tt(pair) container, which requires the
explicit mentioning of two data types. Here is a tt(pair) object
containing both an tt(int) and a tt(string):
verb( pair<int, string> myPair;)
The object tt(myPair) is defined as an object holding both an tt(int) and
a tt(string).
The angle bracket notation is used intensively in the upcoming
discussion of abstract containers. Actually, understanding this part of
templates is the only real requirement for using abstract containers. Now
that we've introduced this notation, we can postpone the more thorough
discussion of templates to chapter ref(TEMPLATES), and concentrate on
their use in this chapter.
Most abstract containers are em(sequential) containers: they contain
data that can be stored and retrieved in some sequential
way. Examples are the tt(array), implementing a fixed-sized array; a
tt(vector), implementing an extendable array; the
tt(list), implementing a data structure that allows for the easy insertion or
deletion of data; the tt(queue), also called a emi(FIFO)
(i(first in, first out)) structure, in which the first element that is
entered is the first element to be retrieved again; and the tt(stack),
which is a
emi(first in, last out) (i(FILO) or i(LIFO)) structure.
In addition to sequential containers several special containers are
available. The tt(pair) is a basic container in which a pair of values (of
types that are left open for further specification) can be stored, like two
strings, two ints, a string and a double, etc.. Pairs are often used to return
data elements that naturally come in pairs. For example, the tt(map) is an
abstract container storing keys and their associated values. Elements
of these maps are returned as tt(pairs).
A variant of the tt(pair) is the tt(complex) container, implementing
operations that are defined on complex numbers.
A tt(tuple) (cf. section ref(TUPLES)) generalizes the tt(pair) container to a
data structure accommodating any number of different data types.
All abstract containers described in this chapter as well as the tt(string)
and stream datatypes (cf. chapters ref(String) and ref(IOStreams)) are part of
the Standard Template Library.
All but the unordered containers support
hi(basic operators of containers)
hi(container: basic operators)
hi(operators of containers)
the following basic set of operators:
itemization(
it() The i(overloaded assignment) operator, so we can assign two
containers of the same types to each other. If the container's data type
supports move assignment, then assignment of an anonymous temporary container
to a destination container will use move assignment when assigning new values
to the destination container's element. Overloaded assignment is em(also)
supported by the unordered containers;
it() hi(container: equality tests) Tests for equality: ti(==) and ti(!=)
The i(equality operator) applied to two containers returns tt(true) if the two
containers have the same number of elements, which are pairwise equal
according to the equality operator of the contained data type. The
i(inequality operator) does the opposite;
it() hi(container: ordering) Ordering operators: ti(<), ti(<=), ti(>) and
ti(>=). The tt(<) operator returns tt(true) if each element in the
i(left-hand) side container is less than each corresponding element in the
i(right-hand) side container. Additional elements in either the left-hand side
container or the right-hand side container are ignored.
verb(container left;
container right;
left = {0, 2, 4};
right = {1, 3}; // left < right
right = {1, 3, 6, 1, 2}; // left < right)
)
Note that hi(container: data type requirements) before a
user-defined type (usually a tt(class)-type) can be stored in a container, the
user-defined type should at least support:
itemization(
it() A default value (e.g., a i(default constructor))
it() The i(equality operator) (ti(==))
it() The i(less-than operator) (ti(<))
)
Sequential containers can also be initialized using em(initializer lists).
Most containers (exceptions are the link(stack)(STACK) (section
ref(STACK)), link(priority_queue)(PRIQUEUE) (section
ref(PRIQUEUE)), and link(queue)(QUEUE) (section
ref(QUEUE)) containers) support members to determine their maximum sizes
(through their member function i(max_size)).
Virtually all containers support copy construction. If the container
supports copy construction and the container's data type supports move
construction, then move construction is automatically used for the container's
data elements when a container is initialized with an anonymous temporary
container.
Closely linked to the standard template library are the
emi(generic algorithms). These algorithms may be used to perform
frequently occurring tasks or more complex tasks than is possible with the
containers themselves, like counting, filling, merging, filtering etc.. An
i(overview of generic algorithms) and their applications is given in chapter
ref(GENERIC). Generic algorithms usually rely on the availability of
hi(iterator)link(em(iterators))(ITERATORS), representing begin and
end-points for processing data stored inside containers. The abstract
containers usually support constructors and members expecting iterators, and
they often have members returning iterators (comparable to the
tt(string::begin) and tt(string::end) members). In this chapter the
iterator concept is not further investigated. Refer to chapter ref(STL) for
this.
The url hi(http://www.sgi.com/.../stl)
tlurl(https://www.sgi.com/tech/stl/) is worth visiting as it offers more
extensive coverage of abstract containers and the standard template library
than can be provided by the annotations().
Containers often collect data during their lifetimes. When a container
goes out of scope, its destructor tries to destroy its data elements. This
only succeeds if the data elements themselves are stored inside the
container. If the hi(container: storing pointers) data elements of containers
are pointers to dynamically allocated memory then the memory pointed to by
these pointers is not destroyed, resulting in a i(memory leak). A consequence
of this scheme is that the data stored in a container should often be
considered the `property' of the container: the container should be able to
destroy its data elements when the container's destructor is called. So,
normally containers should not contain pointers to data. Also, a container
should not be required hi(containter: storing const data)
hi(const data and containers) to contain tt(const) data, as tt(const) data
prevent the use of many of the container's members, like the assignment
operator.
|
