Standard Template Library (STL): An Introduction Part 2

In previous post, STL Part 1.

I have written about the standard libraries in C++ and how some of them are inherited from our beloved C programming language.

In this post I will be walking you through 

• Containers : types and some examples.
• Sequence Containers
• Associative Containers
• Container Adapter Classes
• vector STL Template Class

C++ Standard Template Library (STL)

2.1  Containers

The STL contains sequence containers and associative containers.

• The standard sequence containers : vector, deque, and list.

• Standard associative containers :   set, multiset, map, multimap, hash_set, hash_map, hash_multiset and hash_multimap.

Sequence Containers, Associative Containers and Adapters

STL provides the following types of containers:

1. Sequence Containers: linear data structures of elements
   • vector: dynamically resizable array. Support fast insertion and deletion at back; and direct access to its elements.
   • deque: double-ended queue. Support fast insertion and deletion at front and back; and direct access to its elements.
   • list: double-linked list. Support fast insertion and deletion anywhere in the list; and direct access to its elements.
2. Associative Containers: nonlinear data structures storing key-value pairs
   • set: No duplicate element. Support fast lookup.
   • multiset: Duplicate element allowed. Support fast lookup.
   • map: One-to-one mapping (associative array) with no duplicate. Support fast key lookup.
   • multimap: One-to-many mapping, with duplicates allowed. Support fast key lookup.
3. Container Adapter Classes:
   • Stack: Last-in-first-out (LIFO) queue, adapted from deque (default), or vector, or list. Support operations back, push_back, pop_back.
   • queue: First-in-first-out (FIFO) queue, adapted from deque (default), or list. Support operations front, back, push_back, pop_front.
   • priority_queue: highest priority element at front of the queue. adapted from vector (default) or deque. Support operations front, push_back, pop_front.

C++98/03 has 

11 containers

: vector, stack, list, queue, deque, priority_queue, map, multimap, set, multiset and bitset.

C++11 added 

:forward_list, unordered_map, unordered_multimap, unordered_set and unordered_multiset 

and moves bitset from container category to its own separate category. 

string is not really part of STL, but implemented many STL concepts.

The STL container are template class, which can be instantiated with a type. The actual type has to be copy constructable (having copy constructor) and assignable (overload = operator).

Sequence Container

A sequence container requires that elements are arranged in a strict linear order.

• vector: direct-access class-representation of dynamic array. Elements can be added and removed from the end in constant time. But insertion and removal not from the end require linear time. It supports direct-access, as well as bidirectional transversal.
• deque: (pronounced "deck") double-ended queue, allow elements to be added and removed from both the front and the rear, at constant time. The deque implementation in STL is similar to vector, which allows direct access. It is more complex than vector, as it allows constant-time insertion and removal from the front and rear; whereas vector only for rear.
• list: double-linked list that can be transverse in both direction. It support constant-time insertion and removal, but does not allow direct (random) access with no indexing operator.
• forward_list (C++11): single-linked list that support forward transversal only. It is simpler than list.
• queue: allow elements to be added at the rear and removed from the front at constant time. STL's queue is very restrictive that it does not support direct access nor transversal through the elements.
• priority_queue: Similar to queue, but move the larger element to the front of the queue.
• stack: LIFO (last-in-first-out) queue, elements can be added and removed from the top-of-stack in a last-in-first-out manner. In STL, stack is an adapter class over the vector class. It is more restrictive than vector. Elements can only be accessed, added and removed from one-end (top-of-stack). It does not support direct access, nor transversal through all the elements.
• array (C++11): array is NOT a STL container because it has a fixed size and does not support operations like insert. But you can apply STL algorithms on array container.

Associative Containers

Associative container stores key-value pair or name-value pairs (i.e., associate a key with a value, and use a key to find the value). Associative container (or associative array) is actually similar to an array or vector, where a numerical index key is associated with a value, and you use the numerical key to find a value. Example of key-value pair are person-phone number(s), id-name, etc.

STL supports the following associative containers:

• set: the key is the same as the value. It does not allow duplicate values. STL set is sorted and reversible.
• multiset: allow duplicate values.
• map: key-value pair, where keys are unique. One key is associated with one value. STL map is sorted and reversible. It needs two types to instantiate: map<key-type, value-type). To represent each key-value, STL provides a template class called pair<class K, class V>. You can instantiate the template class with specific key-type and value-type, e.g., pair<const int, string>.
• multimap: one key could be associated with multiple values.
• C++11 added 4 unordered associative containers: unordered_set, unordered_multiset, unordered_map, and unordered_multimap. These unordered associative containers are based on hash table (efficient in insertion, removal and search, but requires more storage spaces); whereas the ordered counterparts are based on tree.

First-class Containers, Adapters and Near Containers

The containers can also be classified as:

1. First-class Containers: all sequence containers and associative containers are collectively known as first-class container.
2. Adapters: constrained first-class containers such as stack and queue.
3. Near Containers: Do not support all the first-class container operations. For example, the built-in array (pointer-like), bitsets (for maintaining a set of flags), valarray (support array computation),string (stores only character type).

Container's Functions

All containers provides these functions:

• Default Constructor: to construct an empty container. Other constructors are provided for specific purposes.
• Copy Constructor:
• Destructor:
• empty(): returns true if the container is empty.
• size(): returns the size (number of elements).
• Assignment Operator (=)
• Comparison Operators (==, !=, <, <=, >, >=).
• swap(): exchanges the contents of two containers.

In addition, the first-class containers support these functions:

• begin, end, cbegin, cend: Returns the begin and end iterator, or the const version.
• rbegin, rend, crbegin, crend: Returns the reverse_iterator.
• clear(): Removes all elements.
• erase(): Removes one element given an iterator, or a range of elements given [begin, end) iterators.
• max_size(): Returns the maximum number of elements that the container can hold.

Container Header

• <vector>
• <list>
• <deque>
• <queue>: queue and priority_queue
• <stack>
• <map>: map and multimap
• <set>: set and multiset
• <valarray>
• <bitset>
• <array> (C++11)
• <forward_list> (C++11)
• <unordered_map> (C++11)
• <unordered_set> (C++11)

2.2  Let's Get Started with Examples of vector STL Template Class

In computing, a vector refers to an array-like structure that holds a set of direct-access elements of the same kinds, instead of mathematical n-component vector. Unlike array which is fixed-size, vector is dynamically-sized. vector is a class template, declared in the vector header.

Let's begin with some examples.

Example 1: Construct vector<> object and access its elements

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

/* Test vector class element access (TestVectorIndex.cpp) */ #include <iostream> #include <cstdlib> #include <ctime> #include <vector> using namespace std; void print(const vector<int> & v); int main() { const int SIZE = 10; vector<int> numbers(SIZE); // Declare vector of int of SIZE elements, init to 0 cout << "size = " << numbers.size() << endl; cout << "capacity = " << numbers.capacity() << endl; print(numbers); // Assign random numbers into vector srand(time(0)); // Seed the pseudo-random number generator for (size_t i = 0; i < numbers.size(); ++i) { numbers.at(i) = rand() % 100; // at() did bound check } print(numbers); cout << "First element is " << numbers.front() << endl; cout << "Last element is " << numbers.back() << endl; // [] does not perform index bound check, but at() does cout << numbers[55] << endl; // no error compile and run// cout << numbers.at(55) << endl; // runtime out_of_range exception return 0; } // Print the content of this vector using indexing operator [] void print(const vector<int> & v) { for (int i = 0; i < v.size(); ++i) { cout << v[i] << " "; // no bound check, but safe here } cout << endl; }

Program Notes:

• vector is a template class. We create an int specialization via vector<int>. We create a vector<int> object via constructor vector<int> numbers(SIZE); which allocates SIZE elements and initializes to 0.
• The size() member function returns the number of elements. The capacity() returns the storage allocated. All STL containers dynamically allocate storage.
• Elements in vector has a linear order index. You can use [] overloaded operator or at() member function to access the n-th element. Take note that [] does not perform index-bound check; but at()does at runtime and throws out_of_range exception if index exceeds bound.
• The member function front() and back() returns the first and last element respectively.

Example 2: Using push_back() and pop_back() to add and remove element

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43

/* Test modifying vector class's element (TestVectorMod.cpp) */ #include <iostream> #include <cstdlib> #include <ctime> #include <vector> using namespace std; void print(const vector<int> & v); int main() { vector<int> numbers; // Declare vector of int with initial size of 0 cout << "size = " << numbers.size() << endl; cout << "capacity = " << numbers.capacity() << endl; // Assign random numbers into vector srand(time(0)); for (int i = 0; i < 5; ++i) { numbers.push_back(rand() % 100); // Append element at the end - vector resize automatically } print(numbers); cout << "size = " << numbers.size() << endl; cout << "capacity = " << numbers.capacity() << endl; numbers.pop_back(); // Remove the last element - size reduces by 1 numbers.pop_back(); print(numbers); cout << "size = " << numbers.size() << endl; cout << "capacity = " << numbers.capacity() << endl; numbers.clear(); // Remove all elements cout << "size = " << numbers.size() << endl; cout << "capacity = " << numbers.capacity() << endl; return 0; } // Print the content of this vector using indexing operator [] void print(const vector<int> & v) { for (int i = 0; i < v.size(); ++i) { cout << v[i] << " "; // no bound check, but safe here } cout << endl; }

Program Notes:

• The default constructor vector<int> numbers construct a vector object with size of 0.
• The member function push_back() appends the item at the end; while pop_back() removes the last element.
• It is very important to note that in a vector you can add or delete an element only from the back and not from the front! (This is added in the list container which I will be covering in a short while)

Example 3: Using iterator to access the container

We can use a special object called iterator to iterate through all the elements of a STL container, such as vector. The vector class provides a pair of functions begin() and end() to work with iterator. To use iterator:

// Declare a vector
vector<int> aVector(10);
// Declare an iterator called iter for vector<int>
vector<int>::iterator iter;
// Assign iter to the beginning of the vector
iter = aVector.begin()
// Use *iter to access the current element
cout << *iter << endl;
// Next element
++iter;
// The pass-the-end element is aVector.end() - to be excluded

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45

/* Test vector class's iterator (TestVectorIterator.cpp) */ #include <iostream> #include <string> #include <cstdlib> #include <vector> using namespace std; void print(vector<string> & v); int main() { vector<string> strs; strs.push_back("apple"); strs.push_back("orange"); strs.push_back("banana"); print(strs); cout << "size = " << strs.size() << endl; // Test insert() strs.insert(strs.begin() + 2, "b4-banana"); strs.insert(strs.begin() + 1, 2, "b4-orange"); print(strs); cout << "size = " << strs.size() << endl; // Test erase() strs.erase(strs.begin() + 1, strs.begin() + 4); print(strs); cout << "size = " << strs.size() << endl; // insert() from another vector vector<string> newStrs; newStrs.push_back("1"); newStrs.push_back("2"); newStrs.push_back("3"); strs.insert(strs.begin() + 1, newStrs.begin(), newStrs.end()); print(strs); cout << "size = " << strs.size() << endl; } // Use iterator to iterate thru the entire vector void print(vector<string> & v) { for (vector<string>::iterator iter = v.begin(); iter != v.end(); ++iter) { cout << *iter << " "; // dereference } cout << endl; }

Program Notes:

• Each container class defines its suitable iterator, with type name of vector<T>::iterator.
• The vector's member function begin() and end() returns an iterator to the first element and the pass-the-end element, respectively. The pass-the-end element shall be excluded, i.e., [begin(), end()).
• Iterator works like pointer, you can use *iter (dereferencing operator) to retrieve the vector element; ++iter (increment operator) to move to the next element; iter+n to point to the +n element.
• The insert() and erase() member functions works on the iterator as well. insert(iter, item) inserts item before the iter-element. insert(insert, n, item) fills n element before the iter-element. erase(fist, last) removes all element in [first, last).
• In C++11, you can use the auto as the type of iterator, which asks the compiler to deduce the type automatically.

  for (auto iter = strs.begin(); iter != strs.end(); ++iter) {
     cout << *iter << " ";           // Print string
  }
  cout << endl;
  

• C++ introduces for-each loop, which can be used to iterate thru all the items of an array or a container:

  for (auto item : strs) {
     cout << item << " ";
  }
  cout << endl;
  

2.3  The vector Template Class

Let's take a closer look at the vector template class, which serve as a sample for all the STL container classes.

Constructor

vector (const allocator_type & alloc = allocator_type());
   // Default Constructor: construct a vector objectvector (size_type n, const value_type & val = value_type(),
        const allocator_type & alloc = allocator_type());
   // Fill Constructor: construct a vector object with n-element filled with valvector (const vector & v);
   // Copy Constructor
template <class InputIterator>
vector (InputIterator first, InputIterator last,
        const allocator_type & alloc = allocator_type());
   // Range Copy Constructor

Size and Capacity

size_type size () const;      // Return the size (number of elements)
size_type capacity () const;  // Return the storage allocated (in term of element)
bool empty () const;          // Return true if size is 0
void reserve (size_type n);   // Request for storage to hold n elements
void resize (size_type n, value_type val = value_type());
      // resize to n, remove extra element or fill with val
size_type max_size () const;  // Return the maximum number of element
void shrink_to_fit ();        // (C++11) Request to shrink storage

Accessing Element

value_type & operator[] (size_type n);  // [n] operator (without index-bound check)
value_type & at (size_type n);          // Return a reference to n-th element with index-bound check
value_type & front ();    // Return a reference to the first element
value_type & back ();     // Return a reference to the last element

Modifying Contents

void push_back (const value_type & val); // Append val at the end
void pop_back ();                        // Remove the last element
void clear ();                           // Remove all elements

Non-member Friend Functions

==, !=, <, >, <=, >=    // Comparison Operators// E.g.
template <class T, class Alloc>
bool operator== (const vector<T,Alloc> & left, const vector<T, Alloc> & right);
   // Compare two vectors
   // For == and !=, first compare the size, then each element with equal algorithm.
   //   Stop at the first mismatch.
   // For <, >, <=, >=, use lexicographical_compare algorithm. Stop at first mismatch.
 
template <class T, class Alloc>
void swap (vector<T,Alloc> & v1, vector<T,Alloc> v2);
   // Swap the contents of containers v1 and v2.
   // Both shall has the same type, but can have different sizes.

Iterator

iterator begin();  // Return an iterator pointing to the first element
iterator end();    // Return an iterator pointing to the pass-the-end element
 
reverse_iterator rbegin(); // Return a reverse iterator pointing to the reverse beginning (last element)
                           // increasing a reverse iterator to transverse in reverse order
reverse_iterator rend();   // Return a reverse iterator pointing to the reverse past-the-end

Iterator-based Operations

iterator insert (iterator pos, const value_type & val);  // Single-Element: insert element val before iterator pos
void     insert (iterator pos, size_type n, const value_type & val);  // Fill: insert n copies of val before pos
template <class InputIterator>
void     insert (iterator pos, InputIterator first, InputIterator last)
    // Range-copy: copy the range [first, last) and insert before pos.
 
iterator erase (iterator pos);  // Single-element: remove element pointed to by iterator pos
iterator erase (iterator first, iterator last);  // Range: remove elements between [first,last)
 
void assign (size_type n, const value_type & val);  // Fill: clear old contents and assign n copies of val
template <class InputIterator>
void assign (InputIterator first, InputIterator last);  // Range: assign [first, last)

[TODO] Example

In the next post, STL : An introduction Part 3.

I have explained in detail about iterators and continue with STL.

I hope it helped and subscribe if you want more interesting articles coming up your mail ! :)

Cheers!