C++ Standard Containers and Use Cases
Overview
Intro of C++ containers and usage method
1 Overview
A container is a holder object that stores a collection of other objects as its elements. Containers are implemented as class templates, they have great flexibility in the elements' types supported. Container manages storage for elements and provides sever member functions to access and manipulate elements.
Two main categories:
- Sequence container: Maintain elements in a linear sequence.
- Associative containers: Allow efficient retrieval based on keys rather than positions. Typically implemented using binary search trees or hash tables.
Below, I'll review several commonly used sequence container and unordered associative containers along with their typical use cases.
2 Sequence Container
Sequence contaienr refers to a group of container class templates in the standard library that implements storage of data elements. It includes array, vector, list, forword_list, deque.
- Array: A compile-time non-resizable array
- Vector: Array with fast random access and automatically resize when appending elements.
- Deque: Double-ended queue with comparatively fast random access.
- List: Doubly linked list.
- Forward list: Singly linked list.
2.1 Array
std::array is a container that encapsulates fixed size arrays.
1#include <array>
2// Declare an array of integers with a fixed size of 3 elements
3array<int, 3> arr = {0, 1, 2};
4// Retrieve the size of the array using the size() member function
5arr.size();
6// Access the element at index 0 of the array using the subscript operator []
7arr[0];
2.2 Vector
std::vector is a class template in C++ Standard Library. It is sequency containers representing arrays that can change in size, it uses contiguous storage locations for their elements. Vector's size can be changed dynamically, the storage is handled automatically by the container. It allocates array to store elements dynamically.
Vector consumes more memory to manage storage and grow compare to array.
1#include <vector>
2// Ways to declare and initialize a vector
3vector<int> vec = {1, 2, 4};
4vector<int> vec {1, 2, 3};
5vector<int> vec(4, 3); // 4 is size, 3 is value {3, 3，3， 3}
6// Assign value 5 to the element at index 3
7vec[3] = 5;
8// Declare a vector of strings
9vecotr<string> planets;
10/ Add the string "Mercury" to the vector
11planets.push_back("Mercury")
12// Retrieve the number of elements in the vector
13planets.size();
14// Retrieve the current capacity of the vector
15planets.capacity()
3 Unordered Associative Container
Associative containers that store elements formed by the combination of a key value and a mapped value. Fast retrieval of individual elements based on keys. Key value is generally used to uniquely identify the element.
3.1 Unordered Map
Unordered maps are associative containers in C++ that efficiently store key-value pairs without maintaining a specific order. They offer rapid retrieval, insertion, and deletion operations based on keys, making them ideal for scenarios requiring quick access to elements identified by their keys. Compared to ordered containers like maps, unordered maps prioritize speed over element ordering, providing faster access to elements.
1#include <unordered_map>
2// Declare an unordered_map with integer keys and values
3std::unordered_map<int, int> freq_counter;
4// Access the value associated with key 1
5freq_counter[1];
6// Insert a key-value pair into the unordered_map
7freq_counter.insert(std::make_pair(2, 1));
3.2 Unordered Set
An unordered set is a container that stores a collection of unique elements in an unordered fashion. Unordered sets do not maintain a particular order among their elements. They offer fast retrieval, insertion, and deletion operations, typically implemented using hash tables. This makes them suitable for scenarios where fast lookup of unique elements is required, without concern for ordering.
1#include <unordered_set>
2// Declare and initialize an unordered_set with integer elements
3std::unordered_set<int> mySet{2, 7, 1, 8, 2, 8};
4// Insert the value 5 into the unordered_set
5mySet.insert(5);
6// Erase the value 5 from the unordered_set if it exists
7mySet.erase(5);
3.3 Application
Requirment description
This is a use case I encountered at work.
Design a Vehicle Velocity Management System aimed at storing and regulating the speed of traffic vehicles (obstacle). If detect the vehicle's velocity magnitude is not confident, the system retrieves and apply the last known velocity magnitude along with its current velocity direction. The objective is to maintain a consistent velocity for traffic vehicles, minimizing abrupt changes in speed.
Code pieces sample
1// Init associative containers to store obstacle object and obstacle id
2std::unordered_map<int, Eigen::Vector3d> obstacles_;
3std::unordered_set<int> obstacle_ids_;
4// Add obstacle information
5obstacle_ids_.insert(id);
6obstacles_[id] = velocity;
7// Remove obstacle from containers
8obstacles_.erase(id);
9obstacle_ids_.erase(id);
10
11
12// Get last velocity
13auto it = obstacles_.find(id);
14// Return the velocity if the ID is found
15if (it != obstacles_.end())
16{
17 return it->second;
18}
19else
20{
21 // Return Zeros velocity if not found
22}
23
24
25// Remove unneeded obstacle IDs
26std::unordered_set<int> ids_to_remove;
27for (const auto& obstacle : obstacles_)
28{
29 int id = obstacle.first;
30 if (obstacle_ids_.find(id) == obstacle_ids_.end())
31 {
32 ids_to_remove.insert(id);
33 }
34}
35for (int id_to_remove : ids_to_remove)
36{
37 obstacles_.erase(id_to_remove);
38}
39
40
41// Clear info
42 obstacle_ids_.clear();
43
44
45// Use magnitude of last_velocity along with current direction
46double magnitude = last_velocity.norm();
47// Normalize the current_velocity to maintain its direction
48if (current_velocity.norm() > 0.0) // Avoid division by zero
49{
50 current_velocity.normalize();
51}
52else
53{
54 // If current_velocity is zero, just return it
55 return current_velocity;
56}
57// Scale the normalized current_velocity by the magnitude of last_velocity
58current_velocity *= magnitude;
59return current_velocity;
4 Leetcode Problem
3005 Count Elements With Maximum Frequency
You are given an array nums consisting of positive integers. Return the total frequencies of elements in nums such that those elements all have the maximum frequency. The frequency of an element is the number of occurrences of that element in the array.
Example 1:
Input: nums = [1,2,2,3,1,4] Output: 4 Explanation: The elements 1 and 2 have a frequency of 2 which is the maximum frequency in the array. So the number of elements in the array with maximum frequency is 4.
Example 2:
Input: nums = [1,2,3,4,5] Output: 5 Explanation: All elements of the array have a frequency of 1 which is the maximum. So the number of elements in the array with maximum frequency is 5.
Constraints: 1 <= nums.length <= 100 1 <= nums[i] <= 100
4.1 Use Vector
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6class Solution
7{
8public:
9 int maxFrequencyElements(vector<int>& nums)
10 {
11 vector<int> frequency (nums.size(), 0);
12 for (int i = 0; i < frequency.size(); i ++)
13 {
14 frequency[i] = countDuplicatedNumber(i, nums);
15 }
16 for (int element : frequency)
17 {
18 std::cout << element << " ";
19 }
20 cout << endl;
21 int max_value = checkMaxValue(frequency);
22 return sumMaxValue(max_value, frequency);
23 }
24 int countDuplicatedNumber(const int& index, const vector<int>& vector)
25 {
26 int number = 1;
27 for (int i = 1; i + index < vector.size(); i++)
28 {
29 if (vector[i + index] == vector[index])
30 {
31 number ++;
32 }
33 }
34 return number;
35 }
36 int checkMaxValue(const vector<int>& vector)
37 {
38 int max = 0;
39 for (int i = 0; i < vector.size(); i++)
40 {
41 if (vector[i] > max)
42 {
43 max = vector[i];
44 }
45 }
46 cout << "max value in the vec is: " << max << endl;
47 return max;
48 }
49 int sumMaxValue(const int& max, const vector<int>& vector)
50 {
51 int sum = 0;
52 for (int i = 0; i < vector.size(); i++)
53 {
54 if (vector[i] == max)
55 {
56 sum += vector[i];
57 }
58 }
59 return sum;
60 }
61};
62
63int main()
64{
65 vector<int> num1 {1,2,2,3,4,4,1};
66 Solution solution;
67 float result = solution.maxFrequencyElements(num1);
68 cout << "result is: " << result << endl;
69}
4.1 Use Unnordered map
Implementation with unordered map, [reference]
1#include <iostream>
2#include <vector>
3#include <unordered_map>
4
5using namespace std;
6
7class Solution
8{
9public:
10 int maxFrequencyElements(vector<int>& nums)
11 {
12 std::unordered_map<int, int> freq_counter;
13 for(int num : nums)
14 {
15 freq_counter[num]++;
16 }
17
18 int max_frequency = 0;
19 for (const auto& entry : freq_counter)
20 {
21 max_frequency = std::max(max_frequency, entry.second);
22 }
23
24 int max_freq_elements = 0;
25 for (const auto& entry : freq_counter)
26 {
27 if (entry.second == max_frequency)
28 {
29 max_freq_elements++;
30 }
31 }
32
33 int total_frequency = max_frequency * max_freq_elements;
34 return total_frequency;
35 }
36};
37
38int main()
39{
40 vector<int> num1 {7,7,7,1,2,2,3,4,4,1};
41 Solution solution;
42 int result = solution.maxFrequencyElements(num1);
43 cout << "result is: " << result << endl;
44}