By sharpc and udpn. Code samples by Evil_Stivie.
This is theoretical STL minimum for competitive programmers, a subset of features of C++ standard library useful for solving algorithmic problems. Topics are grouped mostly by STL header file name and context of use. Almost all names you might encounter in this guide are in std namespace. For it, and only for it, you should add below all #includes:
using namespace std;Input/output streams are preferred to C functions, because they need no format string, and are free from common mistakes made in it.
int n = 123123123;
char ch = 'a' + 3;
long long ll = 92233720368547758LL;
cout << n << " " << ch << " " << ll << endl; // 123123123 d 92233720368547758Similarly, input requires neither format strings nor pointers.
int k;
cin >> k;
cout << k << endl;Some problems have no exact input size, and the input is terminated with EOF (run.exe<file or Ctrl-Z in stdin). Overloaded operator >> for streams returs istream& that can be implicitly converted to bool. The resulting value is !fail(), and fail() fail returns true trying to read after EOF.
int k, sum = 0;
while (cin >> k) { // reads until EOF
sum += k;
}
cout << sum << endl; // sum of numbers on input until EOFSome problems ask to input string until newline character is encountered. Naïve string s; cin >> s; inputs string to first space-like character. This is done with getline, that returns istream& too with same same handling of EOF. Terminating newline character is not added to string variable.
aa bb
cc ddddd^Zstring s1, s2;
while (getline(cin, s1)) { // reads until EOF
s2 += s1;
}
cout << s2.length() << endl; // 13It should be added, that cin >> var; doesn't consume newline character from input stream, thus it might be needed to do one more getline call to consume it explicitly.
stringstream ss("5\na b c");
int n;
string s;
ss >> n;
getline(ss, s); // consumes newline after 5
getline(ss, s); // reads second line
cout << n << " : " << s << endl; // 5 : a b cThe header <iomanip> contains formatting related features, which mostly replace format strings of printf.
Manipulators setprecision and fixed set precision for all subsequent << calls for floating-point numbers, by setting number of all digits or digits after the point correspondingly.
double n = 3.141592653;
cout << setprecision(5) << n << endl; // 3.1416
cout << fixed << setprecision(5) << n << endl; // 3.14159A pair setw and setfill set how to pad subsequent number or string, and which character to use for that padding.
cout << setw(8) << "hello" << endl; // " hello"
cout << setfill('0') << setw(3) << 7 << endl; // "007"Manilpulators hex and dec output subsequent numbers in hexadecimal and decimal numeral systems.
int n;
stringstream("2A") >> hex >> n;
cout << dec << n << endl; // 42
cout << hex << 42 << endl; // 2aBy defautlt cin inputs several chars, skipping all space-like characters. Manipulators noskipws/skipws switch this behavior.
char s1, s2, s3;
stringstream("a b c") >> s1 >> s2 >> s3;
cout << s1 << ", " << s2 << ", " << s3 << endl; // a, b, c
stringstream("a b c") >> noskipws >> s1 >> s2 >> s3;
cout << s1 << "," << s2 << "," << s3 << endl; // a, ,bInput/output streams were developed in a way to extensively expand and modify their state. Ensuing overhead can make solutions hit time limits on online judges. In such cases there are magic words of
cin.tie(0);
cin.sync_with_stdio(false);for ample inputs, and another one, with cout, for ample outputs.
Usually, in competitive programming it's expected to use << endl to put newline character to the output. It's equivalent to << '\n' << flush. Manipulator flush flushes output buffer, and in case of large number of rows this makes code ridiculously slow. In such case, all endl should be replaced by "\n", with only one endl or flush left at the end of the program.
If this is not enough yet to squeeze iostreams into time limit (if it's really the case, and only one), it's fine to use functions from C.
int n;
long long n_l;
double d;
float f;
char s[5];
char ch;
scanf("%d %lld %lf %f %s %c", &n, &n_l, &d, &f, &s, &ch);
printf("%d %lld %lf %f %s %c", n, n_l, d, f, s, ch);Instead of arrays C++ programs should always use sequence container vector. Its size is set as constructor argument. It's possible to set different default value (other than 0, "", false and empty vector) for items with second constructor argument.
vector<int> v(5); // {0,0,0,0,0}
vector<vector<int>> v(2, vector<int>(3, -1)); // {{-1,-1,-1}, {-1,-1,-1}}For size and default value:
vector<double> v;
v.assign(4, 1.0); // {1.0, 1.0, 1.0, 1.0}Vector can be initialized with initialization lists or a pair of iterators.
vector<int> v{1, 2, 3, 4, 5};
vector<int> v2(v.begin() + 2, v.begin() + 4); // {3, 4}Access to item is same as for an array.
cout << v2[0]; // 3Vectors have almost same performance as arrays, thus in release build they don't check for array boundaries. There is a way to access an item with explicit array boundary check, and throw an exception in case of boundary violation:
cout << v2.at(2); // Exception: out_of_rangeClean (don't confuse with emptyness check, v.empty() (are there people, that do?)), works for any container.
v.clear();There are several ways to iterate over container (examples are for vector):
vector<int> v{1, 2, 3}
// By index
for (int i = 0; i < v.size(); ++i) {
cout << v[i] << endl;
}
// By iterator
// auto = vector<int>::iterator
for (auto it = v.begin(); it != v.end(); ++it) {
cout << *it << endl;
}
// Recommended: C++11 range-based for
for (int item : v) {
cout << item << endl;
}Containers can be traversed in reverse order:
// auto = vector<int>::reverse_iterator
for (auto it = v.rbegin(); it != v.rend(); ++it) {
cout << *it << endl;
}Vector is a dynamic array with an ability to append to the end new elements (push_back) and resize (size), both in amortized O(1) time. To achieve this complexity, vector allocates more memory than it's strictly required (the exact amount is available from capacity() method call result). When the memory limit is reached (.size() == .capacity()) it allocates 1.5-2 times more memory (the multiplier is for MSVC), and copies all items. Memory reallocation invalidates all previously created iterators for that vector, which might lead to errors.
vector<int> v;
for (int i = 0; i < 16; ++i) {
v.push_back(123);
cout << v.size() << "-" << v.capacity() << " ";
}
// 1-1 2-2 3-3 4-4 5-6 6-6 7-9 8-9 9-9 10-13 11-13 12-13 13-13 14-19 15-19 16-19If an item to be appended has to be constructed first (for example, a pair), constructor and push_back could be merged into single call to avoid extraneous calls to copy constructor.
vector<pair<int, string>> v;
// Instead of v.push_back(make_pair(5, "hello"));
v.emplace_back(5, "hello");In addition to appending to the end, it's possible to delete items from the end.
vector<int> v{1, 2, 3};
v.pop_back(); // {1, 2}First and last item are accessible by reference returned by front() and back() method calls correspondingly.
vector<int> v{2, 4, 8, 16, 32};
cout << v.front() << endl; // 2
cout << v.back() << endl; // 32
v.back() = -1; // {2, 4, 8, 16, -1}It's possible to insert a value or a segment (defined by iterator pair) after a position given by an iterator. All elements subsequent to iterator before the insertion ({2, 3} and {6, 2, 3} in the example) are copied in O(N) time.
vector<int> v{1, 2, 3};
vector<int> w{5, 6};
v.insert(v.begin() + 1, w.begin(), w.end()); // {1, 5, 6, 2, 3}
v.insert(v.begin() + 2, 8); // {1, 5, 8, 6, 2, 3}Existing vector can be resized.
vector<int> v{1, 2, 3};
v.resize(5, -1); // {1, 2, 3, -1, -1}Its capacity can also be changed to avoid time-consuming memory reallocations in case it's upper bound on item quantity is known in advance.
cout << v.size() << " " << v.capacity() << endl; // 5 5
v.reserve(1000);
cout << v.size() << " " << v.capacity() << endl; // 5 1000While reserve can be used only to increase capacity, vector can be recreated with same item values and minimal capacity in one line (so called "swap hack"). It might be useful if momentary sizes of vectors are bigger than sizes when computations on them are finished, especially in case there are vector<vector<...>>s somewhere in the code.
v.swap(vector<int>(v));
cout << v.size() << " " << v.capacity() << endl; // 5 5In C++ you can use .shrink_to_fit() to same effect.
Vector is specialized for bool, so that each element takes only 1 bit of memory. It saves memory, but operations on such vector are slower, and it's impossible to get a pointer to item. If increased cost of operations is not desired, vector<int> (or vector of other integral numeric type) can be used. Boolean operators will cast numeric values to boolean, so barely any change in code is required.
Instead of zero-terminated C-strings C++ programs should always use string.
string s = "hello, world!";
char c = s[6]; // same as s.at(6) for vectors
cout << s << endl;
s += c; s += s; // Concatenation: "hello, world! hello, world! "Constructor for string — just like vector's — takes number of characters and character to repeat.
cout << string(5, '!') << endl; // "!!!!!"For C compatibility reasons string literal "a" is char const *, and + doesn't concanate them.
string s = "AaBb";
// s += "C" + "c"; // results in compile error
s += string("C") + "c"; // correct
cout << s << endl; // AaBbCcC++14 now has another literal to construct strings.
string s = "a"s + "b";Same as vector, string has methods assign, clear, empty, begin, end, rbegin, rend, size, resize, capacity, reserve. Also there is an alias for size: length.
string t = "Hedgehog is gonna get out from that jail";
cout << t.size() << endl; // 40
cout << t.length() << endl; // 40Substring (0-based first character, length):
string t = "abcdef";
cout << t.substr(2, 3) << endl; // cdeSame as vector, string has methods push_back, pop_back, front, back, insert.
string s;
for (int i = 0; i < 10; ++i) {
s.push_back('a' + i);
}
cout << s << endl; // abcdefghijNumeric types can be cast to string with to_string, and vice versa with stoi/stoll/stoull/stof/stod.
double pi = 3.14159265;
string s = "Pi = " + to_string(pi);
cout << s << endl; // Pi = 3.141593
s = "12345678901";
// cout << stoi(s) << endl; // Exception: out_of_range
cout << stoll(s) << endl; // 12345678901It's possible to find substrings in a string (using a naïve search algorithm with O(NM) complexity). Optional second argument is offset to the position to start search. If there is no such substring, return value is string::npos.
string s = "hello, world!";
// 0123456789012
cout << s.find("wo") << endl; // 7
cout << boolalpha << (s.find("hi") == string::npos) << endl; // trueSearch from the end (the string to be found should be no more to the right than offset):
string s = "hello, world!";
// 0123456789012
cout << s.rfind("l", 9) << endl; // 3This loop finds all occurences of substring.
size_t off = 0;
while (true) {
off = s.find("l", off);
if (off == string::npos) { break; }
cout << off << endl; // 2 3 10
off += 1;
}Besides substrings, it's possible to find characters from a set of characters with find_first_of method. Similarly, find_first_not_of finds characters not in set, and find_last_of and find_last_not_of do the same from the end of the string.
string s = "hello, world!";
// 0123456789012
cout << s.find_last_of("aeiou") << endl; // last vower is at position 8String stream works similarly to cin/cout, but instead of working with stdin/stdout it modifies an internal string.
stringstream ss;
ss << 2 << " " << 4 << " " << 8;
string s = ss.str(); // read internal string
cout << s << endl; // "2 4 8"
stringstream ss("1 2 3"); // initialize internal string
int n1, n2, n3;
ss >> n1 >> n2 >> n3;
cout << n1 << " " << n2 << " " << n3 << endl; // 1 2 3These character classes are most useful in competitive programming. Lists of characters are only of those that are in 0-127 code range.
isalpha— A-Za-zisalnum— 0-9A-Za-zisblank— \t and spaceisdigit— 0-9islower— a-zisupper— A-Zisxdigit— 0-9A-Fa-f
Expectedly transform A-Z into a-z and vice versa. To transform whole string, transform from <algorithm> should be used.
string s = "where is STL?!";
transform(s.begin(), s.end(), s.begin(), toupper);
cout << s << endl; // WHERE IS STL?!Deque is similar to vector, but allows appends and removals from both ends in O(1) time. It's implemented by circular buffer of dynamic size with pointers to segments of items of equal length.
deque<int> d;
d.push_back(3);
d.push_front(2);
d.push_back(4);
d.push_front(1);
d.push_back(5);
for (int i = 0; i < d.size(); ++i) {
cout << d[i] << " ";
}
cout << endl; // 1 2 3 4 5There are also std::stack and std::queue built on top of deque. They are just wrappers on deque without some of the methods.
Priority queue allows insertions in O(logN) time, search for biggest element in O(1), and its removal in O(logN). It's implemented as binary heap on vector that supports A[i] >= A[2*i + 1] && A[i] >= A[2*i + 2] invariant for all i.
priority_queue<int> pq;
for (int i = 0; i < 5; ++i) {
pq.push(i);
}
while (pq.size()) {
int item = pq.top();
cout << item << " ";
pq.pop();
}
cout << endl; // 4 3 2 1 0Usually priority queue is used for pairs of (priority, task), where it got its name from
priority_queue<pair<int, char>> pq;
for (int i = 0; i < 5; ++i) {
pq.emplace(i, 'a' + i);
}
cout << pq.top().second << endl; // eTwo or more associated values can be joined into a pair or a tuple. Elements of a pair are accessible through fields first and second.
pair<int, int> p(1, 2);
cout << p.first << " " << p.second << endl; // 1 2
p = make_pair(14, 28);
cout << p.first << " " << p.second << endl; // 14 28Elements of tuple are accessible through a function template get:
tuple<int, int, int> tp(1, 2, 3);
cout << get<0>(tp) + get<1>(tp) + get<2>(tp) << endl; // 6
tp = make_tuple(14, 28, 42);
cout << get<0>(tp) + get<1>(tp) + get<2>(tp) << endl; // 84For sequence containers (vector, string, deque, pair, tuple) STL defines operator <, that compares them lexicographically (first by first element, in case they are equal by second, etc), so they can be compared, and containers that stores them can be sorted.
Comparison of vectors:
vector<int> box1(3), box2(3);
for (int i = 0; i < 3; ++i) { cin >> box1[i]; }
for (int i = 0; i < 3; ++i) { cin >> box2[i]; }
sort(box1.begin(), box1.end());
sort(box2.begin(), box2.end());
if (box1 <= box2) {
cout << "You can put the first box into the second one" << endl;
} else if (box2 <= box1) {
cout << "You can put the second box into the first one" << endl;
} else {
cout << "You can't put one box into another" << endl;
}Comparison of strings:
cout << boolalpha << (string("a") < string("abcd")) << endl; // true
cout << boolalpha << (string("a") < string("ABCD")) << endl; // falseComparison of pairs:
cout << boolalpha << (make_pair(1, 2) < make_pair(1, 3)) << endl; // trueSTL has container map (associative array, dictionary) that associates to a key of any type with < operator defined a value of any type. It's implemented as an almost balanced binary red-black tree, so that accessing an element by key takes O(logN) comparisons, as well as insertion or removal of an element. Red-black tree is ordered by keys, and all keys are unique.
Call to [] operator automatically creates a value for given key with default constructor for value type if there was no value for that key previously. Thus for const map<..., ...> instead of [] operator an at() method should be used that throws an out_of_range exception if the key doesn't exist.
Iteration on map gives pair<TKey, TValue>.
map<char, int> m;
for (char ch : string("abacaba")) {
m[ch] += 1;
}
cout << m.size() << endl; // 7
for (auto kv : m) {
cout << kv.first << "-" << kv.second << " ";
} // a-4 b-2 c-1Note that keys are iterated over in ascending order.
A check that m.find(key) (returns iterator) is not equal to m.end() succeeds if a value for a given key is in a map. Another way to do the check is count method call.
map<char, int> m{{'a', 1}, {'c', 1}, {'b', 0}, {'d', 2}, {'f', 1}};
cout << m.count('a') << " " << m.count('e') << endl; // 1 0Elements are removed by erase method, either by key, iterator or two-iterator segment.
m.erase('c'); // {'a': 1, 'b': 0, 'd': 2, 'f': 1}
m.erase(m.find('f')); // {'a': 1, 'b': 0, 'd': 2}Container set is similar to map, but stores no values, and, consequently, no []. Insertion of new values is done with insert that takes an element or a segment given by two iterators.
set<int> s{1, 2, 3, 5, 6};
cout << s.count(1) << " " << s.count(4) << endl; // 1 0
cout << s.size() << endl; // 5
s.insert(2);
cout << s.size() << endl; // 5
s.insert(0);
cout << s.size() << endl; // 6
vector<int> add{6, 7, 8};
s.insert(add.begin(), add.end());
s.erase(7);
for (int item : s) {
cout << item << " "; // 0 1 2 3 5 6 8
}STL implements open hash-table that allows inserting of keys in O(1) amortized time. Its implementation relies on std::list that stores all inserted elements in the order of container traversal, and pointers into this list to first and last element for each of b = 2n buckets in a vector of 2 * b length. Number of possibly stored items in buckets is kept no less than number of items. When hash-table capacity is exhausted, number of buckets is increased to be twice higher (8 times higher in MSVC for small hash-tables) and hashes for all elements are recomputed with std::hash.
Containers unordered_map and unordered_set are mostly similar to map and set, but keys are sorted by hash % u.bucket_count().
unordered_set<char> u;
for (int i = 0; i < 26; ++i) {
u.insert('a' + i);
}
for (char ch : u) {
cout << ch;
} // iabcdefghjklmnopqrstuvwxyzFunction hash is implemented for most data types as "exclusive or" with next byte and multiplication, iterated. But for some useful types like tuples, hash has to be implemented by user:
namespace std {
template<typename T1, typename T2> struct hash<pair<T1, T2>> {
size_t operator () (pair<T1, T2> const& arg) const {
return hash<T1>()(arg.first) ^ hash<T2>()(arg.second);
}
};
}STL implements some simple and often used generic algorithms. "Generic" they are, because there pay no difference to the type of container, because they take just a pair of iterators.
Minimum, maximum, both of them:
cout << min(123, 456) << " " << min('a', 'b') << endl; // 123 a
cout << max(2.5, 2.6) << " " << max('k', 'o') << endl; // 2.6 o
pair<int, int> res = minmax({ 2, 4, 8, 16, 32 });
cout << res.first << ' ' << res.second << endl; // 2 32Maximum of a sequence (min_element for minimum), returns an iterator:
vector<int> v{1, 2, 3, 4, 5};
cout << max_element(v.begin(), v.end()) - v.begin() << endl; // index 4
cout << *max_element(v.begin(), v.end()) << endl; // value 5A sort:
vector<int> v{2342, 1231, 87978, 123, 789};
sort(v.begin(), v.end()); // 123 789 1231 2342 87978A reverse sort:
sort(v.rbegin(), v.rend()); // 87978 2342 1231 789 123A sort with comparison predicate:
vector<int> v{-2, -1, 0, 1, 2, 3};
sort(v.begin(), v.end(), [](int a, int b) {
return abs(a) < abs(b);
}); // 0 -1 1 -2 2 3A sort with lexicographical comparison predicate (tie creates a tuple of references); an example sorts characters first by frequency in descending order, then by character code in ascending order:
string s = "hello, world!";
map<char, int> m;
for (char ch : s) { m[ch] += 1; }
vector<pair<char, int>> v(m.begin(), m.end());
sort(v.begin(), v.end(), [](pair<char, int> const& a, pair<char, int> const& b) {
return tie(-a.second, a.first) < tie(-b.second, b.first);
}); // {{'l', 3}, {'o', 2}, {' ', 1}, {'!', 1}, {',', 1}, {'d', 1}, {'e', 1}, {'h', 1}, {'r', 1}, {'w', 1}}Stable sort doesn't change initial order for values that are equal, [comparison predicate]-wise.
vector<pair<char, int>> v(m.rbegin(), m.rend());
stable_sort(v.begin(), v.end(), [](pair<char, int> const& a, pair<char, int> const& b) {
return -a.second < -b.second;
}); // {{'l', 3}, {'o', 2}, {'w', 1}, {'r', 1}, {'h', 1}, {'e', 1}, {'d', 1}, {',', 1}, {'!', 1}, {' ', 1}}Check that the sequence is already sorted:
vector<int> v{1, 2, 3, 1};
cout << boolalpha << is_sorted(v.begin(), v.end()) << endl; // false
sort(v.begin(), v.end());
cout << boolalpha << is_sorted(v.begin(), v.end()) << endl; // trueFunction next_permutation iterates over permutations (returning false if current permutation is lexicographically the biggest). In competitive programming usually permutations of indices get iterated over. In this case source sequence is usually created with iota. If not, almost all the time it's a lexicographically smallest permutation of values, that is easily computed by sort.
vector<int> v(4);
iota(v.begin(), v.end(), 1);
do {
cout << v[0] << v[1] << v[2] << v[3] << "; ";
} while (next_permutation(v.begin(), v.end()));
// 1234; 1243; 1324; 1342; 1423; 1432; 2134; 2143; 2314; 2341; 2413; 2431; 3124; 3142; 3214; 3241; 3412; 3421; 4123; 4132; 4213; 4231; 4312; 4321;Generic algorithms can move elements, but cannot remove them. The container itself is responsible for that. Function unique searches for multiple (second and so on) sequent (next to each other) occurences of items, and moves them to the end of container. In order for unique to return a sequence of only unique items, sequence has to be sorted first. Functions remove/remove_if move a certain value or values that pass a check by predicate to the end of container. They return iterator to first moved item, that can be used to remove all the items between it and the end of container with erase.
vector<int> v = {1, 1, 2, 3, 3, 3, 1, 1, 2, 2};
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end()); // 1 2 3
v.erase(remove_if(v.begin(), v.end(), [](int x) {
return x % 2 == 0;
}), v.end()); // 1 3Reverse the order of items in sequence container:
string s = "desserts";
reverse(s.begin(), s.end());
cout << s << endl; // stressedA whole range of functions are intended to fill containers with items from some source. Every time you use memset, a kitten dies. Functions back_inserter and inserter create an insertion iterator, that calls push_back or insert correspondingly on a container passed to their constructors as argument when it's dereferenced and assigned a value.
vector<int> a(5); // {0, 0, 0, 0, 0}
fill(a.begin() + 1, a.end(), -1); // {0, -1, -1, -1, -1}
copy(a.begin(), a.begin() + 2, a.begin() + 2); // {0, -1, 0, -1, -1}
vector<int> b;
copy_n(a.rbegin(), 3, back_inserter(b)); // {-1, -1, 0}STL has an iterator class (that only supports reading and writing to it) for input and output streams. Default constructor of istream_iterator allows to read until EOF.
stringstream ss("5\n1 2 3 4 5\n1 1 2 3 5");
int n;
ss >> n;
vector<int> v, w;
copy_n(istream_iterator<int>(ss), n, back_inserter(v)); // v = {1, 2, 3, 4, 5}
copy(istream_iterator<int>(ss), istream_iterator<int>(), back_inserter(w)); // w = {1, 1, 2, 3, 5}
copy(w.begin(), w.end(), ostream_iterator<int>(cout, ", ")); cout << endl; // 1, 1, 2, 3, 5, On a rare occasion a peculiar ambiguity is met (so called "most vexing parse") when a programmer thinks, that w is a definition of variable with 2 arguments passed into constructors, but compiler thinks it's a function declaration.
vector<int> w(istream_iterator<int>(ss), istream_iterator<int>());MSVC will warn something in the lines of
warning C4930: prototyped function not called (was a variable definition intended?)Just add a pair of (seemingly extraneous) brackets around one of the arguments to convince compiler that it's really a variable definition.
stringstream ss("1 2 3 4 5");
vector<int> w((istream_iterator<int>(ss)), istream_iterator<int>());
copy(w.begin(), w.end(), ostream_iterator<int>(cout, "_")); // 1_2_3_4_5_Functions find/find_if find iterator to first value equal to the given or satisfying a given predicate. Functions count/count_if count, how many of such values there are in total.
vector<int> v{0, 1, 1, 2, 3, 5, 8, 13, 21, 34};
cout << find(v.begin(), v.end(), 8) - v.begin() << endl; // 6
cout << *find_if(v.begin(), v.end(), [](int i) { return i > 10; }) << endl; // 13
cout << count(v.begin(), v.end(), 1) << endl; // 2
cout << count_if(v.begin(), v.end(), [](int i) { return i % 2 == 0; }) << endl; // 4Function search searches for sequences of values (unlike string::find that searches for only one), similar to a search of substring in a string.
vector<int> v{3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9, 3, 2, 3, 8, 4, 6};
auto seq = {3, 5};
cout << search(v.begin(), v.end(), seq.begin(), seq.end()) - v.begin() << endl; // 9Set-theoretic operations are done on sorted segments (usually on vectors due to smaller overhead).
Inclusion:
vector<int> v1{2, 8, 16, 32};
vector<int> v2{2, 4, 8};
vector<int> v3{8, 16};
cout << boolalpha << includes(v1.begin(), v1.end(), v2.begin(), v2.end()); // false
cout << boolalpha << includes(v1.begin(), v1.end(), v3.begin(), v3.end()); // trueUnion, intersection, difference and symmetric difference (require one iterator to mark the place to store their result):
vector<int> v1{10, 20, 30, 40};
vector<int> v2{40, 50, 60, 70};
vector<int> res0111, res0001, res0100, res0110;
set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), back_inserter(res0111));
// 10 20 30 40 50 60 70
set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), back_inserter(res0001));
// 40
set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), back_inserter(res0100));
// 10 20 30
set_symmetric_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), back_inserter(res0110));
// 10 20 30 50 60 70Integer binary search finds in ascending-sorted segment (for vectors — in O(logN) time) a segment [begin, end[, containing this value.
vector<int> v{1, 1, 1, 1, 2, 2, 2, 3, 3, 4};
cout << "2 in [" <<
lower_bound(v.begin(), v.end(), 2) - v.begin() << "; " <<
upper_bound(v.begin(), v.end(), 2) - v.begin() << "[" << endl; // 2 in [4; 7[If it's desirable to compute "items" on the fly by "index", custom iterator class can be used.
struct int_iterator : iterator<random_access_iterator_tag, int> {
int n;
function<int(int)> pred;
int_iterator(int n, function<int(int)> pred) : n(n), pred(pred) { }
int operator * () const { return pred(n); }
operator int () const { return n; }
int_iterator& operator ++ () { return *this += 1; }
int_iterator& operator += (int rhs) { n += rhs; return *this; }
};
function<int(int)> pred = [](int x) {
if (x < 100500) { return -1; }
if (x > 100600) { return 1; }
return 0;
};
int_iterator it_begin(0, pred), it_end(1000000, pred);
cout << "[" <<
lower_bound(it_begin, it_end, 0) << ", " <<
upper_bound(it_begin, it_end, 0) << "[" << endl; // [100500, 100601[Instead of .begin()/.end()/.size() methods on containers, global begin(cont)/end(cont)/size(cont) functions can be used, that also support arrays and strings from C.
cout << size("abcde") << endl; // 6, because there's also \0 character in the endSum of all values on a segment of container, defined by a pair of iterators. Type of resulting value is the same as type of initial value (sum vector<int64_t> to 0LL).
vector<int> v{1, 2, 3, 4};
cout << accumulate(v.begin(), v.end(), 0) << endl; // 10Partial sums:
vector<int> v{1, 2, 3, 4, 5}, res(5);
partial_sum(v.begin(), v.end(), res.begin()); // 1 3 6 10 15Generation of a sequence of values (with a prefix increment operator ++):
vector<int> v(5);
iota(v.begin(), v.end(), -2); // -2 -1 0 1 2There's a lot of math functions. Only popular and non-obvious given here.
L2-distance (hypotenuse of right triangle). More precise, but slower than naïve computation:
cout << hypot(4, 3) << endl; // 5Function atan2(y, x) computes the angle (in ]−π, +π]) between x axis and the ray to (x, y). It's an arctangent of y / x that takes into consideration operand signs, and also handles 0 / 0 case:
cout << atan2(10, -10) << " radians" << endl; // 2.35619π is not in standard yet. To avoid compiler-specific macros or manual definition, it's possible to use atan(1) = π / 4:
double const pi = atan(1) * 4; // 3.1415926535897931
cout << setprecision(20) << pi << " " // 3.141592653589793116
<< nexttoward(pi, 3.0) << " " // 3.1415926535897926719
<< nextafter(pi, 4.0) << endl; // 3.1415926535897935601Rounding down to next integer:
cout << floor(2.7) << " " << floor(-2.5) << endl; // 2 -3Rounding up:
cout << ceil(2.7) << " " << ceil(-2.5) << endl; // 3 -2Rounding to closest integer (half-integers rounding outwards from 0):
cout << round(2.7) << " " << round(-2.5) << endl; // 3 -3Absolute value:
cout << abs(-10) << endl; // 10Complex numbers can be used to shorten some 2D geometry calculations. For example, generation of coordinate offsets on square grid to 4-neighbors
complex<int> dir(1, 0);
for (int i = 0; i < 4; ++i) {
cout << dir << " " << dir.real() << " + " << dir.imag() << "j" << endl;
// (1,0) 1 + 0j; (0, 1) 0 + 1j; (-1, 0) -1 + 0j; (0, -1) 0 + -1j
dir *= complex<int>(0, 1);
}or triangle area.
stringstream ss("1 1\n1 4\n5 1");
double x, y;
ss >> x >> y; complex<double> a(x, y);
ss >> x >> y; complex<double> b(x, y);
ss >> x >> y; complex<double> c(x, y);
complex<double> A = b - a, B = c - a;
double S = abs((conj(A) * B).imag()) / 2.0;
cout << S << endl; // 6Don't forget that in times of war a value for sine can be as high as four.
cout << sin(1.570796327 - 2.063437069i) << endl; // (4,7.94362e-10)For all "unachievably big" and sentinel values (like 1e9) precise maximum and minimum values can be used.
cout << numeric_limits<int64_t>::min() << endl; // -9223372036854775808
cout << numeric_limits<int64_t>::max() << endl; // 9223372036854775807Pseudo-random number generators are rarely used in competitive programming in a fair way, but sometimes randomized solution is hard to challenge. By default C++ uses mt19937 generator.
default_random_engine generator;
generator.seed(0);
uniform_real_distribution<double> distribution(0.0, 1.0); // similarly, uniform_int_distribution<int>
double rnd = distribution(generator);
cout << rnd << endl; // 0.592845Swap values:
int x = 5, y = 3;
swap(x, y);
cout << x << " " << y << endl; // 3 5Bit representation with known number of digits might be easy to show with bitset.
cout << bitset<10>(777) << endl; // 1100001001Precise time measurement:
auto t0 = chrono::high_resolution_clock::now();
this_thread::sleep_for(1.0s);
auto t1 = chrono::high_resolution_clock::now();
cout << chrono::duration_cast<chrono::milliseconds>(t1 - t0).count() << endl; // 999
cout << chrono::duration<double>(t1 - t0).count() << endl; // 0.999376With the addition of lambda-functions in C++11 it became much easier to write callback functions. function template class is very useful to store them in variables (mostly for recursive lambda-functions, otherwise auto works just fine) or take them as arguments.
stringstream ss("6 5\n0 1\n0 2\n1 3\n1 4\n4 5");
int n, m;
ss >> n >> m;
vector<vector<int>> adjlist(n);
for (int i = 0; i < m; ++i) {
int a, b;
ss >> a >> b;
adjlist[a].push_back(b);
adjlist[b].push_back(a);
}
int time = 0;
function<void(int, int, function<void(int, int)>)> dfs =
[&adjlist, &time, &dfs](int v, int from, function<void(int, int)> enter) {
enter(v, time++);
for (int nn : adjlist[v]) {
if (nn != from) {
dfs(nn, v, enter);
}
}
time++;
};
dfs(0, -1, [](int v, int time) {
cout << "Entered " << v << " at time " << time << endl;
});
/*
Entered 0 at time 0
Entered 1 at time 1
Entered 3 at time 2
Entered 4 at time 4
Entered 5 at time 5
Entered 2 at time 9
*/These intrinsic functions might be useful. They compute in one assembler instruction number of set bits in a number (popcount), number of zeros in binary representation until first 1 is met, counting from the left (clz — count leading zeroes) and from the right (ctz — count trailing zeroes). Intrinsic functions are compiler-specific. These are only for MSVC or GCC.
#if defined(_MSC_VER)
#include <intrin.h>
#define popcount __popcnt
#define popcount64 __popcnt64
#elif defined(__GNUC__)
#define popcount __builtin_popcount
#define popcount64 __builtin_popcountll
#endif
#if defined(_MSC_VER)
#include <intrin.h>
int clz(uint32_t x) { unsigned long result = -1; _BitScanReverse(&result, x); return 31 - result; }
int ctz(uint32_t x) { unsigned long result = -1; _BitScanForward(&result, x); return result; }
int clz64(uint64_t x) { unsigned long result = -1; _BitScanReverse64(&result, x); return 63 - result; }
int ctz64(uint64_t x) { unsigned long result = -1; _BitScanForward64(&result, x); return result; }
#elif defined(__GNUC__)
#define clz __builtin_clz
#define ctz __builtin_ctz
#define clz64 __builtin_clzll
#define ctz64 __builtin_ctzll
#endif
uint64_t num = 0x000000F000000000ULL;
cout << "popcount: " << popcount64(num) << endl; // 4
cout << "leading 0s: " << clz64(num) << " trailing: " << ctz64(num) << endl; // 24 36
uint32_t num2 = 0x000F0000;
cout << "popcount: " << popcount(num2) << endl; // 4
cout << "leading 0s: " << clz(num2) << " trailing: " << ctz(num2) << endl; // 12 16In C++17 std::gcd was added to <numeric> header, but previously there was none. In GCC it was part of implementation of std::rotate, and could be accessed as __gcd. In MSVC it's available in boost library.
#if defined(_MSC_VER)
#include <boost/math/common_factor.hpp>
using boost::math::gcd;
#elif defined(__GNUC__)
#define gcd __gcd
#endif
cout << gcd(2983479376572795LL, 29837483726583645LL) << endl; // 1564-bit GCC extends a set of predefined integral numeric types with __int128. In MSVC it has to be taken from boost too.
#if defined(_MSC_VER)
#include <boost/multiprecision/cpp_int.hpp>
typedef boost::multiprecision::int128_t int128_t;
#elif defined(__GNUC__)
typedef __int128 int128_t;
#endif
int128_t result = int128_t(2983479376572795LL) * 29837483726583645LL;
cout << int(result % 1000000007) << endl; // 493398412