Standard Template Library (and adjacency list implementation)
December 23, 2016
Below is a short snippet of code giving examples of basic usage of the C++ STL for handling vectors (arrays), sorting, and graphs (adjacency matrix, adjacency list).
# include<iostream>
# include<vector>
# include<algorithm>
# include<utility>
using namespace std;
int NMAX = 5000; // constraints on N
int MMAX = 100000; // constraints on M
vector <int> vv; // vector
vv.resize(n); // resizing since you get to know n during run-time
for (i = 0; i < n; i++) {
cin >> vv[i];
}
sort(vv.begin(), vv.end()); // sort vv from begin to end
vector < pair <int, int> > pairs(n); // vector of pairs
int a, b;
for (i = 0; i < n; i++) {
cin >> pairs[i].first >> pairs[i].second;
}
sort(pairs.begin(), pairs.end()); // sort still works
vector <int> nodes(NMAX); // vector with NMAX elements
vector <int> nodes(NMAX, 0); // vector with NMAX elements initialized to 0
int adjacency_matrix[NMAX][NMAX]; // 2D matrix NMAX x NMAX
for (int i = 0; i < m; i++) {
cin >> a >> b;
adjacency_matrix[a][b] = 1;
adjacency_matrix[b][a] = 1; // only if graph is undirected
}
// neighbors of node using adjacency matrix
// ( good if dense graph, for sparse graph use adjacency list )
for (int i = 0; i < n; i++) {
if (adjacency_matrix[node][i] == 1) {
// do stuff
}
}
// is x neighbor of y ? ( good )
if ( adjacency_matrix[x][y] == 1 ) {
// do stuff
}
vector <int> adjacency_list [NMAX]; // NMAX vectors
for (int i = 0; i < m; m++) {
cin >> a >> b;
adjacency_list[a].push_back(b);
adjacency_list[b].push_back(a); // only if graph is undirected
}
// is x neighbor of y ? ( bad, adjacency matrix is faster )
for (int i = 0; i < adjacency_list[node].size() ; i++) {
if (adjacency_list[x][i] == j) {
// do stuff
}
}
// neighbors of node using adjacency list ( good )
for (int i = 0; i < adjacency_list[node].size() ; i++) {
int neighbor = adjacency_list[node][i];
// do stuff
}
// adjacency matrix using vectors.
// overkill. not recommended. use 2D arrays
vector< vector<int> > adjacency_matrix (N, vector<int>(N, 0)) ;
An in-depth STL tutorial can be found on TopCoder (it is pretty advanced though): STL part 1, STL part 2. Also, here are a couple of popular websites if you want to check what operations each thing in C++ STL supports: Learn C++, The C++ Resources Network.
Feel free to ask questions, and post additional STL usage you have found useful while solving problems. And obviously, do let me know if you notice any errors above.