C++ Data Structures and STL

Welcome to The Coding College! In this tutorial, we’ll explore Data Structures and the Standard Template Library (STL) in C++. The STL provides powerful, reusable templates for common data structures and algorithms, making it an essential tool for every C++ programmer.

What Are Data Structures?

Data structures are ways to organize and store data efficiently for various operations like searching, sorting, and indexing. C++ provides built-in data structures and a comprehensive STL to simplify their implementation.

What Is the Standard Template Library (STL)?

The Standard Template Library (STL) is a collection of:

  1. Containers: Classes that store data.
  2. Iterators: Tools for accessing elements in containers.
  3. Algorithms: Predefined operations like sorting, searching, and more.

Key STL Components

CategoryExamples
Sequential Containersvector, list, deque, array, forward_list.
Associative Containersset, map, multiset, multimap.
Unordered Containersunordered_set, unordered_map, etc.
Algorithmssort, find, binary_search, accumulate.
Iteratorsbegin(), end(), rbegin(), rend().

Sequential Containers

1. Vectors

Vectors are dynamic arrays that can resize automatically.

#include <iostream>
#include <vector>
using namespace std;

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

    // Adding elements
    numbers.push_back(5);

    // Accessing elements
    cout << "First element: " << numbers[0] << endl;

    // Iterating
    for (int num : numbers) {
        cout << num << " ";
    }

    return 0;
}

Output:

First element: 1  
1 2 3 4 5

2. Lists

Lists are doubly linked lists that provide efficient insertions and deletions.

#include <iostream>
#include <list>
using namespace std;

int main() {
    list<int> numbers = {1, 2, 3, 4};

    // Adding elements
    numbers.push_back(5);
    numbers.push_front(0);

    // Iterating
    for (int num : numbers) {
        cout << num << " ";
    }

    return 0;
}

Output:

0 1 2 3 4 5

3. Deque

Deque (double-ended queue) supports fast insertion and deletion at both ends.

#include <iostream>
#include <deque>
using namespace std;

int main() {
    deque<int> dq = {1, 2, 3};

    dq.push_front(0);
    dq.push_back(4);

    for (int num : dq) {
        cout << num << " ";
    }

    return 0;
}

Output:

0 1 2 3 4

Associative Containers

1. Sets

Sets store unique, sorted elements.

#include <iostream>
#include <set>
using namespace std;

int main() {
    set<int> s = {3, 1, 4, 2};

    s.insert(5);
    s.insert(2); // Duplicate elements are ignored

    for (int num : s) {
        cout << num << " ";
    }

    return 0;
}

Output:

1 2 3 4 5

2. Maps

Maps store key-value pairs with unique keys.

#include <iostream>
#include <map>
using namespace std;

int main() {
    map<string, int> studentMarks = {{"Alice", 90}, {"Bob", 85}};

    studentMarks["Charlie"] = 88;

    for (auto& pair : studentMarks) {
        cout << pair.first << ": " << pair.second << endl;
    }

    return 0;
}

Output:

Alice: 90  
Bob: 85  
Charlie: 88

Unordered Containers

Unordered containers store elements in no particular order and provide faster access using hash tables.

Example: unordered_map

#include <iostream>
#include <unordered_map>
using namespace std;

int main() {
    unordered_map<string, int> studentMarks = {{"Alice", 90}, {"Bob", 85}};

    studentMarks["Charlie"] = 88;

    for (auto& pair : studentMarks) {
        cout << pair.first << ": " << pair.second << endl;
    }

    return 0;
}

Output:

Alice: 90  
Charlie: 88  
Bob: 85

Algorithms

STL algorithms operate on containers and iterators.

Example: Sorting with sort()

#include <iostream>
#include <vector>
#include <algorithm> // Include for algorithms
using namespace std;

int main() {
    vector<int> numbers = {4, 2, 5, 1, 3};

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

    for (int num : numbers) {
        cout << num << " ";
    }

    return 0;
}

Output:

1 2 3 4 5

Example: Finding with find()

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> numbers = {1, 2, 3, 4, 5};

    auto it = find(numbers.begin(), numbers.end(), 3);

    if (it != numbers.end()) {
        cout << "Found: " << *it << endl;
    } else {
        cout << "Not found!" << endl;
    }

    return 0;
}

Output:

Found: 3

Iterators

Iterators are used to traverse containers.

Example: Using Iterators with vector

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> numbers = {1, 2, 3, 4, 5};

    for (vector<int>::iterator it = numbers.begin(); it != numbers.end(); ++it) {
        cout << *it << " ";
    }

    return 0;
}

Output:

1 2 3 4 5

Summary

  1. STL Containers: Use containers like vector, set, and map for efficient data management.
  2. STL Algorithms: Leverage algorithms like sort() and find() for common operations.
  3. Iterators: Use iterators to traverse and manipulate containers.
  4. Unordered Containers: Opt for hash-based containers for fast lookups.

Learn More at The Coding College

For more advanced tutorials on C++ programming and efficient coding practices, visit The Coding College.

Leave a Comment