home

STL (Standard Template Library)

Table of Contents

Containers

Containers are data structures that are already implemented in STL.

Container is further divided into the following data structure types:

  • Sequential
    • vectors
    • stack
    • queue
  • Ordered
    • maps
    • multimap
    • set
    • multiset
  • Unordered
    • unordered map
    • unordered set

Above list does not include all the containers but most relevant ones. See https://cplusplus.com/reference/stl/ for more information on STL containers.

Nested Containers

Cotainers can be nested. Some examples are given below.

  • vector<vector<int>>
  • map<int, vector<int>>
  • set<pair<int, string>>

Pairs

pair is defined in the utility header file. Pairs are copied when passed as arguments or assigned to some other variable. Use cpp references or pointers to refer to a pair if needed. 

#include <utility>
#include <string>
#include <iostream>

int main() {
    std::pair<int, std::string> p = {1, "string"};
    std::cout << p.first << ":" << p.second << std::endl;

    // pairs are copied
    std::pair<int,std::string> p1 = p;
    p1.first = 43;
    std::cout << p.first << ":" << p.second << std::endl;

    // cpp references use with pairs
    std::pair<int,std::string> &p2 = p;
    p2.first = 69;
    std::cout << p.first << ":" << p.second << std::endl;

    // with pointers
    std::pair <int, std::string> *p3 = &p;
    p3->first = 990;
    std::cout << p.first << ":" << p.second << std::endl;
}

Vectors

Dynmaically sized contiguous memory blocks. Defined in vector header file. Vector has same size limits as arrays in cpp. Local vector can't be more than 105 in size and global vector can't be more than 107 in size. This limit is on the contiguous memory allocation that's why it's same for both arrays and vectors. 

#include <vector>
#include <iostream>

int main() {
    std::vector<int> v = {1,2,3};
    // vector of initial size 10 with all values set to 3
    // std::vector<int> x(10) will set all 10 values to 0 (data type's zero value)
    std::vector<int> x(10,3);

    for (int i : x) {
        std::cout << i << " ";
    }

    std::cout << std::endl;

    for (int i : v) {
        std::cout << i << std::endl;
    }

    v.push_back(69); // O(1)

    std::cout << v[3] << std::endl;
    std::cout << v.size() << std::endl;

    v.pop_back(); // O(1)
    std::cout << v.size() << std::endl;
}

Vectors can be copied unlike arrays. Use cpp references or pointers to get a reference to a vector. 

#include <vector>
#include <iostream>

int main() {
    std::vector<int> v = {1,2,3};
    std::vector<int> v1 = v;

    v1.push_back(10);

    for (int i : v) {
        std::cout << i << " ";
    }

    std::cout << std::endl;

    std::vector<int> &v2 = v;
    v2[0] = 99;
    std::cout << v[0] << std::endl;

    std::vector<int> *v3 = &v;
    (*v3)[0] = 32;
    std::cout << v[0] << std::endl;
}

Vectors can be nested to created multi-dimensional vectors (2d, 3d, …). Vector of pairs is also common in use. 

#include <utility>
#include <vector>
#include <iostream>

int main() {
    std::vector<std::pair<int, int>> v = {{1,2}, {2,9}};

    for (std::pair<int, int> p : v) {
        std::cout << p.first << " : " << p.second << std::endl;
    }
}

Maps

A data structure to store collection of key:value pairs. Pairs are stored in sorted order in a normal Map, use unordered map for storing unordered pairs.

Insertion and access in map is O(log(n)). Keys in a map are unique. It'll replace the old value in case of an overwrite operation.

Find operation (O(log(n))) returns an iterator that points to the found pair or the .end() if the pair does not exist.

Erase (map.erase()) (O(log(n))), takes in either the key or the iterator to the pair we want to erase from the map. You can't pass m.end() to erase as it's points to the element which is after the last element.

Use map.clear() to clear the map. 

#include<iostream>
#include<map>

int main() {
    std::map<int, std::string> m;
    m[1] = "abc";
    m.insert({2, "dewf"});
    m[9] = "jsf";
    m[5] = "jsklfjlks";
    m[99]; // insertion will still happen even if we didn't assign anything

    for (auto i : m) {
        std::cout <<  i.first << " : " << i.second << std::endl;
    }

    auto el = m.find(5);

    if (el != m.end()) {
        std::cout << el->second << std::endl;
    }

    m.erase(m.find(1)); // O(log(n)) + O(log(n)) for find and then erase
    m.erase(9); // O(log(n))

    for (auto i : m) {
        std::cout <<  i.first << " : " << i.second << std::endl;
    }
}

Unordered Maps

Difference from normal normal maps:

  • Inbuilt implementation: uses hash tables. Each key's hash values is calculated for comparison
  • time complexity: Insertion/Access time is O(1) (average time complexity). .erase() happens in O(1) when given an iterator.
  • valid key data types: vector<int> or pair<int, int> can't be used as key of a pair in unorderedmaps as their hash is not predefined by default. All standard data types (including std::string) can be used.
#include<iostream>
#include<unordered_map>

int main() {
    std::unordered_map<int, std::string> m;
    m[1] = "abc";
    m.insert({2, "dewf"});
    m[9] = "jsf";
    m[5] = "jsklfjlks";
    m[99]; // insertion will still happen even if we didn't assign anything

    for (auto i : m) {
        std::cout <<  i.first << " : " << i.second << std::endl;
    }
}

Multimaps

Pairs with same keys can exist in a multimap.

Sets

Collection of unique elements.

  • Normal Sets: Stores elements in sorted order. Insertion/Access takes O(log(n)) time. Find is also O(log(n)). =set.erase()= is same as it was in maps.
  • Unordered Sets: Stores elements in random order. Insert take O(1) time. Standard data types (including) strings can be used by default (uses hash for uniq check).
  • Multisets: allows for duplicate elements. If passed a value to set.erase(), it'll delete all the occurence of it. With an iterator, it'll only delete the element that's pointed by the iterator.
#include <iostream>
#include <set>

using namespace std;

int main() {
    set<string> s = {"gh", "asdf"};
    s.insert("abc");
    s.insert("abc"); // stores unique element

    auto res = s.find("asdf"); // return s.end() if not found
    cout << *res << endl;

    for (auto val : s) {
        cout << val << endl;
    }
}

#include <iostream>
#include <unordered_set>

using namespace std;

int main() {
    unordered_set<string> s = {"sidd"};
    s.insert("sidd"); // stores unique element

    cout << s.size() << endl;

    for (auto &val : s) {
        cout << val << endl;
    }
}

Stack

LIFO

Operations:

  • push (element on top of the stack)
  • pop (element from top of the stack)
  • top (get the top element of the stack)
#include <iostream>
#include <stack>

using namespace std;

int main() {
    stack<int> s;
    s.push(2);
    s.push(9);
    s.push(8);
    s.push(3);
    s.push(99);
    s.push(10);

    while(!s.empty()) {
        cout << s.top() << endl;
        s.pop();
    }
}

LC question (valid parens)

https://leetcode.com/problems/valid-parentheses

  • Solution 1
    class Solution1 {
public:
    bool isValid(string s) {
        stack<char> st;
        bool res = true;
        for (char &c : s) {
            if (c == '(' || c == '[' || c == '{') {
                st.push(c);
            } else {
                if (st.empty()) {
                    res = false;
                } else {
                    auto top = st.top();
                    st.pop();

                    if (c == ')' && top != '(') {
                        res = false;
                    } else if (c == '}' && top != '{') {
                        res = false;
                    } else if (c == ']' && top != '[') {
                        res = false;
                    }
                }
            }
        }

        if (!st.empty()) {
            res = false;
        }

        return res;
    }
};

    class Solution2 {
public:
    unordered_map<char, int> mp = {{'(', -1}, {'{', -2}, {'[', -3}, {')', 1}, {'}', 2}, {']', 3}};
    bool isValid(string s) {
        stack<char> st;
        for (char &c : s) {
            if (mp[c] < 0) {
                st.push(c);
            } else {
                if (st.empty()) {
                    return false;
                }
                auto top = st.top();
                st.pop();
                if (mp[top] + mp[c] != 0) {
                    return false;
                }
            }
        }

        return st.empty();
    }
};

    Driver Code with both the solutions 

    #include <iostream>
#include <stack>
#include <unordered_map>

using namespace std;

class Solution1 {
public:
    bool isValid(string s) {
        stack<char> st;
        bool res = true;
        for (char &c : s) {
            if (c == '(' || c == '[' || c == '{') {
                st.push(c);
            } else {
                if (st.empty()) {
                    res = false;
                } else {
                    auto top = st.top();
                    st.pop();

                    if (c == ')' && top != '(') {
                        res = false;
                    } else if (c == '}' && top != '{') {
                        res = false;
                    } else if (c == ']' && top != '[') {
                        res = false;
                    }
                }
            }
        }

        if (!st.empty()) {
            res = false;
        }

        return res;
    }
};

class Solution2 {
public:
    unordered_map<char, int> mp = {{'(', -1}, {'{', -2}, {'[', -3}, {')', 1}, {'}', 2}, {']', 3}};
    bool isValid(string s) {
        stack<char> st;
        for (char &c : s) {
            if (mp[c] < 0) {
                st.push(c);
            } else {
                if (st.empty()) {
                    return false;
                }
                auto top = st.top();
                st.pop();
                if (mp[top] + mp[c] != 0) {
                    return false;
                }
            }
        }

        return st.empty();
    }
};

int main() {
    auto sol1 = new Solution1();
    auto sol2 = new Solution2();

    cout << sol1->isValid("((()))") << endl;
    cout << sol1->isValid("({[]})") << endl;

    cout << sol1->isValid("(]") << endl;
    cout << sol1->isValid("[](()") << endl;

    cout << sol2->isValid("((()))") << endl;
    cout << sol2->isValid("({[]})") << endl;

    cout << sol2->isValid("(]") << endl;
    cout << sol2->isValid("[](()") << endl;
}

Queues

FIFO

Operations:

  • push (element to the back of the queue)
  • pop (remove the first element)
  • front (get the first element of the queue)
#include <iostream>
#include <queue>

using namespace std;

int main() {
    queue<string> q;
    q.push("abc");
    q.push("def");
    q.push("ghi");
    q.push("jkl");
    q.push("mno");

    while(!q.empty()) {
        cout << q.front() << endl;
        q.pop();
    }
}

Iterators

Pointer like structures. .begin() points at the first element of a data structure. .end() points at the element after the last element.

Increment operator (++) works for any iterator but adding 1 (it + 1) only works for vectors. (+1) moves to the next memory location which, in case of vectors is the location of the next element. Maps and other data structure do no store elements in contiguous memory block so this does not work. 

#include <iostream>
#include <vector>

int main() {
    std::vector<int> v = {1,2,3,4};
    std::vector<int>::iterator it = v.begin();

    std::cout << (*it) << std::endl;
    std::cout << (*(it + 1)) << std::endl;

    // i++/++i -> next iterator
    for (auto i = v.begin(); i != v.end(); ++i) {
        std::cout << (*i) << std::endl;
    }
}

C++11 introduced range based loops and the auto keyword that shortens the syntax required for iterator usage. 

#include <iostream>
#include <vector>

int main() {
    std::vector<int> v = {1,2,3,4};

    // uses iterators under the hood
    // the value inside identifier `i` is copied
    // use cpp references (int &i) when copying is not desired
    for (int i : v) {
        std::cout << i << std::endl;
    }

    std::vector<std::pair<int,int>> p = {{1,2}, {3,4}};

    // pi :: pair<int,int>
    // pari<int,int> -> auto!
    for (auto pi : p) {
        std::cout << pi.first << std::endl;
    }
}

Algorithms

  • {next,prev}permutations

Sort (O(nlog(n)))

std::sort takes in the first iterator (pointer to the first element) and pointer to the next element after the last element. 

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    int a[5] = {3,34,2,61,3};

    sort(a, a+5);

    for (int i : a) {
        cout << i << endl;
    }
}

Usage with vectors: 

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    vector<int> a = {1,99,3,4,10, 8};

    sort(a.begin(), a.end());

    for (int i : a) {
        cout << i << endl;
    }
}
  • Comparator Function in Sort

    The default logic for sort is to rearrange container elements in ascending order. We can change this behaviour

    Return false from the comparator function if you want to swap, else return true. We typically pass a comparison expression that when evaluated to false, triggers the swap operation. 

    #include <iostream>
#include <algorithm>

using namespace std;

bool cmp(pair<int, int> a, pair<int, int> b) {
    if (a.first != b.first) {
        return a.first < b.first;
    }
    return a.second > b.second;
}

int main() {
    vector<pair<int, int>> a = {{4,3}, {5,5}, {5,3}, {25, 6}, {7, 9}, {8, 5}};

    sort(a.begin(), a.end(), cmp);

    for (auto i : a) {
        cout << i.first << " " << i.second << endl;
    }
}

Lower/Upper Bound (O(log(n)))

The input to lower/upper bound should be sorted to get O(log(n)) perf. If the input isn't sorted, it'll take O(n) time.

Use set.lower_bound or set.upper_bound and map.lower_bound or map.upper_bound to get O(log(n)) with sets and maps.

Lower bound returns pointer (or iterator) to the given element or next element bigger than the given element. If both (given element and any element bigger than the given element) is not found, it'll return .end().

lower_bound searches for element x in a container such that i <= x, where i is the search argument passed. 

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    int a[5] = {3,34,2,61,3};

    sort(a, a+5);

    cout << *lower_bound(a, a+5, 3) << endl;
    cout << *lower_bound(a, a+5, 34) << endl;
    cout << *lower_bound(a, a+5, 61) << endl;

    // neither 69 nor any value greater than 69 exist so we get .end()
    if (lower_bound(a, a+5, 69) == (a+5)) {
        cout << "yes" << endl;
    }

    // we get 34 as 5 doesn't exist in `a`` and 34 is the next bigger element
    cout << *lower_bound(a, a+5, 5) << endl;
}

Upper bound returns pointer (or iterator) to the element which is greater than the given element.

upper_bound searches for element x in a container such that i < x, where i is the search argument passed. 

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    int a[5] = {3,34,2,61,3};

    sort(a, a+5);

    cout << *upper_bound(a, a+5, 3) << endl;
    cout << *upper_bound(a, a+5, 34) << endl;

    if (upper_bound(a, a+5, 61) == (a+5)) {
        cout << "no element bigger than " << 61 << " found" << endl;
    }

    // neither 69 nor any value greater than 69 exist so we get .end()
    if (upper_bound(a, a+5, 69) == (a+5)) {
        cout << "no eleme bigger than 69 found" << endl;
    }

    // we get 34 as 5 doesn't exist in `a`` and 34 is the next bigger element
    cout << *upper_bound(a, a+5, 5) << endl;
}

minelement, maxelement, accumulate, count, find and, reverse

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

using namespace std;

int main() {
    vector<int> v = {1,3,932,342,4,1};

    cout << *min_element(v.begin(), v.end()) << endl;
    cout << *max_element(v.begin(), v.end()) << endl;

    // accumulate gives sum of all elements in a container
    // defined in the `numeric` header file
    cout << accumulate(v.begin(), v.end(), 0) << endl;

    // count returns the number of occurrence of some element in a container
    cout << count(v.begin(), v.end(), 1) << endl;

    // find
    auto it = find(v.begin(), v.end(), 69);
    if (it != v.end()) cout << *it << endl;
    else cout << "not found" << endl;

    // reverse
    reverse(v.begin(), v.end());

    for (int &i:v) {
        cout << i << " ";
    }
    cout << endl;

    string s = "abcdef";
    reverse(s.begin(), s.end());
    cout << s << endl;
}

cpp lambdas

Lambdas in cpp can be used to create functions that are created for one time use. Lambda funcs can be assigned too. 

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

using namespace std;

int main() {
    vector<int> v = {1,3,932,342,4,1};

    for (int i : v) {
        cout << i << " ";
    }
    cout << endl;

    // sort in descending order using cpp lambdas
    sort(v.begin(), v.end(), [](int a, int b){ return a > b; });

    for (int i : v) {
        cout << i << " ";
    }
    cout << endl;

    cout << [](int x){ return x*2; }(10) << endl;
}

all_of, any_of and, none_of

all_of: returns true if the provided function returns true for all the elements. any_of: returns true if the provided function returns true for at least one element. none_of: returns true if the provided function returns false for all the elements. 

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

using namespace std;

int main() {
    vector<int> v = {1,3,932,342,4,1};

    // checks if all the elements are greater than 10 (they're not)
    cout << all_of(v.begin(), v.end(), [](auto a) { return a > 10; }) << endl;
    cout << any_of(v.begin(), v.end(), [](auto a) { return a > 10; }) << endl;
    // since none of the elments are negative, it prints 1 (true)
    cout << none_of(v.begin(), v.end(), [](auto a) { return a < 0; }) << endl;
}

Functors

TODO look more into this topic (not important for LC) Classes that act as functions?

Author: Siddhant Kumar