STL CONTAINERS





The Standard templates library (STL) provides  efficient tools that may be useful for several codes, adapted to several topics, scientifc and non scientific.
Users don't have necessarily to know how these tools  work.

1 - Design features - Definitions


1-1 Containers

A container is the name of  an STL object. Its usually a collection of elements, such as particular arrays, lists ...

Exemples :

Sequence containers :

Associative containers :

//Heading
#include<container_name>   //example:
#include<vector>

//Declaration of a container that we call C

container_name <my_type, ...>  C;  // example: vector <double> C; + possibly optional arguments

1-2 Basic functions

Operation

Effect

container_name <my_type> C
Creates an empty container "C" without any element
container_name <my_type> C2(C1) Copies the container C1 into a new container C2
container_name <my_type> C(beg,end) Creates a container and initializes it with the elements of the range [beg,end)
C.clear( )
Deletes all elements and frees the memory (anyway, the container's life ends automatically at the end of the scope where it is declared)
C.size( )
Returns the actual numer of elements
C.empty( )
Returns "true" if the container is empty, "false" if it is not
C.max_size( )
Returns the maximum number of elements possible
C1= = C2
Logical: returns whether C1 is equal to C2
C1 != C2
Logical: returns whether C1 is not equivalent to C2
C1 < C2, (C1<= C2)
Logical: returns whether each entry of C1 is less than ( less or equal to)  the corresponding entry of C2
C1 > C2, (C1>= C2) Logical: returns whether each entry of C1 is greater than ( greater or equal to)  the corresponding entry of C2
C1=C2
Assignment
C1.swap(C2)   ,    or swap(C1,C2)
Swap
C.begin( )
Returns an iterator for the first element
C.end ( )
Returns an iterator for the last element
C.rbegin( )
Returns a reverse iterator for the first element of a reverse iteration
C.rend( )
Returns a reverse iterator for the last element of a reverse iteration
C.insert(pos,elem )
Inserts a copy of elem at location pos
C.erase(beg,end)
Removes all the elements of the range [beg,end)
C.clear( )
Makes the container empty


1-3 Iterators
Example:

//Heading
#include <container_name>

//Declaration of a container that we call C
container_name <my_type>  C;

// Declaration of an iterator that we call "pos"
container_name <my_type> :: iterator pos;  // Rmq: it does not mention C !
//also possible :
container_name <my_type> :: const_iterator pos;

//Writing the values of C on the screen
for (pos = C.begin(); pos! = C.end(); ++pos) {
    cout << *pos << endl;     // writes the pos^th entry of the vector C
}

!!! Arguments in the "for" loop must be self contained and  have to enable the compiler to know what the iterator "pos" refers to !!!

!!! The instruction:
" for (pos = C.begin(); pos< C.end(); ++pos) " may not work in certain cases, e.g. if C is an associative container !!!

Operations on iterators:

Operator * : returns the element of the actual position
Operator ++ : steps forward to the next element
Operator = = and != : tests whether two iterators represent the same position
Operator = : assignment

// Declaration of an reverse iterator that we call "rpos"
container_name <my_type> :: reverse_iterator rpos; 
//also possible :
container_name <my_type> :: const_reverse_iterator rpos;

//Writing the values of C on the screen in the reverse order
for (rpos = C.rbegin(); pos! = C.rend(); ++rpos) {
    cout << *rpos << endl;     // writes the pos^th entry of the vector C
}


1-4 Algorithms

Functions aimed at manipulating containers.
They rely upon the kind of container used in the code

//Heading
#include <Algorithm>

Examples: for a vector called C,


2 -  Examples

2-1 Vectors
//Heading
#include <vector>

//Declaration
vector <type_of_my_vector> name_of_my_vector; // example : vector <int> V

The good performance of the vectors comes from the fact that vectors usually allocate more memory than they need. This usually avoids reallocations.
However, one may want to ensure the maximum capacity of a vector by typing

name_of_my_vector.reserve(100); // sets the capacity of the vector to 100

2-1-1 Operations

Create operations
Operation
Effect

vector<type> C
Creates an empty vector called C without any element
vector<type> C2(C1)
Creates a vector C2 that is the copy of C1 (all the elements are copied)
vector<type> C(n)
Creates a vector with n elements
vector<type> C(n,elem)
Creates a vector featuring n copies of  element elem
vector<type> C(beg,end)
Creates a vector initialized with the elements of the range [beg,end)

Nonmodifying operations
Operation

Effect
C.capacity( )
Returns the maximum possible number of elements without reallocation
C.reserve(my_value)
Enlarges capacity, if not enough yet

Assignments
Operation

Effect
C.assign (n,elem)
Assigns n copies of element elem
C.assign(beg,end)
Assigns the elements of the range [beg,end)

Element access
Operation

Effect
C.at(idx)
Returns the element with index idx (throws range exception if idx is out of range)
C[idx]
Returns the element with index idx with no range checking
C.front( )
Returns the first element (no check whether the first element exists)
C.back( )
Returns the last element (no check whether the last element exists)

Rmq: A vector can be used like an array; if the i^th component of a vector V exists, then the command  V[i]  has a meaning.


Inserting and removing elements
Operation

Effect
C.push_back(elem)
Appends a copy of elem
C.pop_back( )
Removes the last element
C.erase( )
Removes the element at iterator position and returns the position of the next element
C.erase(beg,end)
Removes all elements of the range [beg,end) and returns the position of the next element
C.resize(num)
Change the number of elements to num
C.resize(num,elem)
Change the number of elements to num (if the size grows, new elements are afected the value elem)


2-1-1 Exemple of using vectors

Exercise:
Create two empty vectors, V1, V2, and assign V1 with the values 1,2,3,1,2,3. Using the function "erase", drop all the elements having for value 2 in V1.
Assign V2 so that each V2-entry is the square of the corresponding V1-entry. Last, print V1 in the normal order and V2 in the reverse order.


Answer:


2-2 Sets, Multisets
//Heading
#include <set>


2-2-1 Declarations

//Declaration
set <my_type,opt_sort_criterion> name_of_my_set;

The type "my_type" must be comparable according to the sorting criterion.
The optional argument "opt_sort_criterion" defines the sorting criterion. The sorting operator, that we call here "op", has the usual mathematical meaning: it must be:
Exemples of sorting criterions
     //Delaration
     set <my_type>
name_of_my_set; // exemple: set <double> S;
       //Declaration
       set <my_type,greater<my_type> >
name_of_my_set;
       // exemple: set <int,greater<int> > S ;
   
!!! Remark: necessity to insert a "space" between the two symbols << in the previous declaration !!!


//Declaration of a multiset
multiset <my_type,opt_sort_criterion> name_of_my_multiset;

!!! Direct access is not allowed when using sets/multisets: instruction name_of_my_set[my_index] induces a compilation error !!!

!!! Modifying elements is not allowed !!!

2-2-2 Operations

Create operations
Operation
Effect
set<type,opt> C
Creates an empty set called C without any element
set<type,opt> C2(C1)
Creates a set C2 that is the copy of C1 (all the elements are copied)
set<type,opt> C(beg,end)
Creates a set initialized with the elements of the range [beg,end)


Special Search Operations
Operation

Effect
C.count (elem)
Return the number of elements with value elem
C.find (elem)
Returns the first element with value elem, or C.end( )
C.lower_bound (elem)
Returns the first element > or = to elem
C.upper_bound (elem)
Returns the first element > elem
C.equal_range (elem)
Returns the position of the first element = = elem and the position of the last element = = to elem


Removing elements
Operation

Effect
C.erase(elem) Removes all elements having for value elem and returns the number of removed elements
C.erase(pos)
Removes the element at iterator position pos and returns nothing
C.erase(beg,end)
Removes all elements of the range [beg,end) and returns nothing
C.resize(num)
Change the number of elements to num


Inserting elements: Multisets
Operation

Effect
C.insert (elem) Insert a copy of elem and returns the position of the new element
C.insert (pos,elem) Insert a copy of elem and returns the position of the new element (insert starts the search from position pos)
C.insert (beg,end) Insert a copy of all elements of the range [beg,end)


Inserting elements: Sets
Operation

Effect
C.insert (elem) Insert a copy of elem, returns the position of the new element and whether it succeeded
C.insert (pos,elem) Insert a copy of elem, returns the position of the new element (insert starts the search from position pos) and whether it succeded


Since sets do not allow duplicates, these above functions return two elements by using the standard c++ structure pair :


Example: The following code tries to add the element 5.6 in a double typed set S. If S already contains 5.6, it prints "5.6 is already contained in S". If S  does not already contains 5.6, it prints "Insertion completed":

if (S.insert(5.6).second)  {cout << "Insertion completed" << endl;}
else {cout << "5.6 is already contained in S" << endl;}


Example:  the following code further prints the position where the operation happens:

//Declaration of a pair
pair <set<double> :: iterator,bool> :: my_pair;

//Call function insert and assign my_pair
my_pair=
S.insert(5.6);

//Print on the screen
if (my_pair.second)  {
    cout << "Insertion completed at position " << distance (S.begin( ),my_pair.first)+1 << endl;
}
else {
    cout << "5.6 is already contained in S at position " 
<< distance (S.begin( ),my_pair.first)+1 << endl;
}


2-2-3 Exemple of using sets and multisets

Exercise:
Create two multisets:
Print S1, remove the first element having for value 3.2 in S1, and re-print S1. Assign S2 with the same values than S1 has, and remove all the elements having for value 7 in S2. Last, print all the value greater than 5 in S2.

Answer



2-3 Maps, Multimaps

//Heading
#include <map>


//Declarations
map <type_key, type_value, opt_sort_criterion> name_of_my_map;

multimap <type_key, type_value, opt_sort_criterion> name_of_my_multimap;


!!! Modifying the key of an element is not allowed !!!

2-3-1 Operations

Create operations
Operation
Effect
map<type_key,type_value,opt> C
Creates an empty map called C without any element
map<type_key,type_value,opt> C2(C1)
Creates a map C2 that is the copy of C1 (all the elements are copied)
map<type_key,type_value,opt> C(beg,end)
Creates a map initialized with the elements of the range [beg,end)



Special Search Operations
Operation

Effect
C.count (elem_key)
Return the number of elements with key elem_key
C.find (elem_key)
Returns the first element with key elem_key, or C.end( )
C.lower_bound (elem_key)
Returns the first element with key > or = to elem_key
C.upper_bound (elem_key)
Returns the first element with key > elem_key
C.equal_range (elem_key)
Returns the position of the first element with key = = elem_key
and the position of the last element with key = = to elem_key

Iterators
When dealing with maps/multimaps, an iterator refers to a pair representing (key,value), and the operator * is useless.
Let pos be an iterator:

The following loop prints all the keys and values of a map by using an iterator:

//Declaration of a map
map <double, string> M;

//Declaration of an iterator
map <double, string> :: iterator pos;

//Print
for (pos=M.begin( ); pos != M.end( ); ++pos) {
    cout << "Key = " << pos->first << " Value = " << pos->second";
}



Inserting elements (function insert)
Need to insert both key and value of the element; three ways:
Example: let us insert the element (2.0,"hello") in a map M
declared as: map <double, string> M;


Removing elements

Operation

Effect
C.erase(elem_key) Removes all elements having for key elem_key and returns the number of removed elements
C.erase(pos)
Removes the element at iterator position pos and returns nothing



Using maps as associative arrays
Operation

Effect
C.[elem_key] Returns a reference to the value of the element with key elem_key if it exists, or inserts and element with key elem_key if it exists

To assign the value of an element into the previous map, the instruction  C.[1.5]="good  bye"  assigns "good bye" as the value of the element with key 1.5 if it exists, and creates an element with key 1.5 and value "good bye" if it does not. 


2-2-3 Exemple of using map and multimaps

Exercise: Create an empty Map M with "string" type keys, representing a brand, and "double" type values, representing the price of this brand in dollars. Assign M by translating:

Sony costs $100,
JVC costs $120,
Philips costs $120,
Samsung costs $130,
Siemens costs $140.

By using an iterator on M, print every brand followed by its price. Replace the name "Siemens" with "Sie". Increase all the prices by 25%, and re-print the brands followed by their prices.

Answer