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.

• Containers
• Iterators
• Algorithms

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 :

• Vectors
• Deques (double ended queue)  
  

Associative containers :

• Sets, multisets
• Maps, multimaps
  

//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

• Objects capable of iterating over elements of a containers
• Some of the properties of the iterators are useful for all the containers, other are specific to a given container
• Behave like pointers
  

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,

• reverse (C.begin(),C.end()); // reverses the order of the elements of C
• remove (C.begin(),C.end(),my_value); // Removes all the elements of the range [beg,end) having the value my_value and return the position of the new end
• min_element (C.begin(),C.end()); // provides the position of the minimum of C
• sort (C.begin(),C.end()); // sorts the elements of C in the increasing order

2 -  Examples

2-1 Vectors

• Dynamic array, good performance when appending or deleting elements at the end
• Bad performance when adding or removing elements in the middle

//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

• Sort their elements automatically
  
• Good performance for searching elements
• Set vs. Multiset: Multisets allow duplicates while Sets do not
  

//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:

• antisymetric: if (x op y) is true, then (y op x) is false
• transitive: (x op y) and (y op z) implies (x op z)
• irreflexive: (x op x) is false
  

Exemples of sorting criterions

• Default criterion: "less"; elements are compered with the operator "<"
  

     //Delaration
     set <my_type> name_of_my_set; // exemple: set <double> S;

• Greater criterion: elements are compered with the operator ">"

       //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 :

• The logical element C.insert(elem).second returns "true"  if the insertion was succesful (ie: if the set did not contain elem before the insertion) , and "false" otherwise.

• The iterator element C.insert(elem).first returns the position of the newly inserted element if C.insert(elem).second = = "true", or the position of the still existing element otherwise.

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:

• S1: double, ascending order, with the values 5.0, 3.2, 3.2, 4.6, 5.0, 6.0, 3.2, 7.0, 7.0, 2.9, 1.1, 6.5.
• S2: double, decreasing order, empty.

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

• Look like sets, with two entries for each element: a key and a value
  
• Sort their elements automatically with respect to their key
• Good performance for searching elements having a certain key
• Bad performance for searching elements having a certain value
  
• Map vs. Multimap: Multimaps allow duplicates while Maps do not
  

//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 instruction pos->first returns the key of the element in the current position of pos.
• the instruction pos->second returns the value of the element in the current position of pos.

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;

• Use value_type function: M.insert(map<double, string>::value_type(2.0,"hello"));
• Use pair: M.insert(pair<double, string>(2.0,"hello"));
• Use make_pair: M.insert(make_pair(2.0,"hello"));
  

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