Блог

У меня есть вектор std::vector<inputInfo> inputList и другой вектор std::vector<int> selection . inputInfo это структура, в которой хранится некоторая информация.

Вектор selection соответствует позициям внутри inputList вектора.

Мне нужно удалить элементы, из inputList которых соответствуют записям в selection векторе.

Вот моя попытка этого алгоритма удаления.

Предполагая selection , что вектор отсортирован и использует некоторую (неизбежную?) арифметику указателей, это можно сделать в одной строке:

 template <class T>
inline void erase_selected(std::vector<T>amp; v, const std::vector<int>amp; selection)
{
    v.resize(std::distance(
      v.begin(),
      std::stable_partition(v.begin(), v.end(),
         [amp;selection, amp;v](const Tamp; item) {
            return !std::binary_search(
               selection.begin(), selection.end(),
               static_cast<int>(static_cast<const T*>(amp;item) - amp;v[0]));
         })));
}
  

Это основано на идее Sean Parent (см. Это видео по C Seasoning) для использования std::stable_partition («стабильный» сохраняет элементы, отсортированные в выходном массиве) для перемещения всех выбранных элементов в конец массива.

Строка с арифметикой указателей

 static_cast<int>(static_cast<const T*>(amp;item) - amp;v[0])
  

в принципе, можно заменить алгоритмами STL и выражением без индекса

 std::distance(std::find(v.begin(), v.end(), item), std::begin(v))
  

но таким образом мы должны потратить O (n) std::find в.

Кратчайший способ удаления несмежных элементов:

 template <class T> void erase_selected(const std::vector<T>amp; v, const std::vector<int>amp; selection)
{
    std::vector<int> sorted_sel = selection;
    std::sort(sorted_sel.begin(), sorted_sel.end());

    // 1) Define checker lambda
    // 'filter' is called only once for every element,
    // all the calls respect the original order of the array
    // We manually keep track of the item which is filtered
    // and this way we can look this index in 'sorted_sel' array
    int itemIndex = 0;
    auto filter = [amp;itemIndex, amp;sorted_sel](const Tamp; item) {
        return !std::binary_search(
                  sorted_sel.begin(),
                  sorted_sel.end(),
                  itemIndex  );
    }

    // 2) Move all 'not-selected' to the end
    auto end_of_selected = std::stable_partition(
                           v.begin(),
                           v.end(),
                           filter);

    // 3) Cut off the end of the std::vector
    v.resize(std::distance(v.begin(), end_of_selected));
}
  

Исходный код и тест

Если по какой-то причине приведенный выше код не работает из-за странного поведения std::stable_partition() , то ниже приведен обходной путь (обертывание значений входного массива selected флагами.

Я не предполагаю, что inputInfo структура содержит selected флаг, поэтому я переношу все элементы в T_withFlag структуру, которая хранит указатели на исходные элементы.

 #include <algorithm>
#include <iostream>
#include <vector>

template <class T>
std::vector<T> erase_selected(const std::vector<T>amp; v, const std::vector<int>amp; selection)
{
    std::vector<int> sorted_sel = selection;
    std::sort(sorted_sel.begin(), sorted_sel.end());

    // Packed (data flag) array
    struct T_withFlag
    {
        T_withFlag(const T* ref = nullptr, bool sel = false): src(ref), selected(sel) {}

        const T* src;
        bool selected;
    };

    std::vector<T_withFlag> v_with_flags;

    // should be like
    //      { {0, true}, {0, true}, {3, false},
    //        {0, true}, {2, false}, {4, false},
    //        {5, false}, {0, true}, {7, false} };
    //  for the input data in main()

    v_with_flags.reserve(v.size());

    // No "beautiful" way to iterate a vector
    // and keep track of element index
    // We need the index to check if it is selected
    // The check takes O(log(n)), so the loop is O(n * log(n))
    int itemIndex = 0;
    for (autoamp; ii: v)
        v_with_flags.emplace_back(
            T_withFlag(amp;ii,
                       std::binary_search(
                          sorted_sel.begin(),
                          sorted_sel.end(),
                          itemIndex  )
                       ));

    // I. (The bulk of ) Removal algorithm
    //   a) Define checker lambda
    auto filter = [](const T_withFlagamp; ii) { return !ii.selected; };
    //   b) Move every item marked as 'not-selected'
    //      to the end of an array
    auto end_of_selected = std::stable_partition(
                               v_with_flags.begin(),
                               v_with_flags.end(),
                               filter);
    //   c) Cut off the end of the std::vector
    v_with_flags.resize(
        std::distance(v_with_flags.begin(), end_of_selected));

    // II. Output
    std::vector<T> v_out(v_with_flags.size());
    std::transform(
               // for C  20 you can parallelize this
               // with 'std::execution::par' as first parameter
               v_with_flags.begin(),
               v_with_flags.end(),
               v_out.begin(),
               [](const T_withFlagamp; ii) { return *(ii.src); });
    return v_out;
}
  

Тестовая функция

 int main()
{
    // Obviously, I do not know the structure
    // used by the topic starter,
    // so I just declare a small structure for a test
    // The 'erase_selected' does not assume
    // this structure to be 'light-weight'
    struct inputInfo
    {
        int data;
        inputInfo(int v = 0): data(v) {}
    };

    // Source selection indices
    std::vector<int> selection { 0, 1, 3, 7 };
    // Source data array
    std::vector<inputInfo> v{ 0, 0, 3, 0, 2, 4, 5, 0, 7 };

    // Output array
    auto v_out = erase_selected(v, selection);

    for (auto ii : v_out)
        std::cout << ii.data << ' ';

    std::cout << std::endl;
}