Program examples compiled usingVC++7.0/.Net, win32 empty console mode application. g++ examples given at the end of this Module. The source code for this tutorial is available inC++ STL Container source code.
The Standard Template Library (STL) is a generic library that provides solutions to managing collections of data with an efficient algorithm.
The STL provides a collection of classes that meet different kind of tasks, with algorithms that operate on the classes. STL components are templates, as you have learned in Module 24, it can be used for arbitrary data types.
Furthermore, STL also provides a framework for other collection of user defined classes or algorithms. The traditional programming such as dynamic arrays, linked lists, binary trees, search algorithms and other data structures routines can be implemented using STL more efficiently and easily.
To easily understand this topic, you should have good understanding of the traditional arrays data type and operations that can be done on arrays elements such as comparison, sorting, deletion, modification, insertion etc. and as well as templates.
| 27.1 Introduction: STL components
27.1.1 What Is Containers?
27.1.2 What Is Iterators?
27.1.3 What Is Algorithms?
|
There are two types of containers, a sequence and associative containers.
Are ordered collections in which every element has a certain position. This ‘ordered’ term does not mean ascending or descending, but it refers to 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 10 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.
Are sorted collections in which the actual position of an element depends on its value due to a certain sorting criterion. If you put ten 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, multimap (and another non standard is hash_map,hash_multimap, hash_set and hash_multiset). Some of these containers are not required by ANSI C++ (ISO/IEC C++) such as hash family.
An associative container can be considered a special kind of sequence container because sorted collections are ordered according to a sorting criterion. 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.
An associative container is a variable-sized container that supports efficient retrieval of elements (values) based on keys.
It supports insertion and removal of elements, but differs from a sequence in that it does not provide a mechanism for inserting an element at a specific position.
As with all containers, the elements in an associative container are the type of value_type. Additionally, each element in an associative container has a key, of type key_type.
In a Simple Associative Containers, the value_type and key_type are the same that is the elements are their own keys.
In others, the key is some specific part of the value. Since elements are stored according to their keys, it is essential that the key associated with each element is immutable.
In simple associative containers this means that the elements themselves are immutable, while in other types of associative containers a Pair Associative Containers, the elements themselves are mutable but the part of an element that is its key cannot be modified. This means that an associative container's value type is not assignable.
The fact that the value type of an associative container is not assignable has an important consequence: associative containers cannot have mutable iterators. This is simply because a mutable iterator must allow assignment.
That is, if i is a mutable iterator and t is an object of i's value type, then*i = t must be a valid expression.
In simple associative containers, where the elements are the keys, the elements are completely immutable; the nested types iterator andconst_iterator are therefore the same. Other types of associative containers, however, do have mutable elements, and do provide iterators through which elements can be modified.
In pair associative containers, for example, have two different nested types’ iterator and const_iterator.
Even in this case, iterator is not a mutable iterator: as explained above, it does not provide the expression:
*i = t.
It is, however, possible to modify an element through such an iterator: if, for example,
i is of type map<int, double>
Then:
(*i).second = 3
Is a valid expression.
In some associative containers a Unique Associative Containers, it is guaranteed that no two elements have the same key.
In other associative containers a Multiple Associative Containers, multiple elements with the same key are permitted.
There are operations common to all containers. The following Table is a list of these operations. You will find these operations somewhere in the program examples later.
Sample Code | Operation |
con,con1 and con2 are containers. | |
ContainerType con e.g. vector<int> vec0 | Creates an empty container without any element. |
ContainerType con1(con2) e.g. vector<int> vec0(vec1) | Copies a container of the same type. |
ContainerType con(begin,end) e.g. vector<int> vec0(p.begin(),p.end()) | Creates a container and initializes it with copies of all elements of [begin, end). |
con.~ContType() | Deletes all elements and frees the memory. |
con.size() | Returns the actual number of elements. |
con.empty() | Returns whether the container is empty, equivalent to size()==0, but might be faster. |
con.max_size() | Returns the maximum number of elements possible. |
con1 == con2 | Returns whether con1 is equal to con2. |
con1 != con2 | Returns whether con1 is not equal to con2, equivalent to !(con1==con2) |
con1 < con2 | Returns whether con1 is less than con2 |
con1 > con2 | Returns whether con1 is greater than con2, equivalent to con2 < con1. |
con1 <= con2 | Returns whether con1 is less than or equal to con2, equivalent to !(con2<con1). |
con1 >= con2 | Returns whether con1 is greater than or equal to con2, equivalent to !(con1<con2). |
con1 = con2 | Assignment, assigns all elements of con1 to con2. |
con1.swap(con2) | Swaps the data of con1 and con2. |
swap(con1,con2) | Same but a global function. |
con.begin() | Returns an iterator for the first element. |
con.end() | Returns an iterator for the position after the last element. |
con.rbegin() | Returns a reverse iterator for the first element of a reverse iteration. |
con.rend() | Returns a reverse iterator for the position after the last element of a reverse iteration. |
con.insert(position,element) | Inserts a copy of element. |
con.erase(begin,end) | Removes all elements of the range[begin, end), some containers return next element not removed. |
con.clear() | Removes all elements, making the container empty. |
con.get_allocator() | Returns the memory model of the container. |
Table 27.1: Common Operations Examples of Container Classes |
A code snippet example: Initializing with the elements of another container:
// ls is a linked list of int
list<int> ls;
...
// copy all elements of the ls list into a con vector
vector<int> con(ls.begin(), ls.end());
27.5.1 Vectors
|
In all such cases, iterators or references that point at altered portions of the sequence become invalid. If no reallocation happens, only iterators and references before the insertion/deletion point remain valid.
Thevector<bool> class is a full specialization of the template class vector for elements of type bool with an allocator for the underlying type used by the specialization.
Thevector<bool> reference class is a nested class whose objects are able to provide references to elements (single bits) within a vector<bool> object.
The list class container is superior with respect to insertions and deletions at any location within a sequence. The performance of the deque class container is superior with respect to insertions and deletions at the beginning and end of a sequence compared to vector.
The following general example defines a vector for integer values, inserts ten elements, and prints the elements of the vector:
// vector example
#include <iostream>
// vector header file
#include <vector>
using namespace std;
int main()
{
// vector container for integer elements declaration
vector<int> coll;
// append or push elements with values 1 to 10
for(int i=1; i<=10; ++i)
coll.push_back(i);
// print all elements separated by a space
for(i=0; i<coll.size(); ++i)
cout<<coll[i]<<' ';
cout<<endl;
return 0;
}
Let us dig more detail about the vector. A lot of stuff has been provided by the C++ STL, our task is to learn how to use them properly, before you create or refine your own containers. Do not reinvent the wheel.
The following section is a <vector> header member.
Operator | Brief Description |
operator!= | Tests if the vector object on the left side of the operator is not equal to the vector object on the right side. The return value is true if the vectors are not equal; false if the vectors are equal. |
operator< | Tests if the vector object on the left side of the operator is less than the vector object on the right side. The return value is true if the vector on the left side of the operator is less than the vector on the right side of the operator; otherwise false. |
operator<= | Tests if the vector object on the left side of the operator is less than or equal to the vector object on the right side. The return value is true if the vector on the left side of the operator is less than or equal to the vector on the right side of the operator; otherwise false. |
operator== | Tests if the vector object on the left side of the operator is equal to the vector object on the right side. The return value is true if the vector on the left side of the operator is equal to the vector on the right side of the operator; otherwise false. |
operator> | Tests if the vector object on the left side of the operator is greater than the vector object on the right side. The return value is true if the vector on the left side of the operator is greater than the vector on the right side of the operator; otherwise false. |
operator>= | Tests if the vector object on the left side of the operator is greater than or equal to the vector object on the right side. The return value is true if the vector on the left side of the operator is greater than or equal to the vector on the right side of the vector; otherwise false. |
Table 27.2 |
A program example:
// vector, operators
#include <vector>
#include <iostream>
using namespace std;
int main()
{
// vector container for integer elements declaration
vector<int> vec1, vec2, vec3;
cout<<"vec1 data: ";
// append elements with values 1 to 10
for(int i=1; i<=10; ++i)
vec1.push_back(i);
// print all elements separated by a space
for(i=0; i<vec1.size(); ++i)
cout<<vec1[i]<<' ';
cout<<endl;
cout<<"vec2 data: ";
// append elements with values 1 to 10
for(i=11; i<=20; ++i)
vec2.push_back(i);
// print all elements separated by a space
for(i=0; i<vec2.size(); ++i)
cout<<vec2[i]<<' ';
cout<<endl;
cout<<"vec3 data: ";
// append elements with values 1 to 10
for(i=1; i<=10; ++i)
vec3.push_back(i);
// print all elements separated by a space
for(i=0; i<vec3.size(); ++i)
cout<<vec3[i]<<' ';
cout<<"\n\n";
cout<<"Operation: vec1 != vec2"<<endl;
if(vec1 != vec2)
cout<<"vec1 and vec2 is not equal."<<endl;
else
cout<<"vec1 and vec2 is equal."<<endl;
cout<<"\nOperation: vec1 == vec3"<<endl;
if(vec1 == vec3)
cout<<"vec1 and vec3 is equal."<<endl;
else
cout<<"vec1 and vec3 is not equal."<<endl;
cout<<"\nOperation: vec1 < vec2"<<endl;
if(vec1 < vec2)
cout<<"vec1 less than vec2."<<endl;
else
cout<<"vec1 is not less than vec2."<<endl;
cout<<"\nOperation: vec2 > vec1"<<endl;
if(vec2 > vec1)
cout<<"vec2 greater than vec1."<<endl;
else
cout<<"vec2 is not greater than vec1."<<endl;
cout<<"\nOperation: vec2 >= vec1"<<endl;
if(vec2 >= vec1)
cout<<"vec2 greater or equal than vec1."<<endl;
else
cout<<"vec2 is not greater or equal than vec1."<<endl;
cout<<"\nOperation: vec1 <= vec2"<<endl;
if(vec1 <= vec2)
cout<<"vec1 less or equal than vec2."<<endl;
else
cout<<"vec1 is not less or equal than vec2."<<endl;
return 0;
}
Class | Description |
vector | A template class of sequence containers that arrange elements of a given type in a linear arrangement and allow fast random access to any element. |
Table 27.3 |
The STL vector class is a template class of sequence containers that arrange elements of a given type in a linear arrangement and allow fast random access to any element. They should be the preferred container for a sequence when random-access performance is concerned.
Typedef | Description |
allocator_type | A type that represents the allocator class for the vector object. |
const_iterator | A type that provides a random-access iterator that can read a constelement in a vector. |
const_pointer | A type that provides a pointer to aconstelement in a vector. |
const_reference | A type that provides a reference to a constelement stored in a vector for reading and performing constoperations. |
const_reverse_iterator | A type that provides a random-access iterator that can read any constelement in the vector. |
difference_type | A type that provides the difference between the addresses of two elements in a vector. |
iterator | A type that provides a random-access iterator that can read or modify any element in a vector. |
pointer | A type that provides a pointer to an element in a vector. |
reference | A type that provides a reference to an element stored in a vector. |
reverse_iterator | A type that provides a random-access iterator that can read or modify any element in a reversed vector. |
size_type | A type that counts the number of elements in a vector. |
value_type | A type that represents the data type stored in a vector. |
Table 27.4 |
Member function | Description |
assign() | Erases a vector and copies the specified elements to the empty vector. |
at() | Returns a reference to the element at a specified location in the vector. |
back() | Returns a reference to the last element of the vector. |
begin() | Returns a random-access iterator to the first element in the container. |
capacity() | Returns the number of elements that the vector could contain without allocating more storage. |
clear() | Erases the elements of the vector. |
empty() | Tests if the vector container is empty. |
end() | Returns a random-access iterator that point just beyond the end of the vector. |
erase() | Removes an element or a range of elements in a vector from specified positions. |
front() | Returns a reference to the first element in a vector. |
get_allocator() | Returns an object to the allocator class used by a vector. |
insert() | Inserts an element or a number of elements into the vector at a specified position. |
max_size() | Returns the maximum length of the vector. |
pop_back() | Deletes the element at the end of the vector. |
push_back() | Add an element to the end of the vector. |
rbegin() | Returns an iterator to the first element in a reversed vector. |
rend() | Returns an iterator to the end of a reversed vector. |
resize() | Specifies a new size for a vector. |
reserve() | Reserves a minimum length of storage for a vector object. |
size() | Returns the number of elements in the vector. |
swap() | Exchanges the elements of two vectors. |
vector() | Vector constructor, constructs a vector of a specific size or with elements of a specific value or with a specific allocator or as a copy of some other vector. |
Table 27.5 |
tenouk C++ STL programming tutorial
The source code for this tutorial is available inC++ STL Container source code.
Acomplete C++ Standard Library documentation that includes STL.
Check thebest selling C / C++ books at Amazon.com.