A container is an object that stores a collection of elements (other objects). Each container manages the storage space for its elements and provides access to them through iterators and/or member functions.
Containers are implemented as classes in STL and thus provide several member functions.
Note : iterators are used to point to the containers in STL, so iterators are somewhat like pointers in C/C++.
There are three categories of containers in STL :
1. sequence containers (eg. vector, list etc.)
2. associative containers (eg. map, set etc. )
3. unordered containers (eg. unordered_set, unordered_map etc.)
To use containers or algorithms in STL, we need to use the corresponding
header files, like
#include<vector> // for using vector container
#include<deque>
#include<list>
#include<set>
#include<map>
Their use can be easily understood by looking at their names
If
you want to avoid writing separate header files, you can use a single header
file to encapsulate all the functionality provided by STL.That header is
#include<bits/stdc++.h>
All the STL functionality is implemented inside 'std' namespace. 'std'
is abbreviation for standard. We need to use 'std' namespace for using any STL
container or algorithm. Therefore I recommend importing 'std' namespace in
your program to avoid preceding everything with 'std::'.
so we add
:
using namespace std;
Now we are ready to start writing STL code.
Let's discuss sequence containers.
Sequence Containers :
They are used to implement data structures that are sequential in nature like
arrays(array) and linked list(list).
Some sequence containers are :
vector, deque, list, array etc.
Let's discuss some of them in detail.
1. vector
A vector is a dynamic array ( size not fixed) which grows in one
direction(towards the end). It stores elements in contiguous memory
locations.
=> Creating a vector :
vector provides different constructors for its creation.
For example to
create an integer vector vec, we write
a.
vector<int> vec; // creates an
empty vector. vec.size() = 0
//
vec.size() is a member function provided by vector which tells the current
number
of elements in vector.
b.
vector<int> vec(10); // creates a vector of 10 uninitialized integers.
vec.size()=10;
c.
vector<int> vec(10,0);
// creates a vector of 10 integers initilaized to 0.
vec.size()=10;
d.
vector<int> vec(vec2); // copy constructor copies all values
of vec2 into vec
e.
vector<int> vec = {2,3,5};
=> Adding/removing an element at end of vector
Since vector is dynamic, you can grow or shrink your vector from the end as
per your requirement.
vector<int> vec; // vec.size()=0
vec.push_back(10); // inserts 10 at the end of
vector vec={10}
vec.push_back(20); // vec={10,20}
vec.pop_back(); // removes last
element(20) from vector vec={10};
=> Access an element of vector
vector provides random access just like array.
a.
cout<<vec[1];
// prints 2nd element of vec(0 base indexing)
but performs no range check
b.
cout<<vec.at(1);
// also performs range check and throws exception if index out of range of
vec
Note : 'auto' is introduced from C++ 11 and is
useful for difficult type names. The compiler automatically infers the correct
type from the data provided.
=> Traversing all the vector elements using for loop.
a. traversal using index of elements
for(int i=0;i<vec.size();i++)
cout<<vec[i]<<" ";
b. using for-each version
for(auto v : vec)
// v automatically gets assigned values of vector one by
one but it is read only traversal
cout<<v<<" ";
c. using iterator
for(auto it=vec.begin();it!=vec.end();it++) // auto can be replaced by
vector<int> :: iterator
cout<<*it<<" ";
=> Traversal using iterator is recommended because :
1.
This methods is faster than using random access operator.
2. This
a universal way of traversing any container in STL and therefore very
important.
Note : These are some common member
functions for all STL containers :
1.
vec.empty()
// boolean function, returns true(0) if vector has no
elements, false otherwise.
2. vec.size() // returns current size of vector
3. vec.clear()
// removes all the elements of vector
Properties of vector :
a. Fast insertion/removal at the end. Time complexity O(1).
b. Slow insertion/removal at any place other than the end
because vector is stored in contiguous memory locations so the other elements
need to be shifted to make space for new insertion. Time complexity
O(n) (linear).
c. Slow search of elements as there is
no order among them. Time complexity O(n).
2. deque
deque is very similar to vector. The main difference is that vector grows in
only one direction, whereas deque grows in both the directions, i.e
from front as well as end.
=> Creating a deque is similar to creating a vector
deque<int> dq;
=> Adding/removing an element at beginning or at end of vector
push_back(val), push_front(val) // add new element at the end or front of vector
respectively.
pop_back(), pop_front() // remove an element from
the end or front of vector respectively.
=> Traversing deque is similar to vector as deque also provides random
access operator like vector.
Properties of deque:
a. Fast insertion/removal at beginning or at end. Time complexity
O(1).
b. Slow insertion/removal at any other place.
Time complexity O(n) (linear).
c. Slow search of
elements as there is no order among them. Time complexity O(n).
3. list
A list in STL is a doubly linked list data structure in which
each node has two pointers pointing to to its next node and previous node
respectively.
The key feature of list is that we have fast insert/removal
of any element of the list at any position but only if we have an iterator to
the desired position.
=> Creating a list
list<int> lis ={2,20,10};
=> list also provides methods push_back(),push_front(), pop_back(),
pop_front() provided by deque for insertion/removal at back or front
respectively.
To insert an element at any other position, first we
require iterator to the desired position.
Let's insert value 5 at
position of 20.
we use find algorithm function(which we will
discuss later) to get an iterator to position where 20 is sotred.
auto it = find(lis.begin(),lis.end(),20); // it -> 20 it is of type list::iterator but we
use auto
To insert new value 5 at position pointed by iterator,, we
use insert member function
lis.insert(it,5);
// Complexity O(1). lis={2,5,20,10};
We
can increment or decrement iterator to move to next or previous element in
list respectively.
it++;
// it -> 20
To erase an
element pointed by iterator(20) use.
lis.erase(it);
// Complexity O(1), lis={2,5,10}
Properties of list :
a. Fast insertion/removal
at any place in list. Time complexity O(1).
b. No
random access operator like vector/deque. So traversal is only possible using
iterators.
c. Slow search of elements. Time complexity
O(n). But this searching is comparitively slower than vector because of
locality of individual elements. In vector, elements
are stored in contiguous memory locations, and cache memory gives more cache
hits for contagious elements. On the other hand, list elements are stored
randomly in memory so it gives more cache misses and we keep swapping elements
in and out of cache.
d. Each node in list stores two extra
pointers one pointing to next element and one pointing to previous element.
Thus list occupies more memory and this also leads to higher cache
misses.
These were some of the mostly used sequence containers in STL. This
completes our discussion of Sequence containers. If you have any doubts.
please mention in the comments section.
Also check out other types of C++ STL containers if you missed them out :
1. Associative Containers
2. Unordered Containers
Thank you for your patience reading. If you enjoyed this post, I’d be very
grateful if you’d help it spread by emailing it to a friend, or sharing it on
Whatsapp or Facebook.
😇Happy Learning!!
I am a Member Technical at D.E. Shaw India Pvt. Ltd. CodingWithArt is a blog where you find tricks and solutions to challenging coding and development problems. I aim to build a universal tech platform for every enthusiast out there.