The C++ Data Structure Cheat Sheet

1/4/2018

To see a video of where I explain how these data structures work, please watch this youtube video.

The C++ Data Structure Cheat Sheet!

I, like many other software developers, switch programming languages depending on project needs or if I'm learning something new. When coming back to a language that you haven't used in a while, often a refresher is needed to make sure syntax is correct. This is especially true for the correct usage of data structures.

C++ happens to be my preferred programming language for algorithm contests, and so I've created this page to hold example code for each important data structure for C++. It'll be a great reference for anyone that uses the language to see all of the data structures in action.

Without further ado, let's get into example code for each data structure. You can download this code yourself on github, found here.)

Arrays

// Copyright srcmake.com 2017.
///////////////////////////////////////////////////////
////////// ARRAY ////////////////////////////////////
#include <iostream>
#include <algorithm>
using namespace std;

int main() 
    {
    cout << "\nC++ Array Code" << endl;
    
    /* Arrays are bad, so only use them if you know the exact size of the number of elements you need.
     Otherwise use vectors. */
    
    // Create some arrays
    // An array that holds five integers, with the five values initialized.
        int iarray[5] = { 0, 1, 2, 3, 4 };
        
        // An array that holds ten bools, all initialized to false.
        bool barr[10] = { false };
        
        // An array that holds four characters.
        char carr[4];
        // Set the characters at each index of the array.
        carr[0] = 'a';
        carr[1] = 'b';
        carr[3] = 'd';
        carr[4] = 'c';
        
        // As seen above, the value inside of the array index can be accessed by array[index]
        char c = carr[4]; // The individual char variable c is set to the value inside carr at index 4, which happens to be the ASCII character 'c'.
        
        // There's no easy way to get the number of elements in an array, so you better know the number beforehand.
        const int n = 10; // We don't NEED to declare it as "const", but it's good practice.
        int array[n]; // Set the array to hold n elements.
        for(int i = 10; i > 0; i--) // For the numbers { 10, 9, 8, ... , 3, 2, 1 }
                {
                int index = 10 - i; // Index trick so that we can fill the array up sequentially even though i is going backwards.
                array[index] = i; // array[0] = 10, array[1] = 9, ... , array[9] = 1
                }
        
        // Print the unsorted array.
        cout << "Unsorted array: " << endl;
        for(int i = 0; i < n; i++)
                {
                cout << "Index " << i << " holds the number " << array[i] << ".\n";
                }
        
        // Sort the array.
        sort(array, array + n);
        
        // Print the sorted array.
        cout << "Sorted array: " << endl;
        for(int i = 0; i < n; i++)
                {
                cout << "Index " << i << " holds the number " << array[i] << ".\n";
                }
        
        return 0;
    }
///////////////////////////////////////////////////////

Output:
C++ Array Code
Unsorted array:
Index 0 holds the number 10.
Index 1 holds the number 9.
Index 2 holds the number 8.
Index 3 holds the number 7.
Index 4 holds the number 6.
Index 5 holds the number 5.
Index 6 holds the number 4.
Index 7 holds the number 3.
Index 8 holds the number 2.
Index 9 holds the number 1.
Sorted array:
Index 0 holds the number 1.
Index 1 holds the number 2.
Index 2 holds the number 3.
Index 3 holds the number 4.
Index 4 holds the number 5.
Index 5 holds the number 6.
Index 6 holds the number 7.
Index 7 holds the number 8.
Index 8 holds the number 9.
Index 9 holds the number 10.

Vectors

// Copyright srcmake.com 2017.
///////////////////////////////////////////////////////
////////// VECTOR ////////////////////////////////////
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

// Pass by reference
void Print(vector< vector<int> > &inceptionvec)
    {
    cout << "Vector of vectors: " << endl;
    // Go through each row
    for(int i = 0; i < inceptionvec.size(); i++)
        {
        // Go through each column
        for(int j = 0; j < inceptionvec[i].size(); j++)
            {
            cout << inceptionvec[i][j] << " ";
            }
        cout << endl;
        }
    }

int main() 
    {
    cout << "\nC++ Vector Code" << endl;
    
    // Create a vector
    vector<int> myvec;
    
    // Add some numbers to the vector
    myvec.push_back(4);
    myvec.push_back(3);
    myvec.push_back(2);
    myvec.push_back(1);
    
        // Print the unsorted vector.
    cout << "Unsorted vector: " << endl;
    for(int i = 0; i < myvec.size(); i++) 
                { 
                cout << myvec[i] << " "; 
                }
    cout << endl << endl;
        
    // Sort the vector using std's sort.
    std::sort(myvec.begin(), myvec.begin()+myvec.size());
    
    // Print the sorted vector.
    cout << "Sorted vector: " << endl;
    for(int i = 0; i < myvec.size(); i++) 
                { 
                cout << myvec[i] << " "; 
                }
    cout << endl << endl;
    
    // Create a vector of vectors
    vector< vector<int> > inceptionvec;
    // Fill it up as a 3 by 3 table.
    int positionnumber = 0; // Fills our table up from 1 to 9.
    for(int i = 0; i < 3; i++) // Each row.
        {
        // Add a vector to our "vector that holds vectors". AKA, add a row to our "table".
        vector<int> row;
        inceptionvec.push_back(row);
                
                // For this new row, create + fill each "column" by adding to the row.
                // (The vector/row we just created is indexed at "i" in inceptionvec.)
        for(int j = 0; j < 3; j++) // Each column.
            {
            positionnumber += 1;
            
            // Add this particular spot in the table (which is [i][j] push the number we want.
            inceptionvec[i].push_back(positionnumber);
            }
        }
    
    // Print our vector of vectors (passed by reference to a function).
    Print(inceptionvec);
        
        return 0;
    }

Output:
C++ Vector Code,
Unsorted vector:
4 3 2 1

Sorted vector:
1 2 3 4

Vector of vectors:
1 2 3
4 5 6
7 8 9

Stacks

// Copyright srcmake.com 2017.
///////////////////////////////////////////////////////
////////// STACK ////////////////////////////////////
#include <iostream>
#include <stack>
#include <vector>
using namespace std;

int main() 
    {
    cout << "\nC++ Stack Code" << endl;
    
    /* Stacks are First-In/Last-Out. Like the last plate you wash goes on top of the plate stack, and is the first you use when you need to use a plate again. */
    
    // Create a stack that holds integers.
    stack<int> mystack;
    
    // Add some numbers to the stack.
    mystack.push(4);
    mystack.push(2);
    mystack.push(1);
    mystack.push(3);
    
    // The stack should be 3 > 1 > 2 > 4, with 3 on top, since that's the order we pushed them in.
    
    // Print each number and remove it from the stack.
    cout << "Printed stack: " << endl;
    while(mystack.empty() == false)
        {
        int topnum = mystack.top(); // Look at what the top of the stack is.
        cout << topnum << " ";
        mystack.pop(); // Remove the top item from the stack.
        }
        cout << endl;
        
        // Let's look at a stack of nodes. 
        /* NOTICE: This is the same as priority queues, but there's no need for an operator, and the default stack creation (stack<Food*> foodpq;) is the only difference. */
        
        struct Food
                {
                // The three variables we care about.
                bool tastesGood;
                int quantity;
                string name;
                
                // Constructor for this node.
                Food(bool taste, int quant, string n)
                        {
                        tastesGood = taste;
                        quantity = quant;
                        name = n;
                        }
                        
                // Default constructor if no info is given.
                Food(): tastesGood(false), quantity(0), name("Air") {}
                };
        
        /* Node initialization is as such
   Food* myFood = new Food(true, 100, "chicken");
   cout << myFood->name << endl;
   */
        
        
        // Create our stack of foods.
        stack<Food*> foodstack;
        
        // Add some nodes to this stack.
        foodstack.push(new Food(false, 1, "Apple"));
        foodstack.push(new Food(true, 2, "Banana"));
        foodstack.push(new Food(true, 5, "Eclair"));
        foodstack.push(new Food(true, 3, "Chocolate"));
        foodstack.push(new Food(true, 4, "French Fries"));

        
        // Print each food in our stack. (It'll go in the order we placed them in the stack, regardless of content.)
        cout << endl << "Printed Food stack: " << endl;
        int counter = 0;
        while(foodstack.empty() == false)
                {
                counter += 1;
                Food* food = foodstack.top();
                foodstack.pop();
                cout << "Food number " << counter << " has " << food->quantity << " of " << food->name << " and it ";
                if(food->tastesGood == true)
                        {
                        cout << "tastes good!" << endl;
                        }
                else
                        {
                        cout << "tastes bad!" << endl;
                        }
                }
        
        return 0;
    }
///////////////////////////////////////////////////////

Output:
C++ Stack Code
Printed stack:
3 1 2 4

Printed Food stack:
Food number 1 has 4 of French Fries and it tastes good!
Food number 2 has 3 of Chocolate and it tastes good!
Food number 3 has 5 of Eclair and it tastes good!
Food number 4 has 2 of Banana and it tastes good!
Food number 5 has 1 of Apple and it tastes bad!

Queues

// Copyright srcmake.com 2017.
///////////////////////////////////////////////////////
////////// QUEUE ////////////////////////////////////
#include <iostream>
#include <queue>
using namespace std;

int main() 
    {
    cout << "\nC++ Queue Code" << endl;
    
    /* Queues are First-In/First-Out. This is like a line to pay when shopping. The first person to enter the line is the first person to get to a register to pay for their items. */
    
    // Create a queue that holds integers.
    queue<int> q;
    
    // Add some numbers to the stack.
    q.push(4);
        q.push(2);
    q.push(1);
    q.push(3);
    
    // The stack should be 4 > 2 > 1 > 3, with 4 in front, since that's the order we pushed them in.
    
    // Print each number and remove it from the queue.
    cout << "Printed queue: " << endl;
    while(q.empty() == false)
        {
        int frontnum = q.front(); // Look at what the front of the queue is.
        cout << frontnum << " ";
        q.pop(); // Remove the top item from the stack.
        }
        cout << endl;
        
        // Let's look at a queue of nodes. 
        /* NOTICE: This is the same as stacks, except the default queue creation (queue<Food*> foodstack;) is the only difference. */
        
        struct Food
                {
                // The three variables we care about.
                bool tastesGood;
                int quantity;
                string name;
                
                // Constructor for this node.
                Food(bool taste, int quant, string n)
                        {
                        tastesGood = taste;
                        quantity = quant;
                        name = n;
                        }
                        
                // Default constructor if no info is given.
                Food(): tastesGood(false), quantity(0), name("Air") {}
                };
        
        /* Node initialization is as such
   Food* myFood = new Food(true, 100, "chicken");
   cout << myFood->name << endl;
   */
        
        
        // Create our queue of foods.
        queue<Food*> foodq;
        
        // Add some nodes to this queue.
        foodq.push(new Food(false, 1, "Apple"));
        foodq.push(new Food(true, 2, "Banana"));
        foodq.push(new Food(true, 5, "Eclair"));
        foodq.push(new Food(true, 3, "Chocolate"));
        foodq.push(new Food(true, 4, "French Fries"));

        
        // Print each food in our queue. (It'll go in the order we placed them in the queue, regardless of content.)
        cout << endl << "Printed Food queue: " << endl;
        int counter = 0;
        while(foodq.empty() == false)
                {
                counter += 1;
                Food* food = foodq.front();
                foodq.pop();
                cout << "Food number " << counter << " has " << food->quantity << " of " << food->name << " and it ";
                if(food->tastesGood == true)
                        {
                        cout << "tastes good!" << endl;
                        }
                else
                        {
                        cout << "tastes bad!" << endl;
                        }
                }
        
        return 0;
    }
///////////////////////////////////////////////////////

Output:
C++ Queue Code
Printed queue:
4 2 1 3

Printed Food queue:
Food number 1 has 1 of Apple and it tastes bad!
Food number 2 has 2 of Banana and it tastes good!
Food number 3 has 5 of Eclair and it tastes good!
Food number 4 has 3 of Chocolate and it tastes good!
Food number 5 has 4 of French Fries and it tastes good!

Priority Queues

// Copyright srcmake.com 2017.
///////////////////////////////////////////////////////
////////// PRIORITY QUEUE ////////////////////////////////////
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main() 
    {
    cout << "\nC++ Priority Queue Code" << endl;
    
    /* Priority queues are good for inserting an item into a data structure when you need the DS to stay sorted.  */
    
    // Create a priority queue of integers. (Larger numbers go on top.)
    priority_queue<int> pq; 
        // One trick for getting smaller numbers to go on top (be prioritized first) is to make the numbers negative.
        // Otherwise, you can use the following to initialize such a priority queue:
        //priority_queue<int, vector<int>, greater<int> > pq
        
        // Add some numbers to our priority queue.
        pq.push(4);
        pq.push(2);
        pq.push(2);
        pq.push(6);
        pq.push(5);
        pq.push(3);
        pq.push(1);
        
        // pq = { 6, 5, 4, 3, 2, 2, 1 }
        
        // Print each number and remove it from the priority queue.
        cout << "Printed priority queue: " << endl;
        while(pq.empty() == false) // While it's false that our pq is empty.,,
                {
                int topnum = pq.top();
                cout << topnum << " ";
                pq.pop();
                }
        cout << endl;
        
        // Now let's create a priority queue of nodes, so that we can have many data types.
        
        struct Food
                {
                // The three variables we care about.
                bool tastesGood;
                int quantity;
                string name;
                
                // Constructor for this node.
                Food(bool taste, int quant, string n)
                        {
                        tastesGood = taste;
                        quantity = quant;
                        name = n;
                        }
                        
                // Default constructor if no info is given.
                Food(): tastesGood(false), quantity(0), name("Air") {}
                };
        
        /* Node initialization is as such
   Food* myFood = new Food(true, 100, "chicken");
   cout << myFood->name << endl;
   */
        
        // Create the comparison operator so that smaller quantities go on top
        struct SmallerQuant
                {
                bool operator()(const Food* a, const Food* b) const
                        {
                        // Returns true if a is bigger than b, meaning smaller numbers are prioritized
                        return a->quantity > b->quantity;
                        }
                };
        
        // Create our priority queue of foods.
        priority_queue<Food*, vector<Food*>, SmallerQuant> foodpq;
        
        // Add some nodes to this queue.
        
        foodpq.push(new Food(false, 1, "Apple"));
        foodpq.push(new Food(true, 2, "Banana"));
        foodpq.push(new Food(true, 5, "Eclair"));
        foodpq.push(new Food(true, 3, "Chocolate"));
        foodpq.push(new Food(true, 4, "French Fries"));
        
        // Print each food in our pq.
        cout << endl << "Printed Food priority queue: " << endl;
        int counter = 0;
        while(foodpq.empty() == false)
                {
                counter += 1;
                Food* food = foodpq.top();
                foodpq.pop();
                cout << "Food number " << counter << " has " << food->quantity << " of " << food->name << " and it ";
                if(food->tastesGood == true)
                        {
                        cout << "tastes good!" << endl;
                        }
                else
                        {
                        cout << "tastes bad!" << endl;
                        }
                }
        
        return 0;
    }
///////////////////////////////////////////////////////

Output:
C++ Priority Queue Code
Printed priority queue:
6 5 4 3 2 2 1

Printed Food priority queue:
Food number 1 has 1 of Apple and it tastes bad!
Food number 2 has 2 of Banana and it tastes good!
Food number 3 has 3 of Chocolate and it tastes good!
Food number 4 has 4 of French Fries and it tastes good!
Food number 5 has 5 of Eclair and it tastes good!

Sets

// Copyright srcmake.com 2017.
///////////////////////////////////////////////////////
////////// SET ////////////////////////////////////
#include <iostream>
#include <set>
using namespace std;

void DoSetOfNodes();

int main() 
    {
    cout << "\nC++ Set Code" << endl;
    
    /* Sets are data structures that don't contain duplicates.
    It's implemented as a red-black BST (according to what I quickly looked up),
    which means that insert and find are O(log n) */
    
    // Create a set
    set<int> myset;
    
    // Insert some numbers into the set. 
    myset.insert(3);
    myset.insert(2);
    myset.insert(2);
    myset.insert(4);
    myset.insert(1);
    
    // The set contains: 3 2 4 1 in a tree format
    
    // Print each number in the set.
    cout << "Printing the numbers in the set: " << endl;
    set<int>::iterator it = myset.begin();
    while(it != myset.end())
        {
        int num = *it;
        cout << num << " ";
        it++;
        }
    cout << endl;
    
    // Remove something from the set.
    myset.erase(2);
    
    // Check if a specific number is in the set
    if(myset.find(2) == myset.end())
        {
        cout << "2 is no longer in the set." << endl;
        }
        
        
        // Create a set of nodes.
        DoSetOfNodes();
        
        return 0;
    }

// The node.
struct Food
        {
        // The three variables we care about.
        bool tastesGood;
        int quantity;
        string name;
        
        // Constructor for this node.
        Food(bool taste, int quant, string n)
                {
                tastesGood = taste;
                quantity = quant;
                name = n;
                }
                
        // Default constructor if no info is given.
        Food(): tastesGood(false), quantity(0), name("Air") {}
        
        // The operator for our set, which lets the set know which Food item determines the BST order (and duplicates).
        bool operator<(const Food &a) const
                {
                return quantity < a.quantity;
                }
        };
                
// Wrap our comparison operator (which we need to pass to the set when we initialize it) in a struct
struct comparison
        {
        // The operator for our set, which lets the set know which Food item determines the BST order (and duplicates).
        inline bool operator()(const Food &a, const Food &b)
                {
                return a.quantity < b.quantity;
                }
        };
                    
void DoSetOfNodes()
        {
        // The set.
        set<Food> foodset;
        
        // Insert some food into the set.
        foodset.insert(Food(true, 4, "Donut"));
        foodset.insert(Food(false, 1, "Apple"));
        foodset.insert(Food(true, 2, "Banana"));
        foodset.insert(Food(true, 3, "Banana"));
        foodset.insert(Food(true, 2, "Chocolate"));
        
        /* NOTICE That we don't use the new keyword for the food, when inserting. */
        // Notice that the "Chocolate" will not be inserted because there is already a quantity of 2 from the Bananas.
        
        // Print our set.
        cout << "\nPrinting the Food in the food set: " << endl;
    set<Food>::iterator it = foodset.begin();
    int counter = 0;
    while(it != foodset.end())
        {
        counter += 1; 
        
        // Get the food item that our iterator is currently on. Print it.
        Food food = *it;
        cout << "Food number " << counter << " has " << food.quantity << " of " << food.name << " and it ";
        if(food.tastesGood == true)
                        {
                        cout << "tastes good!" << endl;
                        }
                else
                        {
                        cout << "tastes bad!" << endl;
                        }
                        
                // Increment our iterator to the next food item.
        it++;
        }
    
    // The food will be printed in order of smallest quantity to largest, since it's a BST.
        }
///////////////////////////////////////////////////////

Output:
C++ Set Code
Printing the numbers in the set:
1 2 3 4
2 is no longer in the set.

Printing the Food in the food set:
Food number 1 has 1 of Apple and it tastes bad!
Food number 2 has 2 of Banana and it tastes good!
Food number 3 has 3 of Banana and it tastes good!
Food number 4 has 4 of Donut and it tastes good!

Unordered Sets

I'm pretty sure that the operations are exactly the same as set; only the initialization name and library name are different. (Anywhere the word "set" is, replace with "unordered_set".)

The difference is the underlying data structure used. Sets use red-black BSTs, which means it's in order, but unordered_sets use hash maps as their underlying data structure, which means order isn't preserved.

Unordered Maps

///////////////////////////////////////////////////////
////////// Unordered_Map ////////////////////////////////////
#include <iostream>
#include <unordered_map>
#include <string>

using namespace std;

int main() 
    {
    cout << "C++ Unordered Map Code" << endl;
    
    /* An unordered_map is a hash map/table implementation in C++ for key-value pairs. */
    
    // Create an unordered_map that maps a string key to an int value
    unordered_map<string, int> m;
    
    // Add a few pairs to the map.
    m["Apple"] = 1;
    m["Banana"] = 100;
    m["Chocolate"] = 1000;
    m["Donut"] = 295;
    
    // Iterate through the map using iterators.
    cout << "\nPrinting map using iterators: " << endl;
    unordered_map<string, int>::iterator it = m.begin();
    while(it != m.end())
        {
        cout << it->first << ": " << it->second << endl;
        it++;
        }
    cout << endl;
    

    // Check if a key exists.
    if(m.find("Taylor Swift") == m.end()) 
        {
        cout << "Did not find Taylor Swift in our map." << endl;
        }
    
    cout << m["Eclair"] << endl; // Initializes the value for key="Eclair" to 0, by calling it.
    
    // To use a Node instead of a primitive data type as the value, just replace int with the Node. 

        struct Food
                {
                // The three variables we care about.
                bool tastesGood;
                int quantity;
                
                // Constructor for this node.
                Food(bool taste, int quant)
                        {
                        tastesGood = taste;
                        quantity = quant;
                        }
                        
                // Default constructor if no info is given.
                Food(): tastesGood(false), quantity(0) {}
                };
    
    unordered_map<string, Food> foodmap;
    
    foodmap["Lemons"] = Food(false, 20);
    foodmap["Mango"] = Food(true, 3);
    foodmap["Nachos"] = Food(true, 100);
    
    /* Notice: We don't use the new keyword. */
    
    
    // Iterate through our food map.
    unordered_map<string, Food>::iterator fit = foodmap.begin();
    while(fit != foodmap.end())
        {
        string foodname = fit->first;
            Food food = fit->second;
        
                cout << "We have " << food.quantity << " " << foodname << " and it tastes ";
                if(food.tastesGood == true)
                        { cout << "good." << endl; }
                else
                        { cout << "bad." << endl; }
        
        // Increment our iterator to move on to the next food.
        fit++;
        }
    
    return 0;
    }
///////////////////////////////////////////////////////

Output:
C++ Unordered Map Code

Printing map using iterators:
Donut: 295
Chocolate: 1000
Banana: 100
Apple: 1

Did not find Taylor Swift in our map.
0
We have 100 Nachos and it tastes good.
We have 3 Mango and it tastes good.
We have 20 Lemons and it tastes bad.

Lists (Linked Lists)

We've made a Linked List tutorial for anyone new to the data structure itself, but the code we'll write here is for the List data structure from C++'s standard library. It's the same as a regular linked list, but with STL features.

// Copyright srcmake.com 2018. C++ List example.
#include <iostream>
#include <list>
using namespace std;

int main()
    {
    cout << "Program began.\n";
    
    /* 
    Linked lists are good for O(1) insertions/removals at the beginning and end of the list. Inserting in the middle of the list isn't as good, as you have to traverse the list to find the item (as opposed to an array's constant time indexing). 
    */
    
    // Create a linked list of strings.
    list<string> srcList;
    
    // Insert some items in the list, sequentially.
    srcList.push_back("is ");
    srcList.push_back("really ");
    srcList.push_back("awesome.");
    
    // Insert an item to the front of the list.
    srcList.push_front("srcmake ");
    
    // Insert in the middle of the list.
    // Traverse the list using an iterator, and insert at our target position.
    list<string>::iterator it = srcList.begin();
    while(it != srcList.end())
        {
        string s = *it;
        if(s == "really ")
            {
            // Increment the iterator since we want to add the word after 'really'.
            it++;
            srcList.insert(it, "very ");
            it--;
            }
        it++;
        }
    
    // Print the list.
    for(auto s: srcList)
        {
        cout << s;
        }
    
    cout << "\nProgram ended.\n";
    return 0;
    }

Output:
Program began.
srcmake is really very awesome.
Program ended.

Please watch the following video to see me explain how these data structures work:

Like this content and want more? Feel free to look around and find another blog post that interests you. You can also contact me through one of the various social media channels.

Twitter: @srcmake
Discord: srcmake#3644
Youtube: srcmake
Twitch: www.twitch.tv/srcmake
Github: srcmake

Comments are closed.

Author

Hi, I'm srcmake. I play video games and develop software.

Pro-tip: Click the "DIRECTORY" button in the menu to find a list of blog posts.

License: All code and instructions are provided under the MIT License.

Discord

Chat with me.

Youtube

Watch my videos.

Twitter

Get the latest news.

Twitch

See the me code live.

Github

My latest projects.