C++ 从矢量效率问题中删除

Question

我有2个完全相同的程序版本，迷宫生成器，用Python编写，C++。在Python中优化它后，我的想法是，如果我用C++重写它，它将更快，更有效率。然而，我发现了一件令人惊讶的事情（当你想到它时，这并不奇怪）。对于Python：我的算法从列表中选择一个随机项目，处理它，然后从那里删除它。对于C++：都是一样的，但不是列表，而是使用向量。从C++中的向量中删除元素比在Python中对列表执行相同的操作要慢得多，因为当您删除它们时，向量的元素会发生变化。我的问题是：C++中可以编制索引并比vector更快地执行其项目删除的最佳数据结构是什么？现在C++的删除时间是Python平均时间的5-6倍。

Answer 1

std::list是一个链接列表，与动态数组的线性复杂性相比，它具有任意元素的恒定复杂性去除。对于少量元素，由于更好地使用缓存，vector 仍然可以更快，但渐近复杂性决定了大量元素的速度。std::vector

也就是说，为了从链表中选择一个随机元素进行删除，您需要使用辅助数据结构来实现低于线性的复杂性。

此外，python列表也具有删除的线性复杂性，因此不清楚为什么您会认为它更快。

随机删除可能更有效的可能是由不同大小的段组成的绳索数据结构。但是标准库中没有使用此类数据结构实现的容器。

---

关于您的特定程序的更多信息，而不是随机或任意删除：似乎更好的算法可能是一种选择：

使用矢量。将最后一个有效元素移到“已删除”元素上，并擦除矢量末尾的已移动对象。除非有效部分的顺序很重要，否则可以使用此算法。

Answer 2

尝试创建一个专用类，该类不是在要删除项目时实际删除项目，而是将项目交换到垃圾部分的末尾。vectorvector

下面是可用于测试性能的代码示例：

#include <vector>

#include <iostream>

using namespace std;

template <typename T>

struct FastDelVec {

    vector<T> data;

    int deleteIndex;

    FastDelVec(int size) {

        data.resize(size);

        deleteIndex = size - 1;

    }

    void Delete(int index) {

        swap(data[index], data[deleteIndex]);

        --deleteIndex;

    }

    size_t size() {

        return deleteIndex + 1;

    }

};

int main() {

    FastDelVec<int> v(100);

    for (int i = 0; i < 100; ++i) {

        v.data[i] = i;

    }

    v.Delete(30);

    v.Delete(5);

    v.Delete(21);

    cout << v.size() << endl;

    system("pause");

    return 0;

}

您还可以尝试其他几种技巧。这会将删除推迟到以后，因为不断释放堆内存并可能调整大小会降低性能vector