Overview of available STL container classes at CppReference.com
Overview of available STL container classes at GeeksForGeeks.org
[vector – Fast removing of element from unordered vector – Keep vector elements sorted]
[map – Insert elements – Modify map key]
[set – filter duplicate entries, sort entries]
[Adapting associative containers (set, map)]
std::vector
When accessing a vector element always prefer usage of at(idx) member function which ensures a safe access when using invalid indices:
std::vector v{10,20,30};
auto & i = v[3]; // bad, undefined behaviour, may corrupt memory
auto & i = v.at(3); // good, causes std::out_of_range exceptionFast removing of element from unordered vector
Principle: only the last element of the vector is moved to the position of the removal. No other vector elements have to be moved around.
Cost: each removal causes a changed order of elements.
Functions for fast removal:
// Remove element at given index
template<typename T> void FastDelete(T& v, size_t idx)
{
if (idx < v.size())
{
v[idx] = std::move(v.back());
v.pop_back();
}
}
// Remove element at given iterator position
template<typename T> void FastDelete(T& v, typename T::iterator it)
{
if (it < v.end())
{
*it = std::move(v.back());
v.pop_back();
}
}Example of usage:
std::vector<int> v{0, 1, 2, 3, 4, 5};
PrintContainer(v, "initial container");
auto it = std::ranges::find(v, 3);
FastDelete(v, it);
PrintContainer(v, "after remove of value 3 via iterator position");
FastDelete(v, 1);
PrintContainer(v, "after remove of index position 1");
Output:
initial container: 0 1 2 3 4 5
after remove of value 3 via iterator position: 0 1 2 5 4
after remove of index position 1: 0 4 2 5Keep vector elements sorted
If you have an already sorted container (vector, set, deque, list) and you want to add a new element then you should insert it at the correct position to keep the correct sort order.
Helper function to check for current sort order:
void CheckIfSorted(auto& container)
{
std::cout << std::format("container is sorted: {}\n", std::ranges::is_sorted(container));
}Function to insert at correct position:
void InsertSorted(auto& container, const auto& element)
{
const auto pos{ std::ranges::lower_bound(container, element) };
container.insert(pos, element);
}Method lower_bound finds the iterator position of the first element in the container which is greater or equal to the element to insert.
Example code:
std::vector<std::string> vs{"BB", "CC", "AA"};
PrintContainer(vs);
CheckIfSorted(vs);
std::ranges::sort(vs);
PrintContainer(vs);
CheckIfSorted(vs);
InsertSorted(vs, "AB");
InsertSorted(vs, "ZZ");
PrintContainer(vs);
CheckIfSorted(vs);Output:
BB CC AA
container is sorted: false
AA BB CC
container is sorted: true
AA AB BB CC ZZ
container is sorted: truestd::map
To add elements to an existing map there are the following possibilities:
- myMap[key] = value
simple method, not performant (because first the default constructor for the value is called on the left side before the value from right side is assigned). The value is always inserted into the map. An older entry for the same key is overwritten. - myMap.insert(std::pair<KeyType,ValueType>(key,value))
The key/value pair is only inserted if the key does not yet exist within the map.
Return value of insert is pair<iterator,bool>, containing the position of the (old or new) element with the given key and the flag indicating whether the new value was added. - myMap.emplace(Args&&… args) or myMap.try_emplace(key, Args&&… args)
The element is only inserted if the key does not yet exist within the map. The methods use perfect forwarding, i.e. the arguments are forwarded directly to the element constructors. Method emplace both creates key and value object. If key is already present in the map both objects (especially the usually bigger value object =payload) are destroyed again. The newer method try_emplace also creates the key object to check for its existence in the map. But the value object will only be created if the element will really be inserted.
Return value of emplace/try_emplace is pair<iterator,bool>, containing the position of the (old or new) element with the given key and the flag indicating whether the new value was added.
Recommendation:
Because of performance reasons always prefer usage of method try_emplace(key, args…).
Insert elements
Map and helper functions:
#include <map>
struct PersonalData
{
std::string name;
int age;
PersonalData(const std::string& in_name, int in_age)
:
name(in_name),
age(in_age)
{
std::cout << std::format("constructing {}\n", name);
}
};
// key is employer number
using PersonMap = std::map<int, PersonalData>;
void PrintMap(const PersonMap& map)
{
for (const auto& [key, data] : map)
{
std::cout << std::format("[{}: {} {}] ", key, data.age, data.name);
}
std::cout << '\n';
}
Client code:
PersonMap m;
m.try_emplace(101, std::string("Meyer"), 48);
m.try_emplace(108, "Miller", 23);
m.try_emplace(103, "Dreyfuss", 56);
PrintMap(m);
// not added, value object is temporarily constructed and destroyed:
m.emplace(std::piecewise_construct, std::forward_as_tuple(108),
std::forward_as_tuple("Williams", 33));
// Remark: the more complex passing of params is only needed when value type has a constructor.
// Without constructor the syntax is the same as for try_emplace.
// But here we need the constructor to produce output.
// not added, value object is NOT constructed
m.try_emplace(101, "Russell", 67);
PrintMap(m);
Output:
constructing Meyer
constructing Miller
constructing Dreyfuss
[101: 48 Meyer] [103: 56 Dreyfuss] [108: 23 Miller]
constructing Williams
[101: 48 Meyer] [103: 56 Dreyfuss] [108: 23 Miller]Modify the keys of map items
When accessing a map element (e.g. through an iterator) the key is write protected and cannot be changed. With the new map method extract() a map element can be removed from the map without destroying the belonging data. When two elements are extracted their key values can be changed (e.g. swapped). Finally the extracted elements are inserted back to the map.
Function to swap two keys:
template<typename Map, typename Key>
bool NodeSwap(Map& m, Key k1, Key k2)
{
// Extract two elements from map
auto node1{ m.extract(k1) };
auto node2{m.extract(k2)};
if (node1.empty() || node2.empty())
return false;
// Exchange the key values
std::swap(node1.key(), node2.key());
// Insert elements back to map
m.insert(std::move(node1));
m.insert(std::move(node2));
return true;
}Example code (extension from the map example above):
PrintMap(m);
NodeSwap(m, 101, 108);
PrintMap(m);
Output:
[101: 48 Meyer] [103: 56 Dreyfuss] [108: 23 Miller]
[101: 23 Miller] [103: 56 Dreyfuss] [108: 48 Meyer]std::set
Common use of a set: filter duplicate entries and establish an automatically sort order.
Example: filter duplicate words from command line input:
#include <set>
using InputIt = std::istream_iterator<std::string>;
using OutputIt = std::ostream_iterator<std::string>;
std::set<std::string> GetUniqueWordsFromCommandLine()
{
std::set<std::string> words;
InputIt it{ std::cin };
InputIt end{};
// Transfer words from std::cin to set of unique words
std::copy(it, end, std::inserter(words, words.end()));
return words;
}Main:
const auto words = GetUniqueWordsFromCommandLine();
std::copy(words.begin(), words.end(), OutputIt(std::cout, " "));
Run in comand prompt:
echo bb aa bb cc aa | MyTestApp.exe
aa bb ccAdapting associative containers (set, map)
Example:
using SetDecreasing = std::set<std::string,
// change sort algorithm with stateless lambda, can be default constructed/copyassigned
decltype([](const auto& l, const auto& r) {return l > r})>;
SetDecreasing set = {"banana", "apple", "peach"};
// => iteration has sequence "peach" - "banana" - "apple"
// (a regular std::set would have sequence "apple" - "banana" - "peach")Attention: Changing the sort algorithm (e.g. only regarding the size of words and not their contents) may have an effect on the number of elements within the container. (e.g. a std::set then has only one word for each length because words with the same length are regarded as equal. Adding “peach” to an existing set {“apple”} will have no effect.)