为什么在 C++ 中添加 std::list::iterator 字段来列表元素会显着减慢 pop_back 速度？

Question

问题详情 我正在开发一个 C++ 项目，其中使用

std::list<TestElement*>

来存储指向动态分配对象的指针。每个 TestElement 对象都有一个附加字段，用于使用

std::list::iterator

存储其在列表中的位置。类看起来像这样：

class TestElement {
public:
    int value;
    std::list<TestElement*>::iterator listIterator; // Stores iterator to its position in the list
};

我用 200 万个

std::list

对象填充两个

TestElement*

。在初始化期间，我将每个对象的迭代器存储在其

listIterator 

字段中。

问题在于，当

listIterator

中存在

TestElement

字段时，列表上的

pop_back

操作会明显变慢。具体来说：

• 使用

  listIterator

  字段：

  pop_back

  +

  delete

  需要 289.316 毫秒。
• 没有

  listIterator

  字段：同样的操作只需要0.0043毫秒。

由于

pop_back

应该是

std::list

的恒定时间操作，因此这种减速似乎是出乎意料的。

我做了什么？ 我创建了一个

std::list<TestElement*>

，其中列表中的每个元素都是指向 TestElement 的指针。 我向每个 TestElement 添加了一个迭代器字段，以将其位置存储在 std::list 中。 我测量了 TestElement 中使用和不使用 listIterator 字段时 pop_back 操作所花费的时间。

这是我使用的测试程序：

#include <iostream>
#include <list>
#include <chrono>

class TestElement {
public:
    int value;
    std::list<TestElement*>::iterator listIterator;
};

int main() {
    const int numElements = 2000000;
    const int testIterations = 10;

    std::list<TestElement*> testList;

    for (int i = 0; i < numElements; ++i) {
        testList.push_front(new TestElement());
        testList.front()->listIterator = testList.begin();
    }

    double totalDuration = 0.0;

    for (int t = 0; t < testIterations; ++t) {
        auto start = std::chrono::high_resolution_clock::now();

        delete testList.back();
        testList.pop_back();

        auto end = std::chrono::high_resolution_clock::now();
        std::chrono::duration<double, std::milli> duration = end - start;
        totalDuration += duration.count();
    }

    std::cout << "Average time for pop_back and delete operations: "
              << (totalDuration / testIterations) << " ms" << std::endl;

    return 0;
}

我预计

pop_back

和

delete

的性能不会受到 listIterator 字段存在的影响。由于

pop_back

是

std::list

的恒定时间操作，因此我没想到在 TestElement 中添加迭代器字段会导致性能显着下降。但是，添加 listIterator 字段会导致

pop_back

和

delete

花费 289.316 毫秒，而没有该字段时仅花费 0.0043 毫秒。

Answer 1

我在 Windows 11 和 Intel Core I7-14700K 上使用 Visual Studio 2022 尝试了您的测试程序。

发布版本，x64 代码：

• 使用迭代器：0.00016 ms
• 没有迭代器：0.00015 ms

发布版本，x86 代码：

• 使用迭代器：0.00028 ms
• 没有迭代器：0.00022 ms

调试构建，x64 代码：

• 使用迭代器：132.247 ms
• 没有迭代器：0.00085 ms

调试构建，x86 代码：

• 使用迭代器：37.3472 ms
• 没有迭代器：0.00092 ms

您的里程会根据您使用的编译器和环境而有所不同。

是否启用优化很重要。 此外，调试构建和调试运行时库在生成的代码中具有额外的正确性检查

列表元素应该从堆中分配，编译器/C++ 运行时可能有不同的策略来分配不同大小的对象。 Visual C++ 调试运行时库还具有额外的检查和统计功能，可以检测内存正确性错误。

最后，根据我的经验，在 Visual C++ 的情况下，如果您在不附加调试器的情况下运行代码，即使对于发布版本，堆操作也往往会更快。