Lesson 05-C++ Containers

Container Introduction

C++ Container Overview

The C++ Standard Template Library (STL) provides a series of containers, which are predefined data structures that can be used to store and manage data of different types. The design purpose of containers is to simplify programming work and improve code reusability. C++ containers are divided into several types:

  • Sequential containers: such as std::vector, std::list, std::deque, std::forward_list.
  • Associative containers: such as std::set, std::map, std::multiset, std::multimap.
  • Unordered containers (hash-based): such as std::unordered_set, std::unordered_map, std::unordered_multiset, std::unordered_multimap.
  • Container adapters: such as std::stack, std::queue, std::priority_queue.

These containers have predefined behaviors, support various operations such as insertion, deletion, lookup, etc., and provide efficient implementations.

Importance of Containers

The importance of containers is reflected in the following aspects:

  • Code reuse: Since containers are generic and can be used with multiple data types, they greatly reduce the workload of writing new code.
  • Ease of use: Containers provide rich interfaces and member functions, making common data operations much simpler.
  • Performance optimization: Containers are carefully designed to provide the best performance. For example, std::vector is optimized in memory allocation to reduce memory fragmentation.
  • Safety: Containers usually perform boundary checks, thus avoiding some common errors, such as array out-of-bounds.
  • Portability: The implementation of containers is standardized, which means they can be used on different platforms without changing the code.

Why Use Containers Instead of Traditional Data Structures

Reasons for using C++ containers instead of traditional data structures include:

  • Ease of use: Containers provide rich APIs, making data operations more convenient.
  • Efficiency: Containers are usually more efficient than manually implemented data structures because they are optimized for performance.
  • Safety: Containers usually perform boundary checks to help prevent common programming errors.
  • Portability: Containers follow the C++ standard, which means they can be used with different compilers and platforms.
  • Maintainability: Using containers can reduce the amount of code, making programs easier to maintain.
  • Consistency: Containers provide consistent interfaces, which helps maintain code style consistency.

Container Examples

Here is a simple example showing how to use std::vector and std::map:

#include <iostream>
#include <vector>
#include <map>

int main() {
    // Use vector to store integers
    std::vector<int> numbers = {1, 2, 3, 4, 5};

    // Add an element
    numbers.push_back(6);

    // Output elements in vector
    for (int num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // Use map to store string-to-integer mappings
    std::map<std::string, int> ageMap = {
        {"Alice", 30},
        {"Bob", 25},
        {"Charlie", 35}
    };

    // Update the value for a key
    ageMap["Alice"] = 31;

    // Output key-value pairs in map
    for (const auto& pair : ageMap) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    return 0;
}

Container Classification

Sequential Containers

Sequential Container Types

Container TypeDescription
vectorVariable-size array. Supports fast random access. Inserting or deleting elements at positions other than the tail can be slow.
dequeDouble-ended queue. Supports fast random access. Inserting/deleting at head or tail is very fast.
listDoubly linked list. Only supports bidirectional sequential access. Inserting/deleting at any position in list is very fast.
forward_listSingly linked list. Only supports unidirectional sequential access. Inserting/deleting at any position in the list is very fast.
arrayFixed-size array. Supports fast random access. Cannot add or delete elements.
stringA container similar to vector, but specialized for holding characters. Fast random access. Fast insertion/deletion at the tail.
  • Except for the fixed-size array, other containers provide efficient and flexible memory management.
  • forward_list and array are types added in the new C++ standard.
  • Usually, using vector is the best choice unless you have a very good reason to choose another container.
  • The new standard library containers are much faster than the old versions.

Sequential containers store data in the order of insertion. These containers provide random access capability, meaning any position can be accessed directly via index. Sequential containers include:

  • std::vector: Dynamic array, supports fast random access and tail insertion/deletion operations.
#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> v = {1, 2, 3, 4, 5};
    v.push_back(6);
    v.insert(v.begin(), 0);

    v.pop_back();
    v.erase(v.begin());

    auto it = std::find(v.begin(), v.end(), 3);
    if (it != v.end()) {
        std::cout << "Found element 3 at index " << std::distance(v.begin(), it) << std::endl;
    }

    for (int num : v) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}
  • std::list: Doubly linked list, supports fast insertion/deletion at any position.
#include <iostream>
#include <list>
#include <algorithm>

int main() {
    std::list<int> l = {1, 2, 3, 4, 5};
    l.push_back(6);
    l.push_front(0);

    l.pop_back();
    l.pop_front();

    auto it = std::find(l.begin(), l.end(), 3);
    if (it != l.end()) {
        std::cout << "Found element 3" << std::endl;
    }

    for (int num : l) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}
  • std::deque: Double-ended queue, supports fast insertion/deletion at both ends.
#include <iostream>
#include <deque>
#include <algorithm>

int main() {
    std::deque<int> d = {1, 2, 3, 4, 5};
    d.push_back(6);
    d.push_front(0);

    d.pop_back();
    d.pop_front();

    auto it = std::find(d.begin(), d.end(), 3);
    if (it != d.end()) {
        std::cout << "Found element 3 at index " << std::distance(d.begin(), it) << std::endl;
    }

    for (int num : d) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}
  • std::forward_list: Singly linked list, supports fast head insertion operations.
#include <iostream>
#include <forward_list>
#include <algorithm>

int main() {
    std::forward_list<int> fl = {1, 2, 3, 4, 5};
    fl.push_front(0);

    fl.pop_front();

    auto it = std::find(fl.begin(), fl.end(), 3);
    if (it != fl.end()) {
        std::cout << "Found element 3" << std::endl;
    }

    for (int num : fl) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

Associative Containers

Associative Container Types:

Container TypeExplanation
Stored in order
mapKey array: holds keyword-value pairs
setKeyword is the value, i.e., a container that only holds keywords
multimapA map that supports the same key appearing multiple times
multisetA set that supports the same key appearing multiple times
Unordered collections
unordered_mapA map organized with a hash function
unordered_setA set organized with a hash function
unordered_multimapA hash-organized map, where keywords can appear repeatedly
unordered_multisetA hash-organized set, where keywords can appear repeatedly

Associative containers store data based on key-value pairs and automatically maintain element ordering. These containers typically use balanced trees (such as red-black trees) as the underlying data structure to ensure logarithmic time complexity for lookup, insertion, and deletion operations. Associative containers include:

  • std::set: Sorted collection, does not allow duplicate elements.
#include <iostream>
#include <set>

int main() {
    std::set<int> s = {1, 2, 3, 4, 5};
    s.insert(6);

    s.erase(6);

    auto it = s.find(3);
    if (it != s.end()) {
        std::cout << "Found element 3" << std::endl;
    }

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

    return 0;
}
  • std::multiset: Sorted collection, allows duplicate elements.
#include <iostream>
#include <set>

int main() {
    std::multiset<int> ms = {1, 2, 3, 2, 4, 3};
    ms.insert(5);

    ms.erase(ms.find(5));

    auto it = ms.find(3);
    if (it != ms.end()) {
        std::cout << "Found element 3" << std::endl;
    }

    for (int num : ms) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}
  • std::map: Sorted key-value pair mapping, does not allow duplicate keys.
#include <iostream>
#include <map>

int main() {
    std::map<std::string, int> m = {{"one", 1}, {"two", 2}, {"three", 3}};
    m["four"] = 4;

    m.erase("four");

    auto it = m.find("three");
    if (it != m.end()) {
        std::cout << "Found element three with value " << it->second << std::endl;
    }

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

    return 0;
}
  • std::multimap: Sorted key-value pair mapping, allows duplicate keys.

In C++11, hash-based unordered containers were introduced, providing average constant-time complexity for lookup, insertion, and deletion operations:

  • std::unordered_set: Hash-based collection, does not allow duplicate elements.
#include <iostream>
#include <unordered_set>

int main() {
    std::unordered_set<int> us = {1, 2, 3, 4, 5};
    us.insert(6);

    us.erase(6);

    auto it = us.find(3);
    if (it != us.end()) {
        std::cout << "Found element 3" << std::endl;
    }

    for (int num : us) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}
  • std::unordered_multiset: Hash Hash-based collection, allows duplicate elements.
#include <iostream>
#include <unordered_set>

int main() {
    std::unordered_multiset<int> ums = {1, 2, 3, 2, 4, 3};
    ums.insert(5);

    ums.erase(5);

    auto count = ums.count(3);
    std::cout << "Element 3 appears " << count << " times." << std::endl;

    for (int num : ums) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}
  • std::unordered_map: Hash-based key-value pair mapping, does not allow duplicate keys.
#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<std::string, int> um = {{"one", 1}, {"two", 2}, {"three", 3}};
    um["four"] = 4;

    um.erase("four");

    auto it = um.find("three");
    if (it != um.end()) {
        std::cout << "Found element three with value " << it->second << std::endl;
    }

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

    return 0;
}
  • std::unordered_multimap: Hash-based key-value pair mapping, allows duplicate keys.
#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_multimap<std::string, int> umm = {{"one", 1}, {"two", 2}, {"three", 3}, {"two", 2}};
    umm.insert({"four", 4});

    umm.erase("four");

    auto range = umm.equal_range("two");
    for (auto it = range.first; it != range.second; ++it) {
        std::cout << "Found element two with value " << it->second << std::endl;
    }

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

    return 0;
}

Container Adapters

Container adapters are encapsulations of existing containers, providing specific operation interfaces without changing the behavior of the underlying container. Container adapters include:

  • std::stack: Last-in, first-out (LIFO) container.
#include <iostream>
#include <stack>

int main() {
    std::stack<int> st;
    st.push(1);
    st.push(2);
    st.push(3);

    int topElement = st.top();
    std::cout << "Top element is: " << topElement << std::endl;

    st.pop();
    topElement = st.top();
    std::cout << "New top element is: " << topElement << std::endl;

    return 0;
}
  • std::queue: First-in, first-out (FIFO) container.
#include <iostream>
#include <queue>

int main() {
    std::queue<int> q;
    q.push(1);
    q.push(2);
    q.push(3);

    int frontElement = q.front();
    std::cout << "Front element is: " << frontElement << std::endl;

    q.pop();
    frontElement = q.front();
    std::cout << "New front element is: " << frontElement << std::endl;

    return 0;
}
  • std::priority_queue: Priority queue, always pops the element with the highest priority.
#include <iostream>
#include <queue>

int main() {
    std::priority_queue<int> pq;
    pq.push(3);
    pq.push(1);
    pq.push(2);

    int topElement = pq.top();
    std::cout << "Top element is: " << topElement << std::endl;

    pq.pop();
    topElement = pq.top();
    std::cout << "New top element is: " << topElement << std::endl;

    return 0;
}

Sequential Containers

  • Sequential container: Provides programmers with the ability to control the storage and access order of elements. This order does not depend on the value of the elements, but corresponds to the position when the elements are added to the container.

Sequential Container Types

Container TypeDescription
vectorVariable-size array. Supports fast random access. Inserting or deleting elements at positions other than the tail can be slow.
dequeDouble-ended queue. Supports fast random access. Inserting/deleting at head or tail is very fast.
listDoubly linked list. Only supports bidirectional sequential access. Inserting/deleting at any position in list is very fast.
forward_listSingly linked list. Only supports unidirectional sequential access. Inserting/deleting at any position in the list is very fast.
arrayFixed-size array. Supports fast random access. Cannot add or delete elements.
stringA container similar to vector, but specialized for holding characters. Fast random access. Fast insertion/deletion at the tail.
  • Except for the fixed-size array, other containers provide efficient and flexible memory management.
  • forward_list and array are types added in the new C++ standard.
  • Usually, using vector is the best choice unless you have a very good reason to choose another container.
  • The new standard library containers are much faster than the old versions.
  • forward_list does not have the size operation; for other containers, size is guaranteed to be a fast constant-time operation.

Container Operations

Type Aliases

OperationExplanation
iteratorIterator type for this container type
const_iteratorIterator type that can read elements but cannot modify them
size_typeUnsigned integer type, sufficient to hold the maximum possible size of this container type
difference_typeSigned integer type, sufficient to hold the distance between two iterators
value_typeElement type
referenceLvalue type of the element; same meaning as value_type &
const_referenceconst lvalue type of the element, i.e., const value_type &

Constructors

OperationExplanation
C c;Default constructor, constructs an empty container
C c1(c2); or C c1 = c2;Constructs c1 as a copy of c2
C c(b, e)Constructs c, copying all elements in the range specified by iterators b and e into c
C c{a, b, c...}List-initializes c
C c(n)Only supports sequential containers, excluding array, contains n value-initialized elements
C c(n, t)Same as above, contains n elements with initial value t
  • Only sequential container constructors accept size parameters; associative containers do not support this.
  • array has a fixed size.
  • Unlike other containers, a default-constructed array is non-empty.
  • Direct copy: When copying one container to another, the types must match: both container type and element type must be the same.
  • Iterator copy: Does not require container types to be the same, and element types within containers can also differ.

Assignment and swap

OperationExplanation
c1 = c2;Replaces elements in c1 with elements from c2
c1 = {a, b, c...}Replaces elements in c1 with elements from the list (not applicable to array)
c1.swap(c2)Swaps the elements of c1 and c2
swap(c1, c2)Equivalent to c1.swap(c2)
c.assign(b, e)Replaces elements in c with elements in the range indicated by iterators b and e; b and e cannot point to elements in c
c.assign(il)Replaces elements in c with elements from the initializer list il
c.assign(n, r)Replaces elements in c with n elements with value t
  • Using the non-member version of swap is a good habit.
  • assign operation is not applicable to associative containers and array

Size

OperationExplanation
c.size()Number of elements in c (not supported by forward_list)
c.max_size()Maximum number of elements c can hold
c.empty()Returns false if c stores elements, otherwise returns true

The above container operations, unless specifically indicated (bolded), apply to all containers;

The following container operations are specific to sequential containers (with some exceptions)

Adding Elements

OperationExplanation
c.push_back(t)Creates an element with value t at the tail of c, returns void
c.emplace_back(args)Creates an element constructed from args at the tail of c, returns void
c.push_front(t)Creates an element with value t at the head of c, returns void. vector does not support
c.emplace_front(args)Same as above
c.insert(p, t)Creates an element with value t before the element pointed to by iterator p, returns an iterator to the newly added element
c.emplace(p, args)Same as above
c.inset(p, n, t)Inserts n elements with value t before the element pointed to by iterator p, returns an iterator to the first new element; if n is 0, returns p
c.insert(p, b, e)Inserts elements in the range of iterators b and e before the element pointed to by p; returns an iterator to the first new element, if the range is empty, returns p. b and e cannot point to elements in p
c.insert(p, il)il is a braced list of element values, inserts them before the element pointed to by p; returns an iterator to the first new element, if il is empty, returns p
  • Because these operations change the size, they are not applicable to array.
  • forward_list has its own specialized versions of insert and emplace.
  • forward_list does not support push_back and emplace_back.
  • When we initialize a container with an object or insert an object into a container, what is actually placed is a copy of the object.
  • Functions starting with emplace are introduced in the new standard; these operations construct rather than copy elements.
  • The parameters passed to emplace must match the constructor of the element type.
  • Inserting elements into a vector, string, or deque invalidates all iterators, references, and pointers to the container.

Accessing Elements

OperationExplanation
c.back()Returns a reference to the tail element of c. If c is empty, the function behavior is undefined
c.front()Returns a reference to the head element of c. If c is empty, the function behavior is undefined
c[n]Returns a reference to the element with index n in c, where n is an unsigned integer. If n >= c.size(), the function behavior is undefined
c.at(n)Returns a reference to the element with index n. If the index is out of bounds, throws an out_of_range exception
  • Access member functions return references.
  • at and subscript operations are only applicable to string, vector, deque, array.
  • back is not applicable to forward_list.
  • If you want to ensure the index is legal, you can use the at function.

Deleting Elements

OperationExplanation
c.pop_back()Deletes the tail element of c. If c is empty, the function behavior is undefined. Returns void
c.pop_front()Deletes the head element of c. If c is empty, the function behavior is undefined. Returns void
c.erase(p)Deletes the element pointed to by iterator p, returns an iterator to the element after the deleted one; if p is the past-the-end iterator, the function behavior is undefined
c.erase(b, e)Deletes elements in the range of iterators b and e, returns an iterator to the element after the last deleted element; if e is the past-the-end iterator, returns the past-the-end iterator
c.clear()Deletes all elements in c, returns void
  • Changes container size, not applicable to array.
  • forward_list has a special version of erase
  • forward_list does not support pop_back
  • vector and string do not support pop_front

Special forward_list Operations

  • When deleting an element from a linked list, the content of the preceding node needs to be modified. Doubly linked lists store predecessor pointers, but singly linked lists do not, so a method to obtain the preceding node is needed.
  • forward_list defines before_begin, which is the off-the-beginning iterator, allowing addition or deletion of elements before the first element.
OperationExplanation
lst.before_begin()Returns an iterator pointing to a non-existent element before the first element of the list; this iterator cannot be dereferenced.
lst.cbefore_begin()Same as above, but returns a constant iterator const_iterator.
lst.insert_after(p, t)Inserts an element after iterator p, t is an object. If p is the past-the-end iterator, the function behavior is undefined
lst.insert_after(p, n, t)n is the count. If n is 0, the function behavior is undefined
lst.insert_after(p, b, e)b and e are a pair of iterators indicating a range, cannot point to elements in lst. If the range is empty, returns p
lst.insert_after(p, il)il is a braced initializer list.
emplace_after(p, args)Uses args to create an element after position p, returns an iterator to the new element. If p is the past-the-end iterator, the function behavior is undefined.
lst.erase_after(p)Deletes the element after the position pointed to by p, returns an iterator to the element after the deleted one. If p points to the tail element of lst or is a past-the-end iterator, the function behavior is undefined.
lst.erase_after(b, e)Similar to above, but deletes the range specified from b to e.

Changing Container Size

OperationExplanation
c.resize(n)Adjusts the size of c to n elements. If n < c.size(), excess elements are discarded. If new elements must be added, they are value-initialized
c.resize(n, t)Adjusts the size of c to n elements, any newly added elements are initialized to value t
  • resize is not applicable to array

Obtaining Iterators

OperationExplanation
c.begin(), c.end()Returns iterators pointing to the first element and the position after the last element of c
c.cbegin(), c.cend()Returns const_iterator
  • Versions starting with c are introduced in the C++11 new standard
  • When write access is not needed, cbegin and cend should be used
  • For arrays that are not class types, the non-member functions begin() and end() should be used

Extra Members of Reverse Containers

OperationExplanation
reverse_iteratorIterator that addresses elements in reverse order
const_reverse_iteratorReverse iterator that cannot modify elements
c.rbegin(), c.rend()Returns iterators pointing to the tail element and the position before the first element of c
c.crbegin(), c.crend()Returns const_reverse_iterator
  • Not supported by forward_list

Iterators

  • Iterator range: begin to end, i.e., the first element to the position after the last element.
  • Left-closed interval: [begin, end)
  • Programming conventions implied by the left-closed range:
    • If begin and end are equal, the range is empty.
    • If they are not equal, the range contains at least one element, and begin points to the first element in the range.
    • begin can be incremented several times to make begin == end.

Container Operations May Invalidate Iterators

  • After adding elements to a container:
    • If the container is vector or string, and storage space is reallocated, iterators, pointers, and references to the container become invalid. If storage space is not reallocated, those pointing before the insertion position remain valid, those after become invalid.
    • For deque, inserting at any position except head or tail invalidates iterators, pointers, and references to the container. If adding at head or tail, iterators become invalid, but references and pointers to existing elements do not.
    • For list and forward_list, iterators, pointers, and references to the container remain valid.
  • After deleting an element from a container:
    • For list and forward_list, iterators, references, and pointers to other positions in the container remain valid.
    • For deque, if deleting at any position except head or tail, iterators, pointers, and references to elements other than the deleted one become invalid; if deleting the tail element of deque, the past-the-end iterator becomes invalid, but others are unaffected; if deleting the head element, these are also unaffected.
    • For vector and string, iterators, references, and pointers to elements before the deleted one remain valid.
    • Note: When deleting an element, the past-the-end iterator always becomes invalid.
    • Note: Using invalid iterators, pointers, or references is a serious runtime error!
    • Suggestion: Minimize code segments that require iterators to remain valid.
    • Suggestion: Do not save the iterator returned by end, because the past-the-end iterator always becomes invalid.

Type Constraints for Elements in Containers

  • Element type must support assignment operations;
  • Objects of the element type must be copyable;
  • If relational operators are needed to compare two containers, the element type should define the corresponding comparison operators.
  • Except for input/output standard library types, all other standard library types are valid container element types.

std::array

Definition: std::array is a fixed-size array container that provides a safe way to handle fixed-size arrays.

Usage Scenarios: Use std::array when you need a fixed-size array and do not want to change its size at runtime.

Example Code:

#include <iostream>
#include <array>

int main() {
    std::array<int, 5> arr = {1, 2, 3, 4, 5};

    // Access element
    std::cout << "Element at index 2: " << arr[2] << std::endl;

    // Traverse
    for (const auto& elem : arr) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    return 0;
}

std::vector

Definition: std::vector is a dynamic array that can change its size at runtime.

Memory Management: std::vector internally uses a contiguous block of memory to store elements. When capacity is insufficient, it reallocates a larger memory space and copies the old data to the new location.

Performance Considerations:

  • Inserting and deleting elements in the middle may cause other elements to move, so performance is poor.
  • Insertion and deletion at the end perform well because no other elements need to be moved.

Example Code:

#include <iostream>
#include <vector>

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

    // Add element at the end
    vec.push_back(6);

    // Access element
    std::cout << "Element at index 2: " << vec[2] << std::endl;

    // Traverse
    for (const auto& elem : vec) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    return 0;
}

std::list

Definition: std::list is a doubly linked list container that provides efficient insertion and deletion operations.

Insertion and Deletion Operations:

  • Insertion and deletion operations usually take constant time O(1) because they only involve pointer updates.

Example Code:

#include <iostream>
#include <list>

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

    // Add element at the end of the list
    lst.push_back(6);

    // Add element at the beginning of the list
    lst.push_front(0);

    // Access element
    auto it = lst.begin();
    std::advance(it, 2);  // Move iterator to the third element
    std::cout << "Element at index 2: " << *it << std::endl;

    // Traverse
    for (const auto& elem : lst) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    return 0;
}

std::forward_list

Definition:

  • std::forward_list is a singly linked list container, similar to std::list, but only provides unidirectional iterators.

Performance Characteristics:

  • Singly linked lists save more space than doubly linked lists because they do not need extra pointers to maintain reverse links.
  • Insertion and deletion operations usually take constant time O(1) because they only involve pointer updates.

Example Code:

#include <iostream>
#include <forward_list>

int main() {
    std::forward_list<int> flst = {1, 2, 3, 4, 5};

    // Add element at the end of the list
    flst.push_front(0);

    // Access element
    auto it = flst.begin();
    std::advance(it, 2);  // Move iterator to the third element
    std::cout << "Element at index 2: " << *it << std::endl;

    // Traverse
    for (const auto& elem : flst) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    return 0;
}

std::deque

Definition:

  • std::deque is a double-ended queue container that can efficiently insert and delete elements at both ends.

Memory Layout:

  • std::deque uses multiple fixed-size arrays to implement, each array is called a segment; this layout allows efficient insertion and deletion at both ends.

Performance Characteristics:

  • Inserting and deleting elements at both ends is very fast, usually taking constant time O(1).
  • Insertion and deletion in the middle may be slower because segments may need to be reallocated.

Example Code:

#include <iostream>
#include <deque>

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

    // Add element at the front
    deq.push_front(0);

    // Add element at the back
    deq.push_back(6);

    // Access element
    std::cout << "Element at index 2: " << deq[2] << std::endl;

    // Traverse
    for (const auto& elem : deq) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    return 0;
}

Associative Containers

  • Associative containers differ from sequential containers: elements in associative containers are saved and accessed according to keywords.
  • Associative containers support efficient lookup and reading of elements by keyword; the basic associative container types are map and set.

Associative Container Types:

Container TypeExplanation
Stored in ordermap and multimap: include <map>;
set and multiset: include <set>;
mapKey array: holds keyword-value (key-value) pairs
setKeyword is the value, i.e., a container that only holds keywords
multimapA map where keywords (key) can appear repeatedly
multisetA set where keywords (key) can appear repeatedly
Unordered collectionsinclude <unordered_map>;
include <unordered_set>;
unordered_mapA map organized with a hash function
unordered_setA set organized with a hash function
unordered_multimapA hash-organized map, where keywords can appear repeatedly
unordered_multisetA hash-organized set, where keywords can appear repeatedly
  • Each of the above containers:
    • Is either a set or a map
    • Either requires unique keywords (key) or allows duplicate keywords
    • Either stores elements in order or stores them unordered
  • Containers that allow duplicate keywords include multi in their names
  • Containers with unordered storage start with the word unordered

Defining Associative Containers

  • Need to specify the element type.
  • List initialization:
    • map: map<string, int> word_count = {{"a", 1}, {"b", 2}};
    • set: set<string> exclude = {"the", "a"};

Requirements for Keyword Types

  • For ordered containers, the standard library uses the keyword type (key)‘s < operator by default to compare two elements.
  • If you want to pass a comparison function, you can define it like this:
bool compareIsbn(const Sales_data &lhs, const Sales_data &rhs){
  return lhs.isbn() < rhs.isbn();
}

// bookstore can have multiple records with the same ISBN, elements are arranged in ISBN order
// Use &compareIsbn to initialize the bookstore object, meaning that when adding elements to bookstore,
// call compareIsbn to sort these elements
multiset<Sales_data, decltype(compareIsbn)*>
  bookstore(&compareIsbn);

pair

  • Defined in the utility header file.
  • A pair holds two data members, and the two types are not required to be the same.
  • When extracting an element from a map, for example for(auto &w : word_count) gets an object of type pair, i.e., w is a pair. (More directly, each element in a map is actually a pair)
OperationExplanation
pair<T1, T2> p;p is a pair, with members of types T1 and T2 respectively, both value-initialized.
pair<T1, T2> p(v1, v2);first and second members are initialized with v1 and v2 respectively.
pair<T1, T2>p = {v1, v2};Equivalent to p(v1, v2)
make_pair(v1, v2);Returns a pair initialized with v1 and v2, the pair type is inferred from the types of v1 and v2
p.firstReturns the data member named first of p.
p.secondReturns the data member named second of p.
p1 relop p2Relational operators (<, >, <=, >=) are defined in dictionary order. Similar to string comparison, for example, when p1.first < p2.first or p1.first == p2.first and p1.second < p2.second, then p1 < p2
p1 == p2Both pairs of elements must be equal
p1 != p2Same as above
// Function returning a pair object
pair<string, int>
process(vector<string> &v){
    // Process v
    if(!v.empty())
        // List initialization, C++11
        return {v.back(), v.back().size()};
    	// Can also use make_pair to generate a pair object
    	//return pair<string, int>(v.back(), v.back().size());
    else
        return pair<string, int>();// Implicitly construct return value
}

Associative Container Operations

Extra Type Aliases for Associative Containers:

Type AliasExplanation
key_typeKeyword type for this container type
mapped_typeType associated with each keyword, only applicable to map
value_typeFor map, it is pair<const key_type, mapped_type>; for set, it is the same as key_type.
  • For map, note that mapped_type differs from value_type

Associative Container Iterators

  • Dereferencing an associative container iterator yields a reference to a value of the container’s value_type.
  • set iterators are const. A set iterator can be used to read an element’s value, but cannot modify it.
  • Traversing an associative container: Using begin and end, when traversing map, multimap, set, multiset, iterators traverse elements in ascending keyword order.

Usually do not use generic algorithms with associative containers

  1. Elements in set are const, elements in map are pair, where the first member is const;
  2. Can be used with algorithms that only read elements, but usually not efficient;
  3. If really needed, either use it as a source sequence or as a destination. For example, use the generic copy to copy elements from one associative container to another sequence.

insert Adding Elements

Adding elements to map:

  • word_count.insert({word, 1});
  • word_count.insert(make_pair(word, 1));
  • word_count.insert(pair<string, size_t>(word, 1));
  • word_count.insert(map<string, size_t>::value_type (word, 1));
insert OperationAssociative Container
c.insert(v) c.emplace(args)v is an object of value_type type; args is used to construct an element.
For map and set, only insert or construct the element if the keyword does not exist in c.
The function returns a pair containing an iterator pointing to the element with the specified keyword and a bool value indicating whether the insertion was successful.
For multimap and multiset, every given element is inserted and an iterator to the new element is returned.
c.insert(b, e) c.insert(il)b and e are iterators indicating a range of c::value_type type values; il is a braced list. The function returns void. For map and set, only elements whose keywords are not in c are inserted.
c.insert(p, v) c.emplace(p, args)Similar to insert(v), but uses iterator p as a hint to indicate where to start searching for the storage position of the new element. Returns an iterator pointing to the element with the given keyword.

erase Deleting Elements

OperationExplanation
c.erase(k)Deletes every element with keyword k from c. Returns a size_type value indicating the number of deleted elements.
c.erase(p)Deletes the element specified by iterator p from c. p must point to a real element in c, cannot be c.end(). Returns an iterator to the element after p; if p points to the tail element in c, returns c.end()
c.erase(b, e)Deletes elements in the range indicated by iterator pair b and e. Returns e.

Subscript Operations for map

OperationExplanation
c[k]Returns the element with keyword k; if k is not in c, adds an element with keyword k, value-initialized.
c.at(k)Accesses the element with keyword k, with parameter checking; if k does not exist in c, throws an out_of_range exception.
  • Supports map and unordered_map, set types do not support subscript
  • Cannot perform subscript operations on “multi” maps because there may be multiple values associated with one keyword
  • Usually, the type returned by dereferencing an iterator is the same as that returned by the subscript operator, but for map: subscript operation obtains a mapped_type, while dereferencing obtains a value_type

Finding Elements

OperationExplanation
c.find(k)Returns an iterator pointing to the first element with keyword k; if k is not in the container, returns the past-the-end iterator
c.count(k)Returns the number of elements with keyword equal to k. For containers that do not allow duplicate keywords, the return value is always 0 or 1
c.lower_bound(k)Returns an iterator pointing to the first element with keyword not less than k
c.upper_bound(k)Returns an iterator pointing to the first element with keyword greater than k
c.equal_range(k)Returns an iterator pair indicating the range of elements with keyword equal to k. If k does not exist, both members of the pair equal c.end().
  • lower_bound and upper_bound are not applicable to unordered containers
  • Subscript and at operations are only applicable to non-const map and unordered_map
  • If a multimap or multiset has multiple elements with a given keyword, these elements are stored adjacently

std::set

Definition:

  • std::set is a sorted collection container where elements are not allowed to repeat.

Lookup Performance:

  • Average lookup performance is O(log n), where n is the number of elements in the container.

Example Code:

#include <iostream>
#include <set>

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

    // Insert element
    s.insert(6);

    // Find element
    auto it = s.find(3);
    if (it != s.end()) {
        std::cout << "Found element 3" << std::endl;
    }

    // Traverse
    for (const auto& elem : s) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    return 0;
}

std::multiset

Definition:

  • std::multiset is a sorted collection container that allows element repetition.

Example Code:

#include <iostream>
#include <set>

int main() {
    std::multiset<int> ms = {1, 2, 3, 2, 4, 3};

    // Insert element
    ms.insert(5);

    // Find element
    auto it = ms.find(3);
    if (it != ms.end()) {
        std::cout << "Found element 3" << std::endl;
    }

    // Traverse
    for (const auto& elem : ms) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    return 0;
}

std::map

Definition:

  • std::map is a key-value pair mapping container where keys are unique.

Sorting Basis:

  • Keys are sorted in ascending order.

Example Code:

#include <iostream>
#include <map>

int main() {
    std::map<std::string, int> m = {{"one", 1}, {"two", 2}, {"three", 3}};

    // Insert element
    m["four"] = 4;

    // Find element
    auto it = m.find("two");
    if (it != m.end()) {
        std::cout << "Found element two with value " << it->second << std::endl;
    }

    // Traverse
    for (const auto& pair : m) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    return 0;
}

std::multimap

Definition:

  • std::multimap is a key-value pair mapping container that allows key repetition.

Example Code:

#include <iostream>
#include <map>

int main() {
    std::multimap<std::string, int> mm = {{"one", 1}, {"two", 2}, {"three", 3}, {"two", 2}};

    // Insert element
    mm.insert({"four", 4});

    // Find element
    auto range = mm.equal_range("two");
    for (auto it = range.first; it != range.second; ++it) {
        std::cout << "Found element two with value " << it->second << std::endl;
    }

    // Traverse
    for (const auto& pair : mm) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    return 0;
}

std::unordered_set

Definition:

  • std::unordered_set is a hash-based collection container where elements are not allowed to repeat.

Average Lookup Performance:

  • Average lookup performance is close to O(1).

Example Code:

#include <iostream>
#include <unordered_set>

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

    // Insert element
    us.insert(6);

    // Find element
    if (us.count(3)) {
        std::cout << "Found element 3" << std::endl;
    }

    // Traverse
    for (const auto& elem : us) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    return 0;
}

std::unordered_multiset

Definition:

  • std::unordered_multiset is a hash-based collection container that allows element repetition.

Example Code:

#include <iostream>
#include <unordered_set>

int main() {
    std::unordered_multiset<int> ums = {1, 2, 3, 2, 4, 3};

    // Insert element
    ums.insert(5);

    // Find element
    auto count = ums.count(3);
    std::cout << "Element 3 appears " << count << " times." << std::endl;

    // Traverse
    for (const auto& elem : ums) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    return 0;
}

std::unordered_map

Definition:

  • std::unordered_map is a hash-based key-value pair mapping container where keys are unique.

Example Code:

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<std::string, int> um = {{"one", 1}, {"two", 2}, {"three", 3}};

    // Insert element
    um["four"] = 4;

    // Find element
    auto it = um.find("two");
    if (it != um.end()) {
        std::cout << "Found element two with value " << it->second << std::endl;
    }

    // Traverse
    for (const auto& pair : um) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    return 0;
}

std::unordered_multimap

Definition:

  • std::unordered_multimap is a hash-based key-value pair mapping container that allows key repetition.

Example Code:

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_multimap<std::string, int> umm = {{"one", 1}, {"two", 2}, {"three", 3}, {"two", 2}};

    // Insert element
    umm.insert({"four", 4});

    // Find element
    auto range = umm.equal_range("two");
    for (auto it = range.first; it != range.second; ++it) {
        std::cout << "Found element two with value " << it->second << std::endl;
    }

    // Traverse
    for (const auto& pair : umm) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    return 0;
}

Container Adapters

std::stack

Definition:

  • std::stack is a last-in, first-out (LIFO) container adapter.

Example Code:

#include <iostream>
#include <stack>

int main() {
    std::stack<int> s;

    // Push elements
    s.push(1);
    s.push(2);
    s.push(3);

    // Pop elements
    while (!s.empty()) {
        std::cout << s.top() << " ";
        s.pop();
    }
    std::cout << std::endl;

    return 0;
}

std::queue

Definition:

  • std::queue is a first-in, first-out (FIFO) container adapter.

Example Code:

#include <iostream>
#include <queue>

int main() {
    std::queue<int> q;

    // Enqueue elements
    q.push(1);
    q.push(2);
    q.push(3);

    // Dequeue elements
    while (!q.empty()) {
        std::cout << q.front() << " ";
        q.pop();
    }
    std::cout << std::endl;

    return 0;
}

std::priority_queue

Definition:

  • std::priority_queue is a priority queue container adapter that allows specifying priority ordering rules, with a max-heap by default.

Example Code:

#include <iostream>
#include <queue>

int main() {
    std::priority_queue<int> pq;

    // Enqueue elements
    pq.push(1);
    pq.push(2);
    pq.push(3);
    pq.push(4);

    // Dequeue elements
    while (!pq.empty()) {
        std::cout << pq.top() << " ";
        pq.pop();
    }
    std::cout << std::endl;

    return 0;
}

Container Operations

Iterators

Iterator Concept:

An iterator is an object that can point to elements in a container and be used to traverse the elements within the container.

Types of Iterators:

Iterators are divided into five basic types:

  • Input iterator
  • Output iterator
  • Forward iterator
  • Bidirectional iterator
  • Random access iterator

Each container provides corresponding iterator types:

  • vector, deque: Random access iterators
  • list: Bidirectional iterators
  • set, map: Bidirectional iterators
  • unordered_set, unordered_map: Do not support random access iterators, but provide iterators

How to Use Iterators:

  • Iterators are typically obtained through the container’s member functions begin() and end().
  • Use iterators for accessing, modifying, and deleting elements.

Example Code:

#include <iostream>
#include <vector>

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

    // Traverse using iterator
    for (auto it = v.begin(); it != v.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    // Modify elements
    for (auto it = v.begin(); it != v.end(); ++it) {
        *it *= 2;
    }

    // Traverse again
    for (auto it = v.begin(); it != v.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    return 0;
}

Algorithms

STL Algorithm Overview:

  • STL provides a series of generic algorithms, all of which are function templates that can work with different types of containers.
  • Common algorithms include: sort, find, copy, reverse, accumulate, etc.

Common Algorithm Examples:

  • Sorting (std::sort): Sorts elements in the container.
  • Searching (std::find): Finds a specific element in the container.
  • Copying (std::copy): Copies elements from one container to another container or array.
  • Reversing (std::reverse): Reverses the order of elements in the container.

Example Code:

#include <iostream>
#include <vector>
#include <algorithm>

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

    // Sort
    std::sort(v.begin(), v.end());

    // Find
    auto it = std::find(v.begin(), v.end(), 3);
    if (it != v.end()) {
        std::cout << "Found element 3 at position: " << std::distance(v.begin(), it) << std::endl;
    }

    // Copy
    std::vector<int> v2(v.size());
    std::copy(v.begin(), v.end(), v2.begin());

    // Reverse
    std::reverse(v.begin(), v.end());

    // Traverse
    for (const auto& elem : v) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    return 0;
}

Container Member Functions

Common Member Functions:

  • size(): Returns the number of elements in the container.
  • empty(): Checks if the container is empty.
  • push_back(), push_front(): Adds an element to the tail or head of the container.
  • pop_back(), pop_front(): Removes an element from the tail or head of the container.
  • clear(): Clears all elements in the container.
  • insert(): Inserts an element into the container.
  • erase(): Deletes an element from the container.

Example Code:

#include <iostream>
#include <vector>

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

    // Add elements
    v.push_back(6);
    v.push_front(0);

    // Delete element
    v.erase(v.begin());

    // Clear container
    v.clear();

    // Check if empty
    if (v.empty()) {
        std::cout << "Vector is empty." << std::endl;
    }

    return 0;
}

Container Selection

Performance Considerations

Access Time:

  • If fast random access to elements is needed, choose std::vector or std::deque.
  • If fast element lookup is needed, choose std::set, std::map, std::unordered_set, std::unordered_map.
  • If fast insertion and deletion of elements is needed, choose std::list or std::forward_list.

Insertion and Deletion Operations:

  • If frequent insertions or deletions occur in the middle of the container, std::list or std::forward_list are more suitable.
  • If insertions mainly occur at the tail of the container, std::vector or std::deque are more efficient.

Sorting Requirements:

  • If a sorted collection is needed, choose std::set or std::map.
  • If hash-based lookup is needed, choose std::unordered_set or std::unordered_map.

Memory Management

Memory Contiguity:

  • std::vector and std::deque store elements contiguously, which benefits cache performance.
  • std::list and std::forward_list use linked storage, memory is not contiguous, but can save space.

Dynamic Expansion:

  • std::vector reallocates a larger memory space when capacity is reached and copies existing data.
  • std::deque implements dynamic expansion through internal fixed-size arrays, allowing fast insertion and deletion at both ends.

Memory Consumption:

  • std::list and std::forward_list require additional space per element to store pointers, thus may consume more memory.

Thread Safety

By Default:

  • Containers in the C++ standard library are not thread-safe. If multiple threads access the same container simultaneously, synchronization mechanisms must be added manually.

Thread-Safe Containers:

  • Third-party libraries like boost::container can be used to obtain thread-safe containers.
  • Alternatively, use std::mutex or std::shared_mutex to protect container access.

Special Requirements

Specific Sorting Needs:

  • If custom sorting rules are needed, choose std::set or std::map and provide a comparison function.

Duplicate Elements:

  • If handling duplicate elements is needed, choose std::multiset or std::multimap.

Hash-Based Operations:

  • If fast lookup is needed and element order does not matter, choose std::unordered_set or std::unordered_map.

Fixed Size:

  • If the container size is fixed, use std::array.

Example Code

Here is a simple example showing how to choose the appropriate container based on different needs:

#include <iostream>
#include <vector>
#include <list>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>

void printVector(const std::vector<int>& v) {
    for (const auto& elem : v) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;
}

void printList(const std::list<int>& l) {
    for (const auto& elem : l) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;
}

void printSet(const std::set<int>& s) {
    for (const auto& elem : s) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;
}

void printUnorderedSet(const std::unordered_set<int>& us) {
    for (const auto& elem : us) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;
}

void printMap(const std::map<int, std::string>& m) {
    for (const auto& pair : m) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }
}

void printUnorderedMap(const std::unordered_map<int, std::string>& um) {
    for (const auto& pair : um) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }
}

int main() {
    // Requirement: Fast random access, dynamic expansion
    std::vector<int> v = {1, 2, 3, 4, 5};
    printVector(v);

    // Requirement: Linked list, fast insertion and deletion
    std::list<int> l = {1, 2, 3, 4, 5};
    l.insert(l.begin(), 0);
    l.erase(l.begin());
    printList(l);

    // Requirement: Sorted collection
    std::set<int> s = {1, 2, 3, 4, 5};
    printSet(s);

    // Requirement: Fast lookup, order doesn't matter
    std::unordered_set<int> us = {1, 2, 3, 4, 5};
    printUnorderedSet(us);

    // Requirement: Sorted key-value pairs
    std::map<int, std::string> m = {{1, "one"}, {2, "two"}, {3, "three"}};
    printMap(m);

    // Requirement: Fast key-value lookup
    std::unordered_map<int, std::string> um = {{1, "one"}, {2, "two"}, {3, "three"}};
    printUnorderedMap(um);

    return 0;
}

This example demonstrates how to select the appropriate container based on different needs and shows how to use these containers.

Container Applications

Using Containers to Optimize Data Access

Below are some example codes demonstrating how to use containers to optimize data access.

Example 1: Using std::vector for Fast Random Access

#include <iostream>
#include <vector>

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

    // Fast random access
    int middle = v[v.size() / 2];
    std::cout << "Middle element: " << middle << std::endl;

    // Pre-allocate space
    v.reserve(10000);  // Reserve space

    // Range-based for loop
    for (const auto& elem : v) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    return 0;
}

Example 2: Using std::list for Fast Insertion and Deletion

#include <iostream>
#include <list>

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

    // Fast insertion
    l.insert(l.begin(), 0);
    l.insert(l.end(), 6);

    // Fast deletion
    l.erase(l.begin());
    l.erase(--l.end());

    // Traverse using iterator
    for (auto it = l.begin(); it != l.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    return 0;
}

Example 3: Using std::unordered_map for Fast Lookup

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<std::string, int> umap = {{"apple", 1}, {"banana", 2}, {"cherry", 3}};

    // Fast lookup
    auto it = umap.find("banana");
    if (it != umap.end()) {
        std::cout << "Found banana with value: " << it->second << std::endl;
    }

    // Traverse using iterator
    for (const auto& pair : umap) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    return 0;
}

Using Containers for Efficient Lookup

The following example codes demonstrate how to use std::unordered_set and std::unordered_map for efficient lookup.

Example 1: Using std::unordered_set for Lookup

#include <iostream>
#include <unordered_set>

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

    // Check if an element exists
    bool found = numbers.find(3) != numbers.end();
    std::cout << "Element 3 found: " << (found ? "Yes" : "No") << std::endl;

    // Insert new element
    numbers.insert(6);

    // Delete element
    numbers.erase(1);

    // Traverse all elements
    for (const auto& num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

Example 2: Using std::unordered_map for Lookup

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<std::string, int> scores = {
        {"Alice", 90},
        {"Bob", 85},
        {"Charlie", 78}
    };

    // Check if a key exists
    bool found = scores.find("Bob") != scores.end();
    std::cout << "Key 'Bob' found: " << (found ? "Yes" : "No") << std::endl;

    // Insert new key-value pair
    scores["David"] = 92;

    // Update value of existing key
    scores["Alice"] = 95;

    // Delete key-value pair
    scores.erase("Charlie");

    // Traverse all key-value pairs
    for (const auto& pair : scores) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    return 0;
}

Code Analysis

Example 1: std::unordered_set

  • Initialization: Use list initialization for std::unordered_set.
  • Lookup: Use the find method to check if a specified element exists.
  • Insertion: Use the insert method to insert a new element.
  • Deletion: Use the erase method to delete a specified element.
  • Traversal: Use a range-based for loop to traverse all elements.

Example 2: std::unordered_map

  • Initialization: Use list initialization for std::unordered_map.
  • Lookup: Use the find method to check if a specified key exists.
  • Insertion: Use the [] operator directly to insert a new key-value pair.
  • Update: Use the [] operator to update the value of an existing key.
  • Deletion: Use the erase method to delete a specified key-value pair.
  • Traversal: Use a range-based for loop to traverse all key-value pairs.

Using Containers in Multithreaded Environments

Synchronization Mechanisms

Mutex (std::mutex):

  • Used to protect access to shared resources.
  • std::lock_guard or std::unique_lock can be used to automatically manage the lock’s lifecycle.

Read-Write Lock (std::shared_mutex):

  • Allows multiple threads to read shared resources simultaneously, but only one thread can write.
  • Suitable for scenarios with more reads and fewer writes.

Atomic Operations (std::atomic):

  • Used to implement atomic operations, such as atomic variables.
  • Suitable for simple data types and certain specific operations.

Example Code

The following example code demonstrates how to use std::mutex and std::lock_guard to protect access to a std::vector.

#include <iostream>
#include <vector>
#include <thread>
#include <mutex>

std::vector<int> shared_vector;
std::mutex mtx;

void addElements(int start, int end) {
    for (int i = start; i < end; ++i) {
        std::lock_guard<std::mutex> lock(mtx);  // Automatically lock and unlock
        shared_vector.push_back(i);
    }
}

int main() {
    // Initialize shared vector
    shared_vector.clear();

    // Create and start threads
    std::thread t1(addElements, 0, 50000);
    std::thread t2(addElements, 50000, 100000);

    // Wait for threads to complete
    t1.join();
    t2.join();

    // Output result
    std::cout << "Final size of shared_vector: " << shared_vector.size() << std::endl;

    // Verify if correctly sorted
    bool is_sorted = true;
    for (size_t i = 1; i < shared_vector.size(); ++i) {
        if (shared_vector[i] < shared_vector[i - 1]) {
            is_sorted = false;
            break;
        }
    }

    std::cout << "Is the vector sorted? " << (is_sorted ? "Yes" : "No") << std::endl;

    return 0;
}

Code Analysis

  • Initialization: Initialize shared resources and mutex using std::vector and std::mutex.
  • Thread Function: Define a thread function addElements that takes start and end values as parameters.
  • Locking: Use std::lock_guard to lock the mutex before each modification of shared_vector.
  • Thread Creation: Create two threads, each responsible for adding a portion of elements to shared_vector.
  • Waiting: Use the join function to wait for all threads to complete.
  • Verification: Output the final vector size and verify whether the vector is in order.

Share your love