The Standard Template Library is an addition to the C++ language that provides a programmer a set of common classes and functions. It is made up of 3 main components:
A container is a data structure that holds objects that usually are the same data type. The order of the objects in the container depends upon the type of container.
There are 3 basic types of containers:
Every container class has:
A sequence container is one in which every object has a specific position in the container. There are 3 predefined sequence containers:
A vector is a data structure whose items are stored linearly and contiguously, and whose capacity can expand when needed.
Constructors:
| vector<data_type> vector_name; | constructs an empty vector object whose initial capacity and size are 0. |
| vector<data_type> vector_name(initial_capacity); | constructs a vector object that contains initial_capacity
values set to the default value: 0 for numbers, null for strings.
The objects starting capacity and size are initially both equal to
initial_capacity. vector<int> intVect(4); |
| vector<data_type> vector_name(initial_capacity, initial_value); | constructs a vector object that contains initial_capacity
values set to the value initial_value. The objects starting capacity
and size are initially both equal to initial_capacity. vector<int> intVect(4,1); |
Vector Methods:
| Method | Description |
| vector_name.capacity() | Returns the current capacity of vector_name. |
| vector_name.size() | Returns the number of values that are current stored in vector_name. |
| vector_name.max_size() | Returns the maximum number of values that vector_name can ever have. |
| vector_name.empty() |
Returns a boolean value to indicate if vector_name contains any values. |
| vector_name.push_back(value); | appends a copy of value to the end of vector_name and increases its size by 1. The capacity might change. |
| vector_name.pop_back(); | removes the last element in vector_name and decreases the size by 1. The capacity does not change. |
| vector_name.front(); | Returns a reference to the first element of vector_name. |
| vector_name.back(); | Returns a reference to the last element of vector_name. |
Vector Operators:
| subscript operator: vector_name[i] or vector_name.at(i) |
Returns the element of vector_name located at index is i. The index of the first element is always 0, and the index of the last is always vector_name.size() - 1. |
| assignment operator: vector1 = vector2; |
changes vector1 to a copy of vector2 after first destroying any previous value assigned to vector1. |
| equality operator: vector1 == vector2 |
the two operands are compared element by element. If they are identical, true is returned. Otherwise false is returned. |
| less than operator: vector1 < vector2 |
the two operands are compared element by element until a mismatch (if any) occurs. If the mismatched element in the left operand is smaller than the corresponding element in the right operand, true is returned. Otherwise false is returned. |
| greater than operator: vector1 > vector2 |
the two operands are compared element by element until a mismatch (if any) occurs. If the mismatched element in the left operand is larger than the corresponding element in the right operand, true is returned. Otherwise false is returned. |
A deque is a double-ended queue, which means that information can be inserted or removed from both ends. Like a vector, a deque is also implemented as a dynamic array.
Constructors:
| deque<data_type> deque_name; | constructs an empty deque object. |
| deque<data_type> deque_name(other_deque); | constructs a deque object that contains copies of the elements in other_deque |
| deque<data_type> deque_name(initial_size); | constructs a deque object with size equal to initial_size |
A few deque methods and operations:
| Method | Description |
| deque_name.push_front(value); | Inserts value at the beginning of deque_name |
| deque_name.pop_front(); | Removes the first element from deque_name |
| deque_name.front(); | Returns a reference to the first element of deque_name. |
| deque_name.back(); | Returns a reference to the last element of deque_name. |
deque_name[i] or deque_name.at(i) |
Returns the element of deque_name located at index is i. The index of the first element is always 0, and the index of the last is always deque_name.size() - 1. |
A list container is implemented as a doubly linked list.
Constructors:
| list<data_type> list_name; | constructs an empty list object. |
| list<data_type> list_name(other_list); | constructs a list object that contains copies of the elements in other_list |
| list<data_type> list_name(initial_size); | constructs a list object with size equal to initial_size |
A few list methods and operations:
| Method | Description |
| list_name.push_front(value); | Inserts value at the beginning of list_name |
| list_name.pop_front(); | Removes the first element from list_name |
| list_name.front(); | Returns a reference to the first element of list_name. |
| list_name.back(); | Returns a reference to the last element of list_name. |
list_name.remove(value) |
Removes all of the elements from list_name that are equal to value. |
list_name.unique() |
Removes the duplicates from consecutive elements. |
list_name.sort() |
Sorts the elements in list_name using a sort criteria of <. |
list_name.merge(other_list) |
Merges list_name and other_list into one list. The elements of list_name are sorted and other_list is empty. |
list_name.reverse() |
The elements of list_name are reversed. |
An associative container is one in which all of the elements are automatically sorted according to some ordering criteria. The default criteria is the relational operator less than (<).
These containers are implemented as binary search trees.
The predefined associative containers are:
A set container is a data structure that stores unique elements in sorted order. A multiset is the same as a set with the exception that duplicate elements are allowed.
Constructors:
| set/multiset<data_type> set_name; | constructs an empty set/multiset object. |
| set/multiset<data_type, sort_type> set_name; | constructs an empty set/multiset object and
specifies the order for the data. sort_type can be specified as greater<data_type>, greater_equal<data_type>, less<data_type>, less_equal<data_type>, equal_to<data_type>, not_equal_to<data_type> |
| set/multiset<data_type> set_name(other_set); | constructs a set/multiset object that contains copies of the elements in other_set |
| set/multiset<data_type, sort_type> set_name(other_set); | constructs a set/multiset object that contains copies
of the elements in other_set and specifies the order for the data (the sort
criteria must be the same for set_name and other_set. sort_type can be specified as greater<data_type>, greater_equal<data_type>, less<data_type>, less_equal<data_type>, equal_to<data_type>, not_equal_to<data_type> |
A few set/multiset methods and operations:
| Method | Description |
| set_name.insert(value); | Inserts value into set_name. In the case of a set, it also returns whether the insert operation was successful |
| set_name.insert(position, value); | Inserts value into set_name. position is an indicator of where to start the search for insert. The position where value is inserted is returned. |
| set_name.erase(value); | Deletes all the elements equal to value. The number of deleted elements is returned. |
| set_name.erase(position); | Deletes the element located at position. No value is returned. |
set_name.clear() |
Deletes all of the elements in set_name. |
Container Adapters are containers that are provided to accommodate special situations. The 3 container adapters are:
A priority queue is a collection of zero or more elements, each of which has an assigned priority or rank. The priority is what is used to determine which element is removed from the queue.
Constructors:
| priority_queue<data_type> queue_name; | constructs an empty priority_queue object. |
| priority_queue<data_type, container_type, sort_type> queue_name; | constructs an empty priority_queue object. The
data will be stored in whatever type of container is specified as
container_type. The priority is determined by sort_type. sort_type can be specified as greater<data_type>, greater_equal<data_type>, less<data_type>, less_equal<data_type>, equal_to<data_type>, not_equal_to<data_type> |
A few priority_queue methods and operations:
| Method | Description |
| queue_name.empty(); | Determines whether the queue is empty |
| queue_name.size(); | Returns the number of items that the queue is holding |
| queue_name.top(); | Returns a reference to the top element (the one with the highest priority) in the queue |
| queue_name.push(value); | Inserts a new element with the value "value" into the queue |
queue_name.pop() |
Removes the item of highest priority from the queue. |