Container classes, or containers for short, manage a collection
of elements. To meet different needs, the STL provides different kinds of
containers, as shown in figure below
Figure: STL Container Types
There are two general kinds of containers:
-
Sequence containers are ordered collections in which every element has a certain position. This position depends on the time and place of the insertion, but it is independent of the value of the element. For example, if you put six elements into a collection by appending each element at the end of the actual collection, these elements are in the exact order in which you put them. The STL contains three predefined sequence container classes: vector, deque, and list.
-
Associative containers are sorted collections in which the actual position of an element depends on its value due to a certain sorting criterion. If you put six elements into a collection, their order depends only on their value. The order of insertion doesn't matter. The STL contains four predefined associative container classes: set, multiset, map, and multimap.
An associative container can be considered a special kind of sequence
container because sorted collections are ordered according to a sorting
criterion. You might expect this especially if you have used other libraries of
collection classes like those in Smalltalk or the NIHCL, in which sorted collections are derived
from ordered collections. However, note that the STL collection types are
completely distinct from each other. They have different implementations that
are not derived from each other.
The automatic sorting of elements in associative containers does not
mean that those containers are especially designed for sorting elements. You can
also sort the elements of a sequence container. The key advantage of automatic
sorting is better performance when you search elements. In particular, you can
always use a binary search, which results in logarithmic complexity rather than
linear complexity. For example, this means that for a search in a collection of
1,000 elements you need, on average, only 10 instead of 500 comparisons. Thus, automatic sorting is only
a (useful) "side effect" of the implementation of an associative container,
designed to enable better performance.
The following subsections discuss the different container classes in detail.
Among other aspects, they describe how containers are typically implemented.
Strictly speaking, the particular implementation of any container is not defined
inside the C++ standard library. However, the behavior and complexity specified
by the standard do not leave much room for variation. So, in practice, the
implementations differ only in minor details. Coming post with covers the exact behavior of the
container classes. It describes their common and individual abilities, and
member functions in detail.
Sequence Containers
The following sequence containers are predefined in the STL:-
Vectors
-
Deques
- Lists
Vectors
A vector manages its elements in a dynamic array. It enables random access,
which means you can access each element directly with the corresponding index.
Appending and removing elements at the end of the array is very fast. However, inserting an
element in the middle or at the beginning of the array takes time because all
the following elements have to be moved to make room for it while maintaining
the order. Strictly speaking,
appending elements is amortized very fast. An individual append may be
slow, when a vector has to reallocate new memory and to copy existing elements
into the new memory. However, because such reallocations are rather rare, the
operation is very fast in the long term.
The following example defines a vector for integer values, inserts six
elements, and prints the elements of the vector:
With
the header file for vectors is included.
The declaration
creates a vector for elements of type int. The vector is not initialized by any value, so the default constructor creates it as an empty collection.
The push_back() function appends an element to the container:
This member function is provided for all sequence containers. The size() member function returns the number of
elements of a container:
This function is provided for any container class.
By using the subscript operator [], you can access a single element of a vector:
Here the elements are written to the standard output, so the output of the whole program is as follows:
Deques
The term deque (it rhymes with "check" ( It is only a mere accident that "deque" also sounds like "hack" :-)) ) is an abbreviation for "double-ended
queue." It is a dynamic array that is implemented so that it can grow in both
directions. Thus, inserting elements at the end and at the beginning is
fast. However, inserting elements in the middle takes time because elements must
be moved.
The following example declares a deque for floating-point values, inserts
elements from 1.1 to 6.6 at the front of the container, and prints all elements
of the deque:
In this example, with
the header file for deques is included.
The declaration
creates an empty collection of floating-point values.
The push_front() function is used to insert elements:
push_front() inserts an element at the front of the collection. Note that this kind of insertion results in a reverse order of the elements because each element gets inserted in front of the previous inserted elements. Thus, the output of the program is as follows:
You could also insert elements in a deque by using the push_back() member function. The push_front() function, however, is not provided for vectors because it would have a bad runtime for vectors (if you insert an element at the front of a vector, all elements have to be moved). Usually, the STL containers provide only those special member functions that in general have "good" timing ("good" timing normally means constant or logarithmic complexity). This prevents a programmer from calling a function that might cause bad performance.
Lists
A list is implemented as a doubly linked list of
elements. This means each element in a list has its own segment of memory and
refers to its predecessor and its successor. Lists do not provide random access.
For example, to access the tenth element, you must navigate the first nine
elements by following the chain of their links. However, a step to the next or
previous element is possible in constant time. Thus, the general access to an
arbitrary element takes linear time (the average distance is proportional to the
number of elements). This is a lot worse than the amortized constant time
provided by vectors and deques.
The advantage of a list is that the insertion or removal of an element is
fast at any position. Only the links must be changed. This implies that moving
an element in the middle of a list is very fast compared with moving an element
in a vector or a deque.
The following example creates an empty list of characters, inserts all
characters from 'a' to 'z', and
prints all elements by using a loop that actually prints and removes the first
element of the collection:
As usual, the header file for lists, <list>, is used to define a collection of type list for character values:
The empty() member function returns whether the container has no elements. The loop continues as long as it returns true (that is, the container contains elements):
Inside the loop, the front() member function returns the actual first element:
The pop_front() function removes the first element:
Note that pop_front() does not return the element it
removed. Thus, you can't combine the previous two statements into one.
The output of the program depends on the actual character set. For the ASCII
character set, it is as follows:
Of course it is very strange to "print" the elements of a list by a loop that
outputs and removes the actual first element. Usually, you would iterate over
all elements. However, direct element access by using operator [] is not
provided for lists. This is because lists don't provide random access, and thus
using operator [] would cause bad performance. There is another way to loop over
the elements and print them by using iterators. After their introduction I will
give an example.
Strings
You can also use strings as STL containers. By strings I mean objects
of the C++ string classes (basic_string<>, string,
and wstring). Strings are similar to vectors
except that their elements are characters.
Ordinary Arrays
Another kind of container is a type of the core C and C++ language rather
than a class: an ordinary array that has static or dynamic size. However,
ordinary arrays are not STL containers because they don't provide member
functions such as size() and empty(). Nevertheless, the STL's design allows you to call
algorithms for these ordinary arrays. This is especially useful when you process
static arrays of values as an initializer list.
The usage of ordinary arrays is nothing new. What is new is using algorithms
for them.
Note that in C++ it is no longer necessary to program dynamic arrays
directly. Vectors provide all properties of dynamic arrays with a safer and more
convenient interface.
Associative Containers
Associative containers sort their elements automatically according to a
certain ordering criterion. This criterion takes the form of a function that
compares either the value or a special key that is defined for the value. By
default, the containers compare the elements or the keys with operator <. However, you can supply your own comparison function
to define another ordering criterion.
Associative containers are typically implemented as binary trees. Thus, every
element (every node) has one parent and two children. All ancestors to the left
have lesser values; all ancestors to the right have greater values. The
associative containers differ in the kind of elements they support and how they
handle duplicates.
The following associative containers are predefined in the STL. Because you
need iterators to access their elements.
-
SetsA set is a collection in which elements are sorted according to their own values. Each element may occur only once, thus duplicates are not allowed.
-
MultisetsA multiset is the same as a set except that duplicates are allowed. Thus, a multiset may contain multiple elements that have the same value.
-
MapsA map contains elements that are key/value pairs. Each element has a key that is the basis for the sorting criterion and a value. Each key may occur only once, thus duplicate keys are not allowed. A map can also be used as an associative array, which is an array that has an arbitrary index type (see page 91 for details).
-
MultimapsA multimap is the same as a map except that duplicates are allowed. Thus, a multimap may contain multiple elements that have the same key. A multimap can also be used as dictionary. See page 209 for an example.
All of these associative container classes have an optional template argument
for the sorting criterion. The default sorting criterion is the operator <. The sorting criterion is also used as the test for
equality; that is, two elements are equal if neither is less than the other.
You can consider a set as a special kind of map, in which the value is
identical to the key. In fact, all of these associative container types are
usually implemented by using the same basic implementation of a binary tree.
Container Adapters
In addition to the fundamental container classes, the C++ standard library
provides special predefined container adapters that meet special needs. These
are implemented by using the fundamental containers classes. The predefined
container adapters are as follows:
-
StacksThe name says it all. A stack is a container that manages its elements by the LIFO (last-in-first-out) policy.
-
QueuesA queue is a container that manages its elements by the FIFO (first-in-first-out) policy. That is, it is an ordinary buffer.
-
Priority QueuesA priority queue is a container in which the elements may have different priorities. The priority is based on a sorting criterion that the programmer may provide (by default, operator < is used). A priority queue is, in effect, a buffer in which the next element is always the element that has the highest priority inside the queue. If more than one element has the highest priority, the order of these elements is undefined.
Container adapters are historically part of the STL. However, from a programmer's view point, they are just special containers that use the general framework of the containers, iterators, and algorithms provided by the STL.
-----------------------------------------------------------------
See Also:
-----------------------------------------------------------------
See Also:
-----------------------------------------------------------------
- Complete Tutorial of C++ Template's
- Standard Template Library Tutorial
- Inter Process Communication Tutorial
- Advance Programming in C & C++
-----------------------------------------------------------------
No comments:
Post a Comment