C++ provides a variety of collections, commonly known as containers, each designed for specific purposes. Here’s a brief overview of some of the main types of collections in C++ along with examples:

Vector (std::vector)

• A dynamic array that can grow and shrink in size.
• Example: std::vector<int> numbers = {1, 2, 3, 4, 5};

List (std::list)

• A doubly linked list that allows efficient insertion and deletion from both ends.
• Example: std::list<int> numbers = {1, 2, 3, 4, 5};

Deque (std::deque)

• A double-ended queue that supports fast insertion and deletion at both the beginning and the end.
• Example: std::deque<int> numbers = {1, 2, 3, 4, 5};

Stack (std::stack)

• Adapts other containers to provide LIFO (Last In, First Out) stack behavior.
• Example: std::stack<int> numbers; numbers.push(1); numbers.push(2);

Queue (std::queue)

• Adapts other containers to provide FIFO (First In, First Out) queue behavior.
• Example: std::queue<int> numbers; numbers.push(1); numbers.push(2);

Priority Queue (std::priority_queue)

• A max heap that allows access to the largest element, with the option to pop it off.
• Example: std::priority_queue<int> numbers; numbers.push(1); numbers.push(2);

Set (std::set)

• A collection of unique elements, sorted by keys.
• Example: std::set<int> numbers = {1, 2, 3, 4, 5};

Map (std::map)

• A sorted associative array that maps unique keys to values.
• Example: std::map<int, std::string> keyValue = {{1, "one"}, {2, "two"}};

Unordered Set (std::unordered_set)

• A hash set for storing unique elements in no particular order.
• Example: std::unordered_set<int> numbers = {1, 2, 3, 4, 5};

Unordered Map (std::unordered_map)

• A hash map that maps unique keys to values.
• Example: std::unordered_map<int, std::string> keyValue = {{1, "one"}, {2, "two"}};

Each of these collections has its own set of characteristics and use-cases. The choice of which one to use depends on factors like the need for sorting, the frequency of insertions and deletions, the importance of random access, etc.

Dynamic Collections

Dynamic collections are containers that can dynamically resize themselves to accommodate new elements or to shrink when elements are removed. They allocate memory during runtime and can change their size accordingly.

Vector (std::vector):

• Behaves like a dynamic array. It can grow and shrink in size as elements are added or removed.Example: Adding elements to a vector can cause it to resize automatically.Example:

std::vector<int> numbers;
numbers.push_back(1); // The vector grows dynamically

List (std::list):

• A doubly linked list that allows insertion and deletion of elements at any point efficiently.
• It doesn’t need contiguous memory and can grow as needed.

Deque (std::deque):

• Similar to a vector but optimized for fast insertions and deletions at both ends.
• It can grow in both directions.

Unordered Set/Map (std::unordered_set, std::unordered_map):

• These use hash tables to store elements. They can grow dynamically as elements are added.

Static Collections

Static collections, on the other hand, are those that have a fixed size that must be known at compile time. These are not as flexible as dynamic containers, as they cannot grow or shrink during runtime.

Array (std::array):

• A wrapper around native C-style arrays. It requires the size to be known at compile time and cannot change its size once created.Example:

std::array<int, 5> numbers = {1, 2, 3, 4, 5}; // Size is fixed to 5

Native C-style Arrays:

• The traditional fixed-size array in C++. They are not considered safe and flexible compared to C++ container classes but are static in size.

int numbers[5]; // Size is fixed to 5

Unidimensional Arrays

A unidimensional array is a linear sequence of elements. They are the simplest form of arrays in C++.

Declaration and Initialization:

Declaration:

• Syntax: dataType arrayName[arraySize];
• Example: int numbers[5]; // An array of 5 integers

Initialization:

• At Declaration: int numbers[5] = {1, 2, 3, 4, 5};
• After Declaration:

int numbers[5];
for(int i = 0; i < 5; i++) {
    numbers[i] = i + 1;
}

Accessing Elements:

• Elements are accessed using the index, starting from 0.
• Example: int firstNumber = numbers[0]; // Accesses the first element

Bidimensional Arrays

Bidimensional arrays are arrays of arrays, often used to represent matrices, grids, or tables.

Declaration and Initialization:

Declaration:

• Syntax: dataType arrayName[rows][columns];
• Example: int matrix[3][3]; // A 3×3 matrix

Initialization:

• At Declaration: int matrix[3][3] = { {1, 2, 3}, {4, 5, 6}, {7, 8, 9} };
• After Declaration:

int matrix[3][3];
for(int i = 0; i < 3; i++) {
    for(int j = 0; j < 3; j++) {
        matrix[i][j] = i * 3 + j + 1;
    }
}

Accessing Elements:

• Elements are accessed using two indices: one for the row and one for the column.
• Example: int element = matrix[0][1]; // Accesses the element in the first row, second column

Notes on Usage

• Memory Layout: In C++, arrays are stored in row-major order. This means in a bidimensional array, the elements of each row are stored in contiguous memory locations.
• Static Size: The size of both unidimensional and bidimensional arrays must be known at compile time (except for Variable-Length Arrays in C99, not standard in C++).
• Dynamic Arrays: For arrays where the size is determined at runtime, dynamic memory allocation (new and delete operators) or container classes like std::vector are used.
• Zero-Based Indexing: Array indexing starts at 0, so the last index of an array with n elements is n-1.

Arrays, both unidimensional and bidimensional, are foundational in C++ programming, especially when handling data sets and matrices. They provide a straightforward way to store and manipulate a fixed-size collection of elements.

Key Differences between static vs dynamic

• Memory Allocation: Dynamic collections allocate memory at runtime and can expand or contract as needed. Static collections have a fixed size determined at compile time.
• Flexibility: Dynamic collections offer more flexibility in handling data as they can adjust their size based on the program’s requirements. Static collections are limited by their predetermined size.
• Use Cases: Dynamic collections are ideal when the number of elements is not known in advance or can change. Static collections are suitable when the number of elements is fixed and known beforehand.

In summary, the choice between dynamic and static collections in C++ depends on the specific requirements of your application, particularly concerning the size of the collection and how it might change during the program’s execution.

Linked List

In C++, a simple linked list can be implemented using pointers. A linked list is a data structure consisting of nodes, where each node contains a data element and a pointer to the next node in the list. Here’s a basic implementation of a singly linked list with some fundamental operations like insertion, deletion, and traversal.

Basic Node Structure

First, define a structure for a node in the list:

struct Node {
    int data;   // Data field
    Node* next; // Pointer to the next node

    // Constructor to initialize the node
    Node(int value) : data(value), next(nullptr) {}
};

Basic Operations

Inserting at the Head:

• Adds a new node at the beginning of the list.

void insertHead(Node*& head, int value) {
    Node* newNode = new Node(value); // Create a new node
    newNode->next = head;            // Point it to the old head
    head = newNode;                  // Update the head to the new node
}

Deleting from the Head:

• Removes the node at the beginning of the list.

void deleteHead(Node*& head) {
    if (head != nullptr) {
        Node* temp = head; // Temporary pointer to the head
        head = head->next; // Update head to the next node
        delete temp;       // Delete the old head
    }
}

Traversing the List:

• Print out the elements in the list.

void printList(Node* head) {
    Node* current = head;
    while (current != nullptr) {
        std::cout << current->data << " ";
        current = current->next;
    }
    std::cout << std::endl;
}

Example Usage

void insertHead(Node*& head, int value) {
    Node* newNode = new Node(value); // 1. Create a new node
    newNode->next = head;            // 2. Set the new node's next pointer to the current head
    head = newNode;                  // 3. Update the head to point to the new node
}

int main() {
    Node* head = nullptr; // Start with an empty list

    // Insert some elements
    insertHead(head, 3);
    insertHead(head, 2);
    insertHead(head, 1);

    // Print the list
    std::cout << "The list: ";
    printList(head);

    // Delete the head
    deleteHead(head);

    // Print the list again
    std::cout << "After deleting the head: ";
    printList(head);

    // Remember to delete the remaining nodes to avoid memory leaks...
}

Example of dynamic menu using linked list

Notes

• The head pointer keeps track of the first node in the list.
• When inserting or deleting at the head, you need to update the head pointer.
• Always remember to free the memory allocated for nodes to avoid memory leaks.
• This is a basic implementation. In a more robust implementation, you might want to add more functionality, like inserting at the tail, searching for elements, etc.

This linked list implementation using pointers in C++ is a good starting point to understand how dynamic data structures are managed and manipulated at a low level.