Modern C++ idoms and recipes

meshell
1,744 views

Open Source Your Knowledge, Become a Contributor

Technology knowledge has to be shared and made accessible for free. Join the movement.

Create Content

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
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#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;
}),
std::end(vec));
// reduce the capacity (Note that this may lead to reallocation of memory)
vec.shrink_to_fit();
}
int main() {
const auto print_numbers = [](const auto& numbers) { ;
for (const auto& i : numbers) {
std::cout << i << ", ";
}
std::cout << "size is " << numbers.size() << "\n";
};
std::vector<int> numbers = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
remove_multiples(numbers, 2);
print_numbers(numbers);
remove_multiples(numbers, 5);
print_numbers(numbers);
if (numbers.size() != 4) {
std::cout << "\nFailure Not all items removed\n";
return 1;
}
return 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
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#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();
}
}
template<typename T>
void quick_remove_at(std::vector<T>& vec, typename std::vector<T>::iterator it) {
if (it != std::end(vec)) {
*it = std::move(vec.back());
vec.pop_back();
}
}
int main() {
const auto print_numbers = [](const auto& numbers) { ;
for (const auto& i : numbers) {
std::cout << i << ", ";
}
std::cout << "size is " << numbers.size() << "\n";
};
std::vector<int> numbers = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
print_numbers(numbers);
quick_remove_at(numbers, 2);
print_numbers(numbers);
quick_remove_at(numbers, std::find(std::begin(numbers), std::end(numbers), 6));
print_numbers(numbers);
if(std::count(std::begin(numbers), std::end(numbers), 6) != 0) {
std::cout << "\nFailure: Element 6 was not removed.\n";
return 1;
}
return 0;
}
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
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#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
};
using namespace modern_cpp::helpers;
using namespace std::string_literals;
int main() {
try {
std::vector<std::string> dictionary = {"some", "random", "words", "with", "no", "particular", "order"};
assert_false(std::is_sorted(std::begin(dictionary), std::end(dictionary)), "Dictionary is sorted"s);
std::sort(std::begin(dictionary), std::end(dictionary));
assert_true(std::is_sorted(std::begin(dictionary), std::end(dictionary)), "Dictionary is sorted"s);
const auto dictionary_elements = dictionary.size();
insert_sorted(dictionary, "foo");
insert_sorted(dictionary, "bar");
insert_sorted(dictionary, "zeta");
assert_true(std::is_sorted(std::begin(dictionary), std::end(dictionary)), "Dictionary is sorted after inserts"s);
assert_equal(dictionary.size(), dictionary_elements + 3, "New dictionary size after insertion"s);
} catch (const std::exception& e) {
std::cout << "Exception: " << e.what();
return 1;
}
return 0;
}
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
Open Source Your Knowledge: become a Contributor and help others learn. Create New Content