如何根据索引列表从std::vector中删除元素

Question

我有一个项目向量 items，还有一个应该从 items 中删除的索引向量：

std::vector<T> items;
std::vector<size_t> indicesToDelete;

items.push_back(a);
items.push_back(b);
items.push_back(c);
items.push_back(d);
items.push_back(e);

indicesToDelete.push_back(3);
indicesToDelete.push_back(0);
indicesToDelete.push_back(1);

// given these 2 data structures, I want to remove items so it contains
// only c and e (deleting indices 3, 0, and 1)
// ???

知道每次删除都会影响到indicesToDelete中的所有其他索引，那么最好的删除方式是什么？

几个想法如下：

1. 逐个将items复制到一个新向量中，如果索引在indicesToDelete中则跳过。 2. 遍历items，对于每个删除操作，将indicesToDelete中大于该索引的所有项都减1。 3. 先对indicesToDelete进行排序，然后遍历indicesToDelete，对于每个删除操作，增加一个indexCorrection，从后续的索引中减去。

这些方法似乎过于复杂了。有更好的想法吗？

编辑：下面是解决方案，基本上是#1的变体，但使用迭代器定义要复制到结果的块。

template<typename T>
inline std::vector<T> erase_indices(const std::vector<T>& data, std::vector<size_t>& indicesToDelete/* can't assume copy elision, don't pass-by-value */)
{
    if(indicesToDelete.empty())
        return data;

    std::vector<T> ret;
    ret.reserve(data.size() - indicesToDelete.size());

    std::sort(indicesToDelete.begin(), indicesToDelete.end());

    // new we can assume there is at least 1 element to delete. copy blocks at a time.
    std::vector<T>::const_iterator itBlockBegin = data.begin();
    for(std::vector<size_t>::const_iterator it = indicesToDelete.begin(); it != indicesToDelete.end(); ++ it)
    {
        std::vector<T>::const_iterator itBlockEnd = data.begin() + *it;
        if(itBlockBegin != itBlockEnd)
        {
            std::copy(itBlockBegin, itBlockEnd, std::back_inserter(ret));
        }
        itBlockBegin = itBlockEnd + 1;
    }

    // copy last block.
    if(itBlockBegin != data.end())
    {
        std::copy(itBlockBegin, data.end(), std::back_inserter(ret));
    }

    return ret;
}

- tenfour

---

第三步应该是“首先对indeciesToDelete进行排序，然后以相反的顺序删除它们。那样就不需要更正了。虽然，这仍然是缓慢的答案。” - Mooing Duck

T是一个小结构体，包含一些std::string和一些整数。通常我们会删除少量元素。我将使用下面发布的反向排序解决方案。谢谢大家。 - tenfour

一定要喜欢你选择列表而不是向量的时代。 - flumpb

@kisplit 的确如此，但如果我们每次都被允许使用最舒适的最佳工具来完成工作，我想这个网站甚至都不会存在。 - tenfour

你的算法没有复制最后一个删除元素之后的块。看起来你需要在 for 循环之后加上 std::copy(itBlockBegin, data.end(), std::back_inserter(ret));。 - JohnPS

Answer 1

我会选择1/3的做法，即：排序索引向量，创建两个指向数据向量的迭代器，一个用于读取，一个用于写入。将写入迭代器初始化为要删除的第一个元素，并将读取迭代器初始化为该元素之后的一个元素。然后，在每个循环步骤中，递增迭代器到下一个值（写入）和不应跳过的下一个值（读取），并复制/移动元素。在循环结束时，调用erase来丢弃最后一个写入位置之后的元素。

顺便说一下，这是STL中remove/remove_if算法实现的方法，不同之处在于您使用单独的有序向量来维护条件。

- David Rodríguez - dribeas

---

一个更简单的算法是对indicesToDelete进行排序，并按相反的顺序从向量中删除元素。您不需要更新任何索引，因为所有连续的索引都会变小。请注意，标准的“erase”函数效率不高。如果不必保留顺序，请将一个元素与最后一个交换，并执行“resize”。 - Tim Kuipers

@Angelorf：答案中的方法比你的更有效率，在这两种方法中都需要对索引进行排序，我的方法中每个有效元素最多只复制一次，而在你的方法中最坏情况下将线性地复制多次。调用erase不是低效的。 在调用完成时，它的行为类似于将大小调整为较小的大小（erase(it，end())），如果检查方面存在微小的常数因子差异，则可以将其替换为resize(it-begin())以获得相同的效果。[...] - David Rodríguez - dribeas

erase(it,end()) 和 resize 之间的差异仍然比从末尾多次移动元素所产生的额外成本要小得多。成本与该方法相似，但这是稳定的。 - David Rodríguez - dribeas

@Angelorf：考虑到稳定版（不稳定版是线性的），想象一个N个元素的向量，要移除的索引为[0，N/2)。从后面开始，你找到要删除的第一个元素，然后erase它，触发从擦除点到结尾（有效元素）的N/2个元素的复制，然后你找到下一个元素，并再次在末尾复制N/2个元素，最终重复操作N/2次，导致N^2/4个拷贝，这是O(N^2)。 - David Rodríguez - dribeas

@DavidRodríguez-dribeas：确切地说，这就是我使用(swap或copy)+resize而不是erase的原因；由于这个事实，我们获得了效率，但是不保持元素顺序，即失去了稳定性。 您算法的优点：稳定性，在某些情况下略微更有效（尽管最坏时间复杂度相同）。 我的优点：易于实现。 - Tim Kuipers

Answer 2

将indicesToDelete按降序排序，然后在普通的for循环中从items中删除。不需要再调整索引。

- Constantinius

---

想法＃1速度更快。 - Mooing Duck

想法＃1与第二个向量的排序结合在一起，使得算法在两个向量的大小上为线性算法O(M + N)，实际上在修改向量大小上是O(N)。 - David Rodríguez - dribeas

如果操作后vector中元素的顺序无关紧要，那么不要立即删除，而是将该索引处的元素与向量末尾的元素进行交换，最后删除末端n个元素，其中n是indicesToDelete向量中元素的数量。 - James Kanze

Answer 3

甚至可能是第四个选项：

如果您要从大量项目中删除几个，并且知道永远不会有高密度的删除项目：

将应该删除的索引处的每个项目替换为“墓碑”值，表示在这些索引处没有有效项目，并确保每当您访问项目时，都要检查是否有墓碑。

- James

---

+1 鼓励创新思维！在多线程情况下，墓碑值非常有用，特别是当您希望尽可能地将更改保持本地化时。请注意，并非所有要求都适用于墓碑，特别是现在将“真实”索引映射到具有幻影元素的向量中的索引变得很昂贵。 - Matthieu M.

Answer 4

由于讨论已经转变为与性能相关的问题，我编写了以下代码。它使用remove_if和vector::erase，应该将元素移动到最小次数。有一些开销，但对于大型情况，这应该是不错的选择。

然而，如果您不关心元素的相对顺序，则这并不会很快。

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <set>

using std::vector;
using std::string;
using std::remove_if;
using std::cout;
using std::endl;
using std::set;

struct predicate {
    public:
        predicate(const vector<string>::iterator & begin, const vector<size_t> & indices) {
            m_begin = begin;
            m_indices.insert(indices.begin(), indices.end());
        }

        bool operator()(string & value) {
            const int index = distance(&m_begin[0], &value);
            set<size_t>::iterator target = m_indices.find(index);
            return target != m_indices.end();
        }

    private:
        vector<string>::iterator m_begin;
        set<size_t> m_indices;
};

int main() {
    vector<string> items;
    items.push_back("zeroth");
    items.push_back("first");
    items.push_back("second");
    items.push_back("third");
    items.push_back("fourth");
    items.push_back("fifth");

    vector<size_t> indicesToDelete;
    indicesToDelete.push_back(3);
    indicesToDelete.push_back(0);
    indicesToDelete.push_back(1);

    vector<string>::iterator pos = remove_if(items.begin(), items.end(), predicate(items.begin(), indicesToDelete));
    items.erase(pos, items.end());

    for (int i=0; i< items.size(); ++i)
        cout << items[i] << endl;
}

这个的输出将会是：

second
fourth
fifth

---

还有一些性能开销可以进一步减少。在 remove_if 中（至少在 gcc 上），谓词被按值复制到向量中的每个元素。这意味着我们可能每次都要对集合 m_indices 进行复制构造函数。如果编译器无法消除这种情况，那么我建议将索引作为集合传递，并将其存储为 const 引用。

我们可以按以下方式实现：

struct predicate {
    public:
        predicate(const vector<string>::iterator & begin, const set<size_t> & indices) : m_begin(begin), m_indices(indices) {
        }

        bool operator()(string & value) {
            const int index = distance(&m_begin[0], &value);
            set<size_t>::iterator target = m_indices.find(index);
            return target != m_indices.end();
        }

    private:
        const vector<string>::iterator & m_begin;
        const set<size_t> & m_indices;
};

int main() {
    vector<string> items;
    items.push_back("zeroth");
    items.push_back("first");
    items.push_back("second");
    items.push_back("third");
    items.push_back("fourth");
    items.push_back("fifth");

    set<size_t> indicesToDelete;
    indicesToDelete.insert(3);
    indicesToDelete.insert(0);
    indicesToDelete.insert(1);

    vector<string>::iterator pos = remove_if(items.begin(), items.end(), predicate(items.begin(), indicesToDelete));
    items.erase(pos, items.end());

    for (int i=0; i< items.size(); ++i)
        cout << items[i] << endl;
}

- Bill Lynch

Answer 5

这是我针对这个问题的解决方案，它保持了原始“items”的顺序：

1. 创建一个“向量掩码”并用“false”值初始化（填充）它。
2. 将掩码的值更改为要删除的所有索引的“true”。
3. 循环遍历“mask”的所有成员，并从“items”和“mask”中删除具有“true”值的元素。

以下是代码示例：

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    vector<unsigned int> items(12);
    vector<unsigned int> indicesToDelete(3);
    indicesToDelete[0] = 3;
    indicesToDelete[1] = 0;
    indicesToDelete[2] = 1;
    for(int i=0; i<12; i++) items[i] = i;

    for(int i=0; i<items.size(); i++)
      cout << "items[" << i << "] = " << items[i] << endl;

    // removing indeces
    vector<bool> mask(items.size());
    vector<bool>::iterator mask_it;
    vector<unsigned int>::iterator items_it;
    for(size_t i = 0; i < mask.size(); i++)
      mask[i] = false;
    for(size_t i = 0; i < indicesToDelete.size(); i++)
      mask[indicesToDelete[i]] = true;        

    mask_it = mask.begin();
    items_it = items.begin();
    while(mask_it != mask.end()){
      if(*mask_it){
        items_it = items.erase(items_it);
        mask_it = mask.erase(mask_it);
      }
      else{
        mask_it++;
        items_it++;
      }
    }

    for(int i=0; i<items.size(); i++)
      cout << "items[" << i << "] = " << items[i] << endl;

    return 0;
}

这不是一个适用于大数据集的快速实现。方法“erase()”需要时间来重新排列向量以消除元素。

- Rasoul

Answer 6

这取决于您要删除的数字。

如果您要删除许多项目，则将未被删除的项目复制到新向量中，然后在排序 indicesToDelete 后将旧向量替换为新向量可能是有意义的。这样，您将避免在每次删除后压缩向量，这是一个O(n)的操作，可能使整个过程变成O(n^2)。

如果您要删除少量项目，则可以按相反的索引顺序（假设索引已排序）进行删除，然后在删除项目时无需调整它们。

- Michael Goldshteyn

Answer 7

基本上，解决这个问题的关键是记住，如果您删除索引i处的对象并且不使用墓碑占位符，则向量必须复制之后的所有对象。 除了#1之外，您建议的每种可能性都适用。将其复制到新列表中使得无论您删除多少个，都只有一次复制，这使它成为迄今为止最快的答案。
正如David Rodríguez所说，将要删除的索引列表进行排序可以进行一些小的优化，但如果您要删除的数量不超过10-20个（请先进行性能分析），则此方法可能只值得一试。

- Mooing Duck