MCP
ProblemsResourcesCompetitions
Log in

Contents

Contents

  • C++ Reference Sheet
  • Template
  • Vectors
  • Algorithms
  • Math
  • Unordered Maps
  • Unordered Set
  • Heaps
  • Strings
  • Bitwise Operations
  • Common Functions
    • Precompute Factorials Modulo a Number
    • Check Whether a Number Is a Perfect Square

C++ Reference Sheet

University of Missouri - Columbia

Everything in this reference sheet assumes:

using namespace std;

Template

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;

#define FAST_IO ios::sync_with_stdio(false); cin.tie(NULL);
#define FOR(n) for (int i = 0; i < (n); ++i)
#define read(v, n) for (int i = 0; i < (n); ++i) cin >> v[i]

void solve() {

}

int main() {
    FAST_IO;

    int t = 1;
    cin >> t;

    FOR(t) {
        // cout << "Case #" << i + 1 << ": ";
        solve();
    }
}

Compile with:

g++ -std=c++17 file.cpp

Vectors

#include <vector>

iota() is included in <numeric>.

Algorithms

#include <algorithm>

Math

#include <numeric>
#include <cmath>

Unordered Maps

#include <unordered_map>

Unordered Set

#include <unordered_set>

Heaps

#include <queue>
#include <vector>

int main() {
    // ***** DECLARATION *****
    priority_queue<int> maxHeap; // Max heap

    priority_queue<int, vector<int>, greater<>> minHeap;
    

    
    maxHeap.();
    maxHeap.();
    maxHeap.();

    
     maximum = maxHeap.();

    
    maxHeap.();
}

Strings

#include <string>
#include <cstring>

Bitwise Operations

Common Functions

Precompute Factorials Modulo a Number

const int MAXN = 1e6;
// If actual factorial values are needed instead of modular values,
// do not generate past 20 when using 64-bit integers.

const long long MOD = 1e9 + ;
  fact[MAXN + ];

{
    fact[] = ;

     ( i = ; i <= MAXN; i++) {
        fact[i] = (fact[i - ] * i) % MOD;
    }
}

Check Whether a Number Is a Perfect Square

Editing is restricted to approved members.

int main() { int n = 10; int m = 5; // ***** DECLARATION ***** vector<int> arrayUnknownSize; // Declare a vector of unknown size vector<int> arrayKnownSize(n, 0); // Declare vector with size n, initialized to 0 vector<vector<int>> array2d(n, vector<int>(m, 0)); // Declare 2D array n x m initialized to 0 // ***** INSERTION ***** arrayUnknownSize.push_back(5); // Add element to vector arrayUnknownSize.pop_back(); // Remove final element arrayKnownSize[0] = 5; // Push when space is already allocated array2d.push_back({0, 0, 0}); // Insert a new row iota(arrayKnownSize.begin(), arrayKnownSize.end(), 1); // Fills the vector with 1, 2, 3, 4, ... // ***** ITERATION ***** // Iterate over vector elements for (int num : arrayUnknownSize) { cout << num << " "; } cout << endl; // Iterate over indexes for (int i = 0; i < arrayKnownSize.size(); i++) { cout << arrayKnownSize[i] << " "; } cout << endl; }
int main() { vector<int> array = {5, 3, 2, 1, 7}; int n = 5; int m = 6; // ***** SORTING VECTORS ***** sort(array.begin(), array.end()); // Sort increasing sort(array.begin(), array.end(), greater<int>()); // Sort decreasing bool isSorted = is_sorted(array.begin(), array.end()); // Check whether array is sorted increasing isSorted = is_sorted(array.begin(), array.end(), greater<int>()); // Check whether array is sorted decreasing // ***** REVERSE VECTOR ***** reverse(array.begin(), array.end()); // ***** MIN/MAX ***** int maxElement = *max_element(array.begin(), array.end()); int minElement = *min_element(array.begin(), array.end()); int maxBetweenTwo = max(n, m); int minBetweenTwo = min(n, m); // ***** PERMUTATIONS ***** // Generates the next lexicographically greater permutation while (true) { for (int num : array) cout << num << " "; cout << endl; if (!next_permutation(array.begin(), array.end())) break; } // Generates the next lexicographically smaller permutation while (true) { for (int num : array) cout << num << " "; cout << endl; if (!prev_permutation(array.begin(), array.end())) break; } }
int main() { int a = 5; int b = 5; double c = 10.0; vector<int> v(10, 0); iota(v.begin(), v.end(), 1); // ***** GCD / LCM ***** int leastCommon = lcm(a, b); // LCM between two numbers // LCM in array int result = 1; for (int num : v) result = lcm(result, num); int greatestCommon = gcd(a, b); // GCD between two numbers // GCD in array result = 1; for (int num : v) result = gcd(result, num); // ***** GENERAL MATH FUNCTIONS ***** abs(a); // Returns absolute value for int fabs(c); // Returns absolute value for double pow(a, b); // Returns a^b as a double sqrt(a); // Returns square root cbrt(a); // Returns cube root exp(a); // e^a log(a); // Natural logarithm log10(a); // Base-10 logarithm log2(a); // Base-2 logarithm // ***** ROUNDING ***** floor(c); // Returns the floor ceil(c); // Returns the ceiling round(c); // Rounds to nearest integer // ***** TRIGONOMETRY ***** double radians = M_PI / 6; double degrees = 90; double radiansFromDegrees = (M_PI / 180) * degrees; double degreesFromRadians = (180 / M_PI) * radians; // All return doubles sin(radians); cos(radians); tan(radians); asin(radians); acos(radians); atan(radians); // Direction is within +-90 degrees atan2(1.0, 1.0); // Angle in radians from vector (x, y) from the x-axis }
int main() { // ***** DECLARATION ***** unordered_map<int, int> map; // Declares a map with <key, value> types // ***** INSERT ***** map[1] = 5; // Overrides key if it exists; otherwise inserts it map.insert({2, 6}); // Does not override key; inserts only if it does not exist // ***** DELETION ***** map.erase(5); // Returns 1 if erased, 0 if the key did not exist // ***** ITERATION ***** for (auto& kv : map) { cout << kv.first << " " << kv.second << endl; } // ***** SIZE / EMPTY ***** map.size(); // Returns number of keys map.empty(); // True if no elements // ***** ACCESSING ***** int value = map[3]; // Automatically creates an entry with value 0 if it does not exist // Returns iterator to end if it does not exist, // otherwise returns iterator to the element. // Access data using it->first and it->second. map.find(1); // ***** DOES IT EXIST? ***** map.count(1); // Returns number of elements with that key: 0 or 1 }
int main() { // ***** DECLARATION ***** unordered_set<int> set; // Declares a set of ints with no duplicate values // ***** INSERT ***** set.insert(1); set.insert({2, 5}); // Insert multiple elements at once // ***** DELETION ***** set.erase(5); // Returns 1 if erased, 0 if the key did not exist // ***** ITERATION ***** for (int num : set) { cout << num << " "; } cout << endl; // ***** SIZE / EMPTY ***** set.size(); // Returns number of keys set.empty(); // True if no elements // ***** DOES IT EXIST? ***** set.count(1); // Returns 0 or 1 because duplicates are not allowed set.find(1); // Search for a value and get an iterator // ***** UNION ***** // Both sets combined. // It is usually faster to add everything to one of the existing sets. unordered_set<int> a = {1, 2, 3}; unordered_set<int> b = {3, 4, 5}; unordered_set<int> c; for (int num : a) c.insert(num); for (int num : b) c.insert(num); // ***** INTERSECTION ***** // Elements in both sets unordered_set<int> d; for (int num : a) { if (b.count(num)) { d.insert(num); } } // ***** DIFFERENCE A - B ***** // Elements only in a, not b or the intersection unordered_set<int> e; for (int num : a) { if (!b.count(num)) { e.insert(num); } } // ***** SYMMETRIC DIFFERENCE ***** // Elements in a or b, but not both unordered_set<int> f; for (int num : a) { if (!b.count(num)) f.insert(num); } for (int num : b) { if (!a.count(num)) f.insert(num); } }
int
// Min heap
// ***** INSERT *****
push
5
push
2
push
8
// ***** ACCESS *****
int
top
// ***** DELETION *****
pop
int main() { string s = "aabcd"; char c = 'A'; // ***** CHARACTER CHECKS ***** isalpha(c); // A-Z and a-z isdigit(c); // 0-9 isalnum(c); // A-Z, a-z, and 0-9 islower(c); // Lowercase isupper(c); // Uppercase tolower(c); toupper(c); // ***** COUNT CHARACTER OCCURRENCES ***** count(s.begin(), s.end(), 'a'); // ***** REVERSE STRING ***** reverse(s.begin(), s.end()); // Can be used to check whether a string is a palindrome // ***** MODIFYING ***** s += "efg"; // Append s.append("xyz"); // Append string s.push_back('z'); // Add one character s.pop_back(); // Remove final character s.insert(2, "XY"); // Insert before index 2 s.erase(1, 3); // Erase 3 characters starting at index 1 s.clear(); // Empty the string // ***** SUBSTRINGS ***** s.find("abc"); // Starting index of substring s.find('a'); // First index of 'a', or string::npos if not found s.rfind('a'); // Last index of 'a' s.substr(s.find("abc"), strlen("abc")); // Make substring starting at position, for a given number of characters // ***** CHECKS ***** s.empty(); s.size(); // ***** CONVERSIONS ***** string numStr = "123"; int num = stoi(numStr); // String -> int string s2 = to_string(42); // Int -> string string cppstr = "string"; char target[1024]; strcpy(target, cppstr.c_str()); // string -> C array }
int main() { int a = 5; // 0101 binary int b = 3; // 0011 binary // ***** BASIC BITWISE OPERATORS ***** a & b; // AND 0101 & 0011 = 0001 (1) a | b; // OR 0101 | 0011 = 0111 (7) a ^ b; // XOR 0101 ^ 0011 = 0110 (6) ~a; // NOT Inverts bits a << 1; // LEFT SHIFT 0101 << 1 = 1010 (10), multiplies by 2 a >> 1; // RIGHT SHIFT 0101 >> 1 = 0010 (2), divides by 2 // ***** COMPARISON EXAMPLES ***** int x = 6; // 110 int y = 3; // 011 x & y; // 010 (2) x | y; // 111 (7) x ^ y; // 101 (5) // ***** CHECKING A BIT ***** int n = 42; // 101010 int i = 3; bool bit = (n >> i) & 1; // Get the i-th bit, zero-indexed from the right // ***** SETTING A BIT ***** n |= (1 << i); // Set bit i to 1 // ***** CLEARING A BIT ***** n &= ~(1 << i); // Set bit i to 0 // ***** TOGGLE A BIT ***** n ^= (1 << i); // Flip bit i // ***** COUNT SET BITS ***** __builtin_popcount(n); // int, 32-bit __builtin_popcountll(n); // long long, 64-bit // ***** CHECK POWER OF 2 ***** bool isPowerOf2 = n && !(n & (n - 1)); // True when only one bit is set // ***** LOWEST SET BIT ***** int lowest = n & -n; // Isolate rightmost 1-bit // ***** REMOVE LOWEST SET BIT ***** n &= (n - 1); // ***** BITMASK EXAMPLE ***** int mask = (1 << 5) - 1; // 00011111, lower five bits set // ***** SWAP USING XOR ***** int p = 5; int q = 7; p ^= q; q ^= p; p ^= q; }
7
long
long
1
void precompute()
0
1
for
int
1
1
#include <iostream> #include <cmath> using namespace std; bool isPerfectSquare(long long n) { long long root = static_cast<long long>(sqrt(n)); return root * root == n; } int main() { cout << isPerfectSquare(25) << endl; // 1 = true cout << isPerfectSquare(26) << endl; // 0 = false }