多个std::vector中删除元素的最快方法

Question

我有三个std::vectors，每个包含不同的数据类型。

我需要做的是根据第一个向量中的索引项的值，从每个向量中删除相同的索引项。

在下面的代码中，如果localMap_points[i].m_counter的值大于30，则从所有三个向量中删除索引为[i]的项。（对于其他向量，localMap_desc包含8个项，因此在该向量中添加了x 8）

这个方法完美地运行，但速度很慢。有没有更快的方法？

我有：

for (int i = 0; i < localMap_points.size(); i++)
{
    if (localMap_points[i].m_counter > 30)
    {
        localMap_kp.erase(localMap_kp.begin() + i, localMap_kp.begin() + i + 1); // Deleting from n element to n element
        localMap_desc.erase(localMap_desc.begin() + (i * 8), localMap_desc.begin() + (i * 8) + 8); // Deleting from n element to n element X 8
        localMap_points.erase(localMap_points.begin() + i, localMap_points.begin() + i + 1); // Deleting from n element to n element

    }

}

- anti

---

可能的解决方案是存储一组索引，而不是每次复制最后的元素，然后一次性删除它们。 - Matthieu Brucher

也许退一步并审视为什么相关数据需要存储在三个不同的向量中，可能会导致不同的设计，问题可能就不再存在了？ - J.R.

向量中的项目顺序对您很重要吗？您可以通过交换/删除技巧大大提高删除性能。即，向量在中间具有缓慢的删除/插入速度，但在后面具有快速的速度。当您遇到要删除的项目时，只需将其与最后一个交换并使用 pop_back() 即可。 - Dan M.

顺序无关紧要，只要这三个向量相对应，所以我可以在所有三个向量上使用交换技巧。我会尝试一下。谢谢！ - anti

Answer 1

此处的性能瓶颈在于 std::vector 的内存布局，可能与向量元素的特殊成员函数属性/存在有关。如果您在中间删除一个元素，则从此位置直到末尾的所有元素都必须移动以调整到已删除元素之前的元素。这是通过以下方式完成的：

• 每个元素一个复制构造函数（如果没有移动构造函数或移动构造函数未标记为noexcept）
• 否则，每个元素都有一个移动构造函数。

因此，第一件要确保的事情是存储在向量中的元素类型具有 noexcept 的移动构造函数。

其次，请确保在此处使用 erase-remove模式。通过按照此模式进行操作，交换调用的重新排序将首先进行，然后再进行任何调用以删除。对于要删除的 n 个项目，这些是 n 个交换调用。然后，您将有一个简单的调用 std::vector::erase，因为所有元素都已按照应该的方式放置好了。为使此过程尽可能快，请考虑为自定义类型提供 swap 函数。

- lubgr

---

谢谢解释。非常有用。我会尝试上面的交换 / 弹出技巧。 - anti

Answer 2

以下是如何同时应用 erase-remove idiom 到三个向量的示例。

该算法的时间复杂度为 O(N)，即只需要对向量进行一次遍历。

template<typename T1, typename T2, typename T3, typename P>
void erase3(T1& v1, T2& v2, T3& v3, P predicate) {
    auto first1 = begin(v1);
    auto first2 = begin(v2);
    auto first3 = begin(v3);
    while (first1 != end(v1) && !predicate(*first1)) {
        ++first1; ++first2; ++first3;
    }
    if (first1 != end(v1)) {
        auto it1 = first1; auto it2 = first2; auto it3 = first3;
        while (++it1 != end(v1)) {
            ++it2;
            ++it3;
            if (!predicate(*it1)) {
                *first1++ = std::move(*it1);
                *first2++ = std::move(*it2);
                *first3++ = std::move(*it3);
            }
        }
        v1.erase(first1, end(v1));
        v2.erase(first2, end(v2));
        v3.erase(first3, end(v3));
    }
}

int main()
{
    std::vector<int> v1 = { 1,2,3,4,5 }, v2 = { 11,12,13,14,15 }, v3 = { 21,22,23,24,25 };

    erase3(v1, v2, v3, [](int a) { return a == 3 || a == 4; });

}

这个操作是通过将所有剩余的元素移动到向量的开头，然后从末尾剪切掉已移动的元素来完成的。

- rustyx

---

谢谢！我会实现这个。 - anti

Answer 3

使用更合适的数据结构。向量不适用于快速内部删除和插入（它们是 O(n)），如果您不需要索引访问，则列表可能是更好的选择（插入/删除是 O(1) == 常数时间）。根据您的需求，您可以使用一个辅助结构，但没有进一步的信息就无法确定。

--- 添加另一个想法（尽管已经有人建议过这个）。

如果向量的顺序无关紧要，您可以将要删除的项与向量中的最后一项进行交换，然后使用 pop_back()。

这将是 O(1)。

--- 自言自语。

另一个技巧是使用 优先队列。它们是基于一个字段的“权重”重新排序自身的数据结构，在您的应用程序中，它将是 counter 字段。它们能够在 O(log n) 中插入，并在顶部删除 O(1)。因此，删除具有较高 counter 的项目会非常快，因为它们始终在顶部。

- HappyCactus

---

（刚才注意到有人已经建议了。对不起，我没有看到它）。 - HappyCactus