Containers in C++
Containers are used to manage collections of objects of a certain kind. There are several different types of containers like deque, list, vector, map etc. A container is a holder object that stores a collection of other objects (its elements). They are implemented as class templates, which allows a great flexibility in the types supported as elements.
The container manages the storage space for its elements and provides member functions to access them, either directly or through iterators (reference objects with similar properties to pointers).
Containers replicate structures very commonly used in programming: dynamic arrays (vector), queues (queue), stacks (stack), heaps (priority_queue), linked lists (list), trees (set), associative arrays (map)…
Many containers have several member functions in common, and share functionalities. The decision of which type of container to use for a specific need does not generally depend only on the functionality offered by the container, but also on the efficiency of some of its members (complexity). This is especially true for sequence containers, which offer different trade-offs in complexity between inserting/removing elements and accessing them.stack, queue and priority_queue are implemented as container adaptors. Container adaptors are not full container classes, but classes that provide a specific interface relying on an object of one of the container classes (such as deque or list) to handle the elements. The underlying container is encapsulated in such a way that its elements are accessed by the members of the container adaptor independently of the underlying container class used.
The Containers library is a generic collection of class templates and algorithms that allow programmers to easily implement common data structures like queues, lists and stacks. There are three classes of containers — sequence containers, associative containers, and unordered associative containers — each of which is designed to support a different set of operations.
The container manages the storage space that is allocated for its elements and provides member functions to access them, either directly or through iterators (objects with similar properties to pointers).
Most containers have at least several member functions in common, and share functionalities. Which container is the best for the particular application depends not only on the offered functionality, but also on its efficiency for different workloads.
1.Sequence containers
Sequence containers implement data structures which can be accessed sequentially.
Array static contiguous array (class template)
vector dynamic contiguous array (class template)
deque double-ended queue (class template)
forward_list singly-linked list (class template)
list doubly-linked list (class template)
2.Associative containers
Associative containers implement sorted data structures that can be quickly searched (O(log n) complexity).
Set collection of unique keys, sorted by keys (class template)
Map collection of key-value pairs, sorted by keys, keys are unique (class template)
Multiset collection of keys, sorted by keys (class template)
Multimap collection of key-value pairs, sorted by keys (class template)
3.Unordered associative containers
Unordered associative containers implement unsorted (hashed) data structures that can be quickly searched (O(1) amortized, O(n) worst-case complexity).
unordered_set collection of unique keys, hashed by keys (class template)
unordered_map collection of key-value pairs, hashed by keys, keys are unique (classtemplate)
unordered_multiset collection of keys, hashed by keys (class template)
unordered_multimap collection of key-value pairs, hashed by keys (class template)
4.Container adaptors
Container adaptors provide a different interface for sequential containers.
Stack adapts a container to provide stack (LIFO data structure) (class template)
Queue adapts a container to provide queue (FIFO data structure) (class template)
priority_queue adapts a container to provide priority queue (class template)
2.Algorithms Algorithms act on containers. They provide the means by which you will perform initialization, sorting, searching, and transforming of the contents of containers.
3.Iterators Iterators are used to step through the elements of collections of objects. These collections may be containers or subsets of containers.
We will discuss about all the three C++ STL components in next chapter while discussing C++ Standard Library. For now, keep in mind that all the three components have a rich set of pre-defined functions which help us in doing complicated tasks in very easy fashion.
Let us take the following program demonstrates the vector container (a C++ Standard Template) which is similar to an array with an exception that it automatically handles its own storage requirements in case it grows:
#include <iostream>
#include <vector>
using namespace std;
int main() {
// create a vector to store int
vector<int> vec;
int i;
// display the original size of vec
cout << “vector size = ” << vec.size() << endl;
// push 5 values into the vector
for(i = 0; i < 5; i++){
vec.push_back(i);
}
// display extended size of vec
cout << “extended vector size = ” << vec.size() << endl;
// access 5 values from the vector
for(i = 0; i < 5; i++){
cout << “value of vec [” << i << “] = ” << vec[i] << endl;
}
// use iterator to access the values
vector<int>::iterator v = vec.begin();
while( v != vec.end()) {
cout << “value of v = ” << *v << endl;
v++;
}
return 0;
}
When the above code is compiled and executed, it produces the following result:
vector size = 0
extended vector size = 5
value of vec [0] = 0
value of vec [1] = 1
value of vec [2] = 2
value of vec [3] = 3
value of vec [4] = 4
value of v = 0
value of v = 1
value of v = 2
value of v = 3
value of v = 4
Here are following points to be noted related to various functions we used in the above example:
The push_back( ) member function inserts value at the end of the vector, expanding its size as needed.
The size( ) function displays the size of the vector.
The function begin( ) returns an iterator to the start of the vector.
The function end( ) returns an iterator to the end of the vector.