Modern C++ idoms and recipes
meshell
12K views
Working with vectors
Remove multiple items from a vector
We looked already at the Erase-Remove Idiom in the Januar 2016 Meeting. The Erase-Remove Idiom is considered the correct way of removing multiple items from a standard library container.
1
2
3
4
5
6
7
8
9
10
#include <vector>
#include <iostream>
#include <algorithm>
template<typename T, typename U>
void remove_multiples(std::vector<T>& vec, U multiple_of) {
vec.erase(std::remove_if(std::begin(vec),
std::end(vec),
[=](const auto& elem) {
return elem % multiple_of == 0;
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
Deleting items from an unsorted vector in O(1)
Deleting an element from the middle of an std::vector
with the Erase-Remove idiom takes O(n), because the resulting gap must be filled by moving all the items after the gap to the left.
This might be expensive if the items are complex and/or very large. If preserving the order of the items is not important, the deletion can be optimized.
1
2
3
4
5
6
7
8
9
10
#include <vector>
#include <iostream>
#include <algorithm>
template<typename T>
void quick_remove_at(std::vector<T>& vec, std::size_t idx) {
if (idx < vec.size()) {
vec.at(idx) = std::move(vec.back());
vec.pop_back();
}
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
Keep std::vector sorted
Sometimes you want a sorted vector to be still sorted after insertion of an element. Try to implement a sorted insertion.
Implement insert_sorted method
1
2
3
4
5
6
7
8
9
10
#include <vector>
#include <iostream>
#include <algorithm>
#include "../helpers/helpers.h"
template<typename Cont, typename T>
void insert_sorted(Cont& container, const T& item) {
// TODO implement insertion such that container is still sorted after insertion
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
Create your playground on Tech.io
This playground was created on Tech.io, our hands-on, knowledge-sharing platform for developers.
Join the CodinGame community on Discord to chat about puzzle contributions, challenges, streams, blog articles - all that good stuff!
JOIN US ON DISCORD Online Participants