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::vectoris 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 Type | Description |
|---|---|
vector | Variable-size array. Supports fast random access. Inserting or deleting elements at positions other than the tail can be slow. |
deque | Double-ended queue. Supports fast random access. Inserting/deleting at head or tail is very fast. |
list | Doubly linked list. Only supports bidirectional sequential access. Inserting/deleting at any position in list is very fast. |
forward_list | Singly linked list. Only supports unidirectional sequential access. Inserting/deleting at any position in the list is very fast. |
array | Fixed-size array. Supports fast random access. Cannot add or delete elements. |
string | A 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_listandarrayare types added in the new C++ standard.- Usually, using
vectoris 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 Type | Explanation |
|---|---|
| Stored in order | |
map | Key array: holds keyword-value pairs |
set | Keyword is the value, i.e., a container that only holds keywords |
multimap | A map that supports the same key appearing multiple times |
multiset | A set that supports the same key appearing multiple times |
| Unordered collections | |
unordered_map | A map organized with a hash function |
unordered_set | A set organized with a hash function |
unordered_multimap | A hash-organized map, where keywords can appear repeatedly |
unordered_multiset | A 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 Type | Description |
|---|---|
vector | Variable-size array. Supports fast random access. Inserting or deleting elements at positions other than the tail can be slow. |
deque | Double-ended queue. Supports fast random access. Inserting/deleting at head or tail is very fast. |
list | Doubly linked list. Only supports bidirectional sequential access. Inserting/deleting at any position in list is very fast. |
forward_list | Singly linked list. Only supports unidirectional sequential access. Inserting/deleting at any position in the list is very fast. |
array | Fixed-size array. Supports fast random access. Cannot add or delete elements. |
string | A 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_listandarrayare types added in the new C++ standard.- Usually, using
vectoris 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_listdoes not have thesizeoperation; for other containers,sizeis guaranteed to be a fast constant-time operation.
Container Operations
Type Aliases
| Operation | Explanation |
|---|---|
iterator | Iterator type for this container type |
const_iterator | Iterator type that can read elements but cannot modify them |
size_type | Unsigned integer type, sufficient to hold the maximum possible size of this container type |
difference_type | Signed integer type, sufficient to hold the distance between two iterators |
value_type | Element type |
reference | Lvalue type of the element; same meaning as value_type & |
const_reference | const lvalue type of the element, i.e., const value_type & |
Constructors
| Operation | Explanation |
|---|---|
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.
arrayhas a fixed size.- Unlike other containers, a default-constructed
arrayis 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
| Operation | Explanation |
|---|---|
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
swapis a good habit. assignoperation is not applicable to associative containers andarray
Size
| Operation | Explanation |
|---|---|
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
| Operation | Explanation |
|---|---|
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_listhas its own specialized versions ofinsertandemplace.forward_listdoes not supportpush_backandemplace_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
emplaceare introduced in the new standard; these operations construct rather than copy elements. - The parameters passed to
emplacemust match the constructor of the element type. - Inserting elements into a
vector,string, ordequeinvalidates all iterators, references, and pointers to the container.
Accessing Elements
| Operation | Explanation |
|---|---|
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.
atand subscript operations are only applicable tostring,vector,deque,array.backis not applicable toforward_list.- If you want to ensure the index is legal, you can use the
atfunction.
Deleting Elements
| Operation | Explanation |
|---|---|
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_listhas a special version oferaseforward_listdoes not supportpop_backvectorandstringdo not supportpop_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_listdefinesbefore_begin, which is the off-the-beginning iterator, allowing addition or deletion of elements before the first element.
| Operation | Explanation |
|---|---|
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
| Operation | Explanation |
|---|---|
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 |
resizeis not applicable toarray
Obtaining Iterators
| Operation | Explanation |
|---|---|
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
care introduced in the C++11 new standard - When write access is not needed,
cbeginandcendshould be used - For arrays that are not class types, the non-member functions
begin()andend()should be used
Extra Members of Reverse Containers
| Operation | Explanation |
|---|---|
reverse_iterator | Iterator that addresses elements in reverse order |
const_reverse_iterator | Reverse 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:
begintoend, 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
beginandendare equal, the range is empty. - If they are not equal, the range contains at least one element, and
beginpoints to the first element in the range. begincan be incremented several times to makebegin == end.
- If
Container Operations May Invalidate Iterators
- After adding elements to a container:
- If the container is
vectororstring, 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
listandforward_list, iterators, pointers, and references to the container remain valid.
- If the container is
- After deleting an element from a container:
- For
listandforward_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 ofdeque, the past-the-end iterator becomes invalid, but others are unaffected; if deleting the head element, these are also unaffected. - For
vectorandstring, 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.
- For
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_listis a singly linked list container, similar tostd::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::dequeis a double-ended queue container that can efficiently insert and delete elements at both ends.
Memory Layout:
std::dequeuses 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
mapandset.
Associative Container Types:
| Container Type | Explanation |
|---|---|
| Stored in order | map and multimap: include <map>;set and multiset: include <set>; |
map | Key array: holds keyword-value (key-value) pairs |
set | Keyword is the value, i.e., a container that only holds keywords |
multimap | A map where keywords (key) can appear repeatedly |
multiset | A set where keywords (key) can appear repeatedly |
| Unordered collections | include <unordered_map>;include <unordered_set>; |
unordered_map | A map organized with a hash function |
unordered_set | A set organized with a hash function |
unordered_multimap | A hash-organized map, where keywords can appear repeatedly |
unordered_multiset | A hash-organized set, where keywords can appear repeatedly |
- Each of the above containers:
- Is either a
setor amap - Either requires unique
keywords (key)or allows duplicate keywords - Either stores elements in order or stores them unordered
- Is either a
- Containers that allow duplicate keywords include
multiin 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
utilityheader file. - A
pairholds two data members, and the two types are not required to be the same. - When extracting an element from a
map, for examplefor(auto &w : word_count)gets an object of typepair, i.e.,wis apair. (More directly, each element in amapis actually apair)
| Operation | Explanation |
|---|---|
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.first | Returns the data member named first of p. |
p.second | Returns the data member named second of p. |
p1 relop p2 | Relational 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 == p2 | Both pairs of elements must be equal |
p1 != p2 | Same 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 Alias | Explanation |
|---|---|
key_type | Keyword type for this container type |
mapped_type | Type associated with each keyword, only applicable to map |
value_type | For map, it is pair<const key_type, mapped_type>; for set, it is the same as key_type. |
- For
map, note thatmapped_typediffers fromvalue_type
Associative Container Iterators
- Dereferencing an associative container iterator yields a reference to a value of the container’s
value_type. setiterators areconst. Asetiterator can be used to read an element’s value, but cannot modify it.- Traversing an associative container: Using
beginandend, when traversingmap,multimap,set,multiset, iterators traverse elements in ascending keyword order.
Usually do not use generic algorithms with associative containers
- Elements in
setareconst, elements inmaparepair, where the first member isconst;- Can be used with algorithms that only read elements, but usually not efficient;
- If really needed, either use it as a source sequence or as a destination. For example, use the generic
copyto 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 Operation | Associative 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
| Operation | Explanation |
|---|---|
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
| Operation | Explanation |
|---|---|
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
mapandunordered_map,settypes 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 amapped_type, while dereferencing obtains avalue_type
Finding Elements
| Operation | Explanation |
|---|---|
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_boundandupper_boundare not applicable to unordered containers- Subscript and
atoperations are only applicable to non-constmapandunordered_map - If a
multimapormultisethas multiple elements with a given keyword, these elements are stored adjacently
std::set
Definition:
std::setis 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::multisetis 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::mapis 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::multimapis 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_setis 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_multisetis 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_mapis 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_multimapis 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::stackis 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::queueis 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_queueis 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 iteratorslist: Bidirectional iteratorsset,map: Bidirectional iteratorsunordered_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()andend(). - 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::vectororstd::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::listorstd::forward_list.
Insertion and Deletion Operations:
- If frequent insertions or deletions occur in the middle of the container,
std::listorstd::forward_listare more suitable. - If insertions mainly occur at the tail of the container,
std::vectororstd::dequeare more efficient.
Sorting Requirements:
- If a sorted collection is needed, choose
std::setorstd::map. - If hash-based lookup is needed, choose
std::unordered_setorstd::unordered_map.
Memory Management
Memory Contiguity:
std::vectorandstd::dequestore elements contiguously, which benefits cache performance.std::listandstd::forward_listuse linked storage, memory is not contiguous, but can save space.
Dynamic Expansion:
std::vectorreallocates a larger memory space when capacity is reached and copies existing data.std::dequeimplements dynamic expansion through internal fixed-size arrays, allowing fast insertion and deletion at both ends.
Memory Consumption:
std::listandstd::forward_listrequire 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::containercan be used to obtain thread-safe containers. - Alternatively, use
std::mutexorstd::shared_mutexto protect container access.
Special Requirements
Specific Sorting Needs:
- If custom sorting rules are needed, choose
std::setorstd::mapand provide a comparison function.
Duplicate Elements:
- If handling duplicate elements is needed, choose
std::multisetorstd::multimap.
Hash-Based Operations:
- If fast lookup is needed and element order does not matter, choose
std::unordered_setorstd::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
findmethod to check if a specified element exists. - Insertion: Use the
insertmethod to insert a new element. - Deletion: Use the
erasemethod to delete a specified element. - Traversal: Use a range-based
forloop to traverse all elements.
Example 2: std::unordered_map
- Initialization: Use list initialization for
std::unordered_map. - Lookup: Use the
findmethod 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
erasemethod to delete a specified key-value pair. - Traversal: Use a range-based
forloop 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_guardorstd::unique_lockcan 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::vectorandstd::mutex. - Thread Function: Define a thread function
addElementsthat takes start and end values as parameters. - Locking: Use
std::lock_guardto lock the mutex before each modification ofshared_vector. - Thread Creation: Create two threads, each responsible for adding a portion of elements to
shared_vector. - Waiting: Use the
joinfunction to wait for all threads to complete. - Verification: Output the final vector size and verify whether the vector is in order.



