The C++ Standard Template Library (STL) is a high-efficiency library built around templates. It packages many of the data structures and basic algorithms that show up constantly in programming, and its design is a strong example of reusable code.
The three pillars are containers, iterators, and algorithms.
Containers are data structures such as vector, list, stack, and queue. They are provided as templates, and iterators are used to reach the data inside them.
Iterators behave like special pointers. They give a way to access objects in a container, letting code move through container contents quickly and safely and use the algorithm templates.
Algorithms are often called generic algorithms. They are reusable algorithm templates that work on containers, and their open design also lets them operate directly on arrays or custom structs.
vector
vector is a container usually described as a vector. In practice it is a dynamically sized array: it supports random access, does not give O(1) insertion at arbitrary positions, and generally adds or removes elements at the end to keep efficiency. As with an ordinary array, indexing starts at 0.
Its advantages are a variable length, dynamic memory allocation, and a large set of encapsulated functions.
Declaration form:
vector <数据类型> 名称;
A declaration example:
#include<vector>
using namespace std;
struct Node{
int x,y;
};
vector <int> a;
vector <Node> b;
int main(){
return 0;
}
push_back adds an element at the end in O(1):
vector <int> a;
a.push_back(5);
A simple traversal can use array-style subscripts, starting from index 0:
#include<iostream>
#include<vector>
using namespace std;
vector <int> a;
int main(){
for(int i=1;i<=10;i++){
a.push_back(i);
}
for(int i=0;i<a.size();i++){
cout<<a[i]<<" ";
}
}
insert places an element at a given position. It works with begin() and end(), and costs O(n):
vector <int> a;
a.insert(a.begin()+3,666);//Insert 666 at the fourth position (index 3)
erase removes elements. It can remove a single element or a range. For a single element, the argument is a position, not a plain index and not a simple number: it is computed from begin() and end(). To delete the element at index 3, do not write erase(3); write a.erase(a.begin()+3). For a range, supply the start and end positions.
vector <int> a;
a.erase(a.begin()+5);//Delete the element at index 5, the sixth element
a.erase(a.begin()+2,a.end()-1);//Delete from index 2 through the second-to-last element
a.erase(a.begin()+2,a.begin()+4);//Delete elements from index 2 to 4
Common operations:
<table> <thead> <tr> <th>Function</th> <th>Purpose</th> </tr> </thead> <tbody> <tr> <td>a.push_back(x)</td>
<td>Add data x at the end</td>
</tr>
<tr>
<td>a.size()</td>
<td>Return the number of actual elements</td>
</tr>
<tr>
<td>a.empty()</td>
<td>Return a Boolean indicating whether the container is empty</td>
</tr>
<tr>
<td>a.clear()</td>
<td>Remove all data from the container</td>
</tr>
<tr>
<td>a.front()</td>
<td>Return the first data item</td>
</tr>
<tr>
<td>a.erase(pos)</td>
<td>Delete the data at position pos</td>
</tr>
<tr>
<td>a.erase(beg,end)</td>
<td>Delete data in the range beg to end</td>
</tr>
<tr>
<td>a.insert(pos,x)</td>
<td>Insert data x at position pos</td>
</tr>
<tr>
<td>a.pop_back()</td>
<td>Delete the last data item</td>
</tr>
<tr>
<td>a.resize(num)</td>
<td>Reset the container size</td>
</tr>
<tr>
<td>a.begin()</td>
<td>Return the address/iterator for the first element</td>
</tr>
<tr>
<td>a.end()</td>
<td>Return the address/iterator just past the last element</td>
</tr>
<tr>
<td>a.rbegin()</td>
<td>Return the reverse address/iterator for the last element</td>
</tr>
<tr>
<td>a.rend()</td>
<td>Return the reverse address/iterator for the first element</td>
</tr>
<tr>
<td>prev()</td>
<td>Return the previous address/iterator</td>
</tr>
<tr>
<td>next()</td>
<td>Return the next address/iterator</td>
</tr>
</tbody>
</table>
A common combination removes duplicates:
a.erase(unique(a.begin(),a.end()),a.end());//Remove duplicates
That idiom removes adjacent duplicates. When the whole container needs to be deduplicated, sort it first.
An iterator is much like a pointer for an STL container. It accesses and changes elements through their addresses, and * dereferences it. The syntax is:
vector<数据类型> ::iterator 自定义标识符;
Example:
#include<iostream>
#include<vector>
using namespace std;
vector<int> a;
int main(){
vector<int> :: iterator it;
for(int i=1;i<=10;i++){
a.push_back(i);
}
for(it=a.begin();it!=end();it++){
cout<<*it;
}
return 0;
}
Since C++11, auto can be used to declare the iterator type:
for(auto it=a.begin();it!=end();it++){
cout<<*it;
}
sort can order a vector:
vector<int> a;
sort(a.begin(),a.end(),cmp);
Two-dimensional vector
A two-dimensional vector is a vector whose elements are themselves vectors. Initialization needs care. Writing vector<vector<int> >a; produces a two-dimensional array of size 0: it cannot be indexed, and an inner row does not exist until it is created.
int N=5, M=6;
vector<vector<int>> a(N); //Define a 2D dynamic array with 5 rows
for(int i =0; i< a.size(); i++) { //The dynamic 2D array is 5 rows by 6 columns, all values 0
a[i].resize(M); //resize can reset the array size
}
queue
A queue is a special linear table that follows first in, first out (FIFO). A car wash lane is a simple picture: the car that enters first leaves first, and the last car in leaves last.
A queue deletes at the front and inserts at the back. Its data items are also called queue elements. Inserting an element is enqueueing; deleting one is dequeueing. Because insertion happens at one end and deletion at the other, only the earliest element can be removed first. That is why a queue is called a FIFO linear table.
Create a queue:
queue<数据类型> 队名
front()</td>
</tr>
<tr>
<td>Access the back element</td>
<td>back()</td>
</tr>
<tr>
<td>Insert an element at the back</td>
<td>push()</td>
</tr>
<tr>
<td>Pop the front</td>
<td>pop()</td>
</tr>
<tr>
<td>Check whether the queue is empty</td>
<td>empty()</td>
</tr>
<tr>
<td>Get the number of elements</td>
<td>size()</td>
</tr>
</tbody>
</table>
priority_queue
A priority queue is implemented as a heap. Unlike a regular queue, it only exposes the front information through top(), and after an insertion it automatically maintains order in O(log n).
Typical problems include greedy algorithms that need to maintain dynamically sorted elements.
Declaration form:
priority_queue<type,Container,Functional>;
type is the data type of each element. Container is the underlying container used to implement the priority queue, such as vector or queue. Functional is the comparison method.
A min-heap, with the smallest element at the front:
priority_queue <int,vector<int>,greater<int> > q;
A max-heap, with the largest element at the front:
priority_queue <int,vector<int>,less<int> > q;
If no comparison method is written, the default is a max-heap.
<table> <thead> <tr> <th>Operation</th> <th>Function</th> </tr> </thead> <tbody> <tr> <td>Access the front element</td> <td>top()</td>
</tr>
<tr>
<td>Check whether the queue is empty</td>
<td>empty()</td>
</tr>
<tr>
<td>Get the number of elements</td>
<td>size()</td>
</tr>
<tr>
<td>Insert an element at the back</td>
<td>push()</td>
</tr>
<tr>
<td>Pop the front</td>
<td>pop()</td>
</tr>
</tbody>
</table>
set
set is an associative container, also called a collection. It stores elements of one data type and can retrieve data from a collection. Every element value in a set is unique, the system automatically sorts the values, and the values themselves cannot be changed directly.
Definition with the set header:
set<类型> 对象名;
set<int> s;
Adding elements:
set<int> s;
s.insert(5);
s.insert(8);
s.insert(5);//Duplicate elements cannot be added, but no error is raised
A set is traversed with iterators, and it can be traversed forward or in reverse.
Forward traversal:
set<int> s;
for(auto it=s.begin();it!=s.end();it++) cout<<*it<<" ";
Reverse traversal:
set<int> s;
for(auto it=s.rbegin();it!=s.rend();it++) cout<<*it<<" ";
Common functions:
<table> <thead> <tr> <th>Function</th> <th>Purpose</th> </tr> </thead> <tbody> <tr> <td>s.clear()</td>
<td>Clear the container</td>
</tr>
<tr>
<td>s.empty()</td>
<td>Check whether it is empty</td>
</tr>
<tr>
<td>s.size()</td>
<td>Return the number of elements</td>
</tr>
<tr>
<td>s.erase(iterator)</td>
<td>Delete the element at the iterator position</td>
</tr>
<tr>
<td>s.erase(first,second)</td>
<td>Delete elements from iterator first to second</td>
</tr>
<tr>
<td>s.erase(key)</td>
<td>Delete this value</td>
</tr>
<tr>
<td>s.find(key)</td>
<td>Find an element; return its iterator position if found, otherwise end()</td>
</tr>
<tr>
<td>s.count(key)</td>
<td>Count occurrences of key</td>
</tr>
<tr>
<td>lower_bound()</td>
<td>Return the first element position (iterator) greater than or equal to the queried element</td>
</tr>
<tr>
<td>upper_bound()</td>
<td>Return the smallest position (iterator) greater than the queried element</td>
</tr>
</tbody>
</table>
Insertion and deletion both have O(log n) complexity.
map
map provides one-to-one data handling: the first part is the key, each key can appear only once, and the second part is the value for that key. This makes map a fast route for programming tasks that process one-to-one data. A map maps a key to a value. Because the operator is overloaded, a map feels like an advanced version of an array.
Without map, looking up the value for a key in an array of structs would require scanning the whole array, which is inefficient. Internally, map uses a red-black tree. When different key-value pairs are placed into a map, that structure automatically keeps all of them ordered by key.
For example, a map<string, int> month_name can represent a mapping from month names to month numbers, and month_name["July"]=7 assigns July the value 7. This also solves cases where bucket sort would need an impractically large array.
Declaration:
map<key_name,value_name> name;
map<long long,bool>vis;
map<string,int> a;
Inserting elements:
my_Map["a"]=1; // Most common method
my_Map.insert(map<string,int>::value_type("b",2));
my_Map.insert(pair<string,int>("c",3));
my_Map.insert(make_pair<string,int>("d",4));
Finding and retrieving a map element:
int x = my_Map["a"];//Most common
This works only when the key already has an instance in the map; otherwise it automatically inserts an instance with an initialized value. Therefore, use find to test whether a value exists:
auto it=a.find(key);
if(it != a.end()) {
string s = it->second;
}
If the key exists, find returns an iterator address corresponding to a pair. For a map<string,int>, that is a pair<string,int>, and the value can be read through the iterator with it->second. If the key does not exist, it returns map.end().
Traversal:
// Iterator
// You can define an iterator pointer it with map::iterator it; C++11 and later support the auto keyword
// it->first is the key, it->second is the value.
#include <bits/stdc++.h>
using namespace std;
int main() {
map<int, string> mapStudent;
mapStudent[1] = "student_one";
mapStudent[2] = "student_two";
mapStudent[3] = "student_three";
for (auto it = mapStudent.begin(); iter != mapStudent.end(); iter++) {
cout << iter->first << "" << iter->second << endl;
}
}
Common functions:
my_Map.size() //Return the number of elements
my_Map.empty() //Check whether it is empty
my_Map.clear() //Clear all elements