c++ - 如何从 C++ 中的 vector 中删除不连续的元素

Question

我有一个 vector std::vector<inputInfo> inputList和另一个 vector std::vector<int> selection 。 inputInfo是一个存储了一些信息的结构。

vector selection对应于 inputList 内的位置 vector 。

我需要从 inputList 中删除元素对应于 selection 中的条目 vector 。

Answer 1

这是我对这种删除算法的尝试。

假设selection vector 已排序并使用一些(不可避免的？)指针算术，这可以在一行中完成:

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

这是基于 Sean Parent 的想法(请参阅此 C++ Seasoning 视频)，即使用 std::stable_partition (“stable”使元素在输出数组中排序)来移动所有选定的项目到数组的末尾。

指针运算的行

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

原则上可以用STL算法和无索引表达式替代

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

但是这样我们就必须在 std::find 中花费 O(n) 时间。

删除不连续元素的最短方法:

template <class T> void erase_selected(const std::vector<T>& v, const std::vector<int>& 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 = [&itemIndex, &sorted_sel](const T& 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>& v, const std::vector<int>& 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 (auto& ii: v)
        v_with_flags.emplace_back(
            T_withFlag(&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_withFlag& 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_withFlag& 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;
}