Standard Template Library (STL)

Standard Template Library (STL)

The Standard Template Library defines powerful, template-based, reusable components
That implements common data structures and algorithms
STL extensively uses generic programming based on templates
Divided into three components:
Containers: data structures that store objects of any type
Iterators: used to manipulate container elements
Algorithms: searching, sorting and many others

CONTAINERS

Three types of containers
Sequence containers:
linear data structures such as vectors and linked lists
Associative containers:
non-linear containers such as hash tables
Container adapters:
constrained sequence containers such as stacks and queues
Sequence and associative containers are also called first-class containers

ITERATORS

Iterators are pointers to elements of first-class containers
Type const_iterator defines an iterator to a container element that cannot be modified
Type iterator defines an iterator to a container element that can be modified
All first-class containers provide the members functions begin() and end()
return iterators pointing to the first and one-past-the-last element of the container
If the iterator it points to a particular element, then
it++ (or ++it) points to the next element and
*it refers to the value of the element pointed to by it
The iterator resulting from end() can only be used to detect whether the iterator has reached the end of the container
We will see how to use begin() and end() in the next slides

Sequence Containers: vector

The implementation of a vector is based on arrays
Vectors allow direct access to any element via indexes
Insertion at the end is normally efficient.
The vector simply grows
Insertion and deletion in the middle is expensive
An entire portion of the vector needs to be moved
When the vector capacity is reached then
A larger vector is allocated,
The elements of the previous vector are copied and
The old vector is deallocated
To use vectors, we need to include the header
Some functions of the class vector include
size, capacity, insert…

EXAMPLES OF USING THE CLASS VECTOR
#include
#include //vector class-template

using std;

int main()
{
vector v;

// add integers at the end of the vector
v.push_back( 2 );
v.push_back( 3 );
v.push_back( 4 );

cout << « \nThe size of v is:  » << v.size()
<< « \nThe capacity of v is:  »
<< v.capacity();