Modern C++ idoms and recipes

meshell

59.3K views

GitHub

Open Source Your Knowledge, Become a Contributor

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

Create Content

Previous: Regular Expressions (Solution) Next: insert_sorted

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.

#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;
}

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.

#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;
}

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

#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;
}

Open Source Your Knowledge: become a Contributor and help others learn. Create New Content

Open Source Your Knowledge, Become a Contributor

15/19 std::vector operations

Working with vectors

Remove multiple items from a vector

Deleting items from an unsorted vector in O(1)

Keep std::vector sorted

c++17 std::optional

Apprendre le C++

Using Pragma For Compile Optimization

Totoro Beam Search C++ Starter

Deleting items from an unsorted vector in $O (1)$