The Standard Template Library (STL) is a programmer's dream. It offers efficient ways to:
and is designed for maximum extensibility. Once a programmer has gotten over the initial syntax hurdles, they quickly learn to appreciate the STL's sheer power and flexibility.
Source: CS106L-Stanford
Containers: a collection of container classes. For example:
map:
an associative collection of key/value pairs
vector:
a growing list of elements.
Iterators: objects that view and modify ranges of stored data. Each STL container exports iterators. Iterators have a common interface, allowing the programmer to write code that operates on data stored in arbitrary containers.
Algorithms: functions that operate over ranges of data specified by iterators.
Adapters: objects which transform an object from one form into another. For instance:
stack
adapter transforms a regular vector or list into a LIFO (Last In First Out) container.
istream_iterator
transforms a standard C++ stream inot an STL iterator.
Functions: facilities for creating and modifying functions at runtime.
Allocators: allow clients of the container classes to customize how memory is allocated and deallocated, either for diagnostic or performance reasons.
A std::vector
is an object that represents a sequence of elements. The elements in a vector are indexed, meaning that they can have a well-defined position in the sequence.
#include <iostream>
#include <vector> // Necessary to use vector
#include <string>
#include <sstream>
// Create a vector containing integers
std::vector<int> v = {7, 10, 15, 8, 98, 0};
Add two more integers to vector using push_back()
v.push_back(45);
v.push_back(56);
Helper function to iterate and print values of vector
void PrintVector(std::vector<int>& v){
for(int n : v){
std::cout << n << ' ';
}
std::cout << std::endl;
}
PrintVector(v)
7 10 15 8 98 0 45 56
The storage of the vector is handled automatically, being expanded and contracted as needed. Vectors usually occupy more space than static arrays, because more memory is allocated to handle future growth. This way a vector does not need to reallocate each time an element is inserted, but only when the additional memory is exhausted.
Grow the vector, setting new elements to 0
v.resize(10);
PrintVector(v)
7 10 15 8 98 0 45 56 0 0
The total amount of allocated memory can be queried using capacity()
function. Extra memory can be returned to the system via a call to shrink_to_fit()
capacity()
: returns the number of element that can be held in currently allocated storage
v.capacity()
(unsigned long) 12
shrink_to_fit()
: reduces memory usage by freeing unused memory
v.shrink_to_fit()
v.capacity()
(unsigned long) 10
resize()
: changes the number of elements stored. E.g; Grow the vector, setting new elements to 100**
v.resize(13, 100);
PrintVector(v);
7 10 15 8 98 0 45 56 0 0 100 100 100
v.capacity()
(unsigned long) 20
pop_back()
: removes the last element
v.pop_back();
PrintVector(v);
7 10 15 8 98 0 45 56 0 0 100 100
NOTE: for detailed information about std::vector
, check out the C++ reference.
?std::deque
There are several aspects of the vector that can be troublesome in certain applications. In particular, the vector is only designed to grow in one direction; calling push_back()
inserts elements at the end of the vector, and resize()
always appends elements to the end.
A std:deque
is an indexed sequence container that allows fast insertion and deletion at both its beginning and its end. As opposed to std:vector
, the elements of a deque are not stored contiguously: typical implementations use a sequence of individually allocated fixed-size arrays, with additional bookkeeping, which means indexed access to deque must perform two pointer dereferences, compared to vector's indexed access which performs only one.
#include <iostream>
#include <deque>
Create a deque (pronounced "deck") containing integers
std::deque<int> d = {45, 48, 40, 79};
void PrintDeque(std::deque<int>& d){
for(int n : d){
std::cout << n << ' ';
}
std::cout << std::endl;
}
PrintDeque(d);
45 48 40 79
Add an integer to the beginning and end of the queue
d.push_front(13);
d.push_back(25);
PrintDeque(d);
13 45 48 40 79 25
A deque can do everything a vector can do and also unlike a vector, it is possible (and fast) to push_front
and pop_front
NOTE: for detailed information about std::deque
, check out the C++ reference or just type ?std::queue
in a notebook cell to get live documentation.
How can we implement stack and queue using the containers we have?
Stack is a type of container adapters with LIFO (Last In First Out) or FILO (First in, Last Out) data structure, where a new element is added at one end and (top) an element is removed from that end only.
Stack: just limit the functionality of a vector/deque to only allow push_back
and pop_back
.
The functions associated with stack are:
empty()
-- Returns whether the stack is emptysize()
-- Returns the size of the stacktop()
-- Returns a reference to the top most element of the stackpush(g)
-- Adds the element 'g' at the top of the stackpop()
-- Deletes the top most element of the stack#include <stack>
Create a stack of integers
std::stack<int> s;
Helper function to show the stack
void ShowStack(std::stack<int> mystack){
std::stack<int> s = mystack;
while (!s.empty()){
std::cout << '\t' << s.top();
s.pop();
}
std::cout << std::endl;
}
ShowStack(s)
Push some elements onto the stack
s.push(10);
s.push(30);
s.push(20);
s.push(5);
ShowStack(s)
5 20 30 10
** Get stack size**
s.size()
(unsigned long) 4
Get the top of the stack
s.top()
(int) 5
Pop top of the stack
s.pop();
ShowStack(s)
20 30 10
Queue is a type of container adaptors which operate in a first in first out (FIFO) type of arrangement. Elements are inserted at the back (end) and are deleted from the front.
The functions supported by queue are:
empty()
-- Returns whether the queue is emptysize()
-- Returns the size of the queuefront()
-- Returns a reference to the first element of the queue.back()
-- Returns a reference to the last element of the queuepush(g)
-- Adds the element g
at the end of the queuepop()
-- Deletes the first element of the queue.#include <queue>
Create an empty queue
std::queue<int> q;
Helper function to show content of the queue
void ShowQueue(std::queue<int> myqueue){
std::queue<int> q = myqueue;
while (!q.empty()){
std::cout << '\t' << q.front();
q.pop();
}
std::cout << std::endl;
}
ShowQueue(q)
Add some elements to the queue
q.push(10);
q.push(20);
ShowQueue(q)
10 20
Get queue size
q.size()
(unsigned long) 2
Get front of the queue
q.front()
(int) 10
Get back of the queue
q.back()
(int) 20
Pop front of the queue
q.pop()
ShowQueue(q)
20