techmore.in

C++ Data Structures

C++ provides a rich set of data structures that are used to store and manage data efficiently. Each data structure has its own strengths and use cases. Here’s an overview of common data structures in C++:

1. Arrays

An array is a collection of elements of the same type stored in contiguous memory locations. Arrays allow random access to elements.

Example:

cpp
#include 
using namespace std;

int main() {
    int arr[5] = {1, 2, 3, 4, 5};

    for (int i = 0; i < 5; ++i) {
        cout << arr[i] << " ";  // Output: 1 2 3 4 5
    }

    return 0;
}

2. Vectors

std::vector is a dynamic array provided by the C++ Standard Library that can grow and shrink in size. It provides random access and efficient operations for insertion and deletion.

Example:

cpp
#include 
#include 
using namespace std;

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

    vec.push_back(6);  // Add element to the end
    vec.pop_back();    // Remove last element

    for (int num : vec) {
        cout << num << " ";  // Output: 1 2 3 4 5
    }

    return 0;
}

3. Lists

std::list is a doubly linked list provided by the C++ Standard Library. It allows efficient insertion and deletion at both ends but does not support random access.

Example:

cpp
#include 
#include 
using namespace std;

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

    lst.push_front(0);  // Add element to the front
    lst.push_back(6);   // Add element to the end

    for (int num : lst) {
        cout << num << " ";  // Output: 0 1 2 3 4 5 6
    }

    return 0;
}

4. Deque

std::deque (double-ended queue) is a sequence container that allows fast insertion and deletion at both ends. It provides random access similar to vectors.

Example:

cpp
#include 
#include 
using namespace std;

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

    dq.push_front(0);  // Add element to the front
    dq.push_back(6);   // Add element to the end

    for (int num : dq) {
        cout << num << " ";  // Output: 0 1 2 3 4 5 6
    }

    return 0;
}

5. Stacks

std::stack is a container adapter that provides a LIFO (Last In, First Out) stack. Elements are added and removed from the top of the stack.

Example:

cpp
#include 
#include 
using namespace std;

int main() {
    stack<int> stk;

    stk.push(1);
    stk.push(2);
    stk.push(3);

    while (!stk.empty()) {
        cout << stk.top() << " ";  // Output: 3 2 1
        stk.pop();
    }

    return 0;
}

6. Queues

std::queue is a container adapter that provides a FIFO (First In, First Out) queue. Elements are added to the back and removed from the front.

Example:

cpp
#include 
#include 
using namespace std;

int main() {
    queue<int> q;

    q.push(1);
    q.push(2);
    q.push(3);

    while (!q.empty()) {
        cout << q.front() << " ";  // Output: 1 2 3
        q.pop();
    }

    return 0;
}

7. Priority Queues

std::priority_queue is a container adapter that provides a priority queue. It maintains elements in a way that the largest (or smallest, depending on the comparison) element is always accessible.

Example:

cpp
#include 
#include 
using namespace std;

int main() {
    priority_queue<int> pq;

    pq.push(10);
    pq.push(20);
    pq.push(5);

    while (!pq.empty()) {
        cout << pq.top() << " ";  // Output: 20 10 5
        pq.pop();
    }

    return 0;
}

8. Sets

std::set is an associative container that stores unique elements in a sorted order. It provides logarithmic time complexity for insertions, deletions, and lookups.

Example:

cpp
#include 
#include 
using namespace std;

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

    s.insert(3);  // Duplicate element is ignored
    s.insert(6);

    for (int num : s) {
        cout << num << " ";  // Output: 1 2 3 4 5 6
    }

    return 0;
}

9. Maps

std::map is an associative container that stores key-value pairs in a sorted order based on the keys. Each key is unique.

Example:

cpp
#include 
#include 
using namespace std;

int main() {
    mapint> m;
    m["apple"] = 3;
    m["banana"] = 2;
    m["cherry"] = 5;

    for (const auto& pair : m) {
        cout << pair.first << ": " << pair.second << endl;
        // Output: apple: 3
        //         banana: 2
        //         cherry: 5
    }

    return 0;
}

10. Unordered Sets and Maps

std::unordered_set and std::unordered_map are hash-based containers that provide average constant-time complexity for insertions, deletions, and lookups. They do not maintain any order.

Example of std::unordered_set:

cpp
#include 
#include 
using namespace std;

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

    us.insert(3);  // Duplicate element is ignored
    us.insert(6);

    for (int num : us) {
        cout << num << " ";  // Output order is not guaranteed
    }

    return 0;
}

Example of std::unordered_map:

cpp
#include 
#include 
using namespace std;

int main() {
    unordered_mapint> um;
    um["apple"] = 3;
    um["banana"] = 2;
    um["cherry"] = 5;

    for (const auto& pair : um) {
        cout << pair.first << ": " << pair.second << endl;
        // Output order is not guaranteed
    }

    return 0;
}

Summary:

  1. Arrays: Fixed-size collection of elements.
  2. Vectors: Dynamic arrays with resizing capabilities.
  3. Lists: Doubly linked lists allowing efficient insertions and deletions.
  4. Deque: Double-ended queue supporting fast insertion and deletion at both ends.
  5. Stacks: LIFO container adapter.
  6. Queues: FIFO container adapter.
  7. Priority Queues: Container adapter maintaining the largest (or smallest) element accessible.
  8. Sets: Sorted collection of unique elements.
  9. Maps: Sorted key-value pairs with unique keys.
  10. Unordered Sets/Maps: Hash-based containers for average constant-time complexity.

Each data structure provides different functionalities and performance characteristics, making them suitable for various tasks and scenarios in programming.