Vector

A vector is a dynamic array that automatically resizes itself. It supports random access via the [] operator, allowing O(1) time access to any element by index. However, inserting elements at arbitrary positions is not an O(1) operation.

Declaration

#include <vector>
using namespace std;

vector<double> data; // A dynamic array of doubles
vector<CustomStruct> objects; // Can hold user-defined types
vector<vector<bool>> matrix(100); // A vector of 100 vectors

Core Operations

• size(): Returns the number of elements. O(1)
• empty(): Returns true if the vector contains no elements. O(1)
• clear(): Removes all elements.

Iterators

Iterators function like pointers to elements within the container.

vector<double>::iterator iter;

• begin(): Returns an iterator pointing to the first element.
• end(): Returns an iterator pionting past the last element.

// Traversal using indices
for (size_t idx = 0; idx < data.size(); ++idx) {
    cout << data[idx] << endl;
}

// Traversal using iterators
for (auto iter = data.begin(); iter != data.end(); ++iter) {
    cout << *iter << endl;
}

Element Access and Modification

• front(): Returns a reference to the first element.
• back(): Returns a reference to the last element.
• push_back(value): Appends an element to the end.
• pop_back(): Removes the last element.

Queue and Priority Queue

Queue

A FIFO (First-In-First-Out) data structure.

#include <queue>
queue<string> task_queue;

// Operations: O(1) complexity
queue.push("Task_A"); // Add to the back
queue.pop();          // Remove from the front
string next = queue.front(); // Access front element
string last = queue.back();  // Access back element

Priority Queue

A max-heap by default, where the largest element is always at the top.

priority_queue<int> max_heap; // Default max-heap
priority_queue<int, vector<int>, greater<int>> min_heap; // Min-heap

// Operations: O(log n) complexity
max_heap.push(30);
max_heap.pop();
int top_value = max_heap.top();

For custom types, overload the < operator for max-heap behavior.

struct Task {
    int priority;
    string name;
    bool operator < (const Task& other) const {
        return priority < other.priority; // Lower priority values are "less than"
    }
};

Deque

A double-ended queue supporting efficient insertion and deletion at both ends, along with random access.

#include <deque>
deque<char> characters;

characters.push_front('a'); // Add to front
characters.push_back('z');  // Add to back
char first = characters.front();
char last = characters.back();
characters.pop_front();
characters.pop_back();
char element = characters[5]; // Random access

Set and Multiset

Sorted associative containers implemented as balanced binary search trees (typically Red-Black Trees).

• set: Contains unique elements.
• multiset: Allows duplicate elements.

#include <set>
set<int> unique_set;
multiset<int> multi_set;

// Insertion: O(log n)
unique_set.insert(5);
multi_set.insert(5);
multi_set.insert(5); // Duplicate allowed

// Finding elements
auto pos = unique_set.find(5);
if (pos != unique_set.end()) {
    cout << "Found: " << *pos << endl;
}

// Range queries
auto lower = unique_set.lower_bound(3); // First element >= 3
auto upper = unique_set.upper_bound(8); // First element > 8

// Erasure
unique_set.erase(5); // Erase by value
multi_set.erase(pos); // Erase by iterator

Map

A container storing key-value pairs, sorted by keys.

#include <map>
map<string, int> word_count;

// Insertion
word_count.insert({"apple", 2});
word_count["banana"] = 3; // Using subscript operator

// Access
int count = word_count["apple"]; // Caution: Creates entry if key doesn't exist
auto it = word_count.find("cherry"); // Safer lookup
if (it != word_count.end()) {
    count = it->second;
}

// Iteration
for (const auto& entry : word_count) {
    cout << entry.first << ": " << entry.second << endl;
}

Bitset

A fixed-size sequence of bits, optimized for space and bit-level operations.

#include <bitset>
bitset<16> flags; // 16 bits

// Setting and resetting bits
flags.set(3);    // Set bit at position 3 to 1
flags.reset(3);  // Set bit at position 3 to 0
flags.flip(5);   // Toggle bit at position 5

// Bitwise operations
bitset<16> other_flags;
bitset<16> result = flags & other_flags; // Bitwise AND

// Queries
int set_bits = flags.count(); // Number of bits set to 1
bool any_set = flags.any();   // True if any bit is 1
bool all_zero = flags.none(); // True if all bits are 0
bool bit_value = flags[3];    // Access specific bit

Algorithm Libray

Common operations from the <algorithm> header.

Reversing and Shuffling

#include <algorithm>
vector<int> nums = {1, 2, 3, 4, 5};

reverse(nums.begin(), nums.end()); // Reverse the entire vector
random_shuffle(nums.begin(), nums.end()); // Randomly shuffle elements

Sorting and Deduplication

sort(nums.begin(), nums.end()); // Ascending order by default

// Custom comparator for descending order
sort(nums.begin(), nums.end(), [](int a, int b) { return a > b; });

// Removing consecutive duplicates
auto new_end = unique(nums.begin(), nums.end());
nums.erase(new_end, nums.end()); // Actually resize the container

Binary Search

// Requires sorted range
vector<int> sorted_data = {10, 20, 30, 40, 50};

// lower_bound: first element >= target
auto lb = lower_bound(sorted_data.begin(), sorted_data.end(), 25);
if (lb != sorted_data.end()) {
    cout << "Lower bound: " << *lb << endl; // Outputs 30
}

// upper_bound: first element > target
auto ub = upper_bound(sorted_data.begin(), sorted_data.end(), 30);
cout << "Upper bound: " << *ub << endl; // Outputs 40