Почему добавление поля std::list::iterator к элементам списка значительно замедляет работу pop_back в C++? ⇐ C++

[Anonymous]

Подробности проблемы
Я работаю над проектом C++, в котором использую std::list для хранения указателей на динамически выделяемые объекты. Каждый объект TestElement имеет дополнительное поле для хранения его позиции в списке с помощью std::list::iterator. Класс выглядит следующим образом:

Код: Выделить всё

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

Я заполняю оба объекта std::list 2 миллионами объектов TestElement*. Во время инициализации я сохраняю итератор каждого объекта в его поле listIterator .
Проблема в том, что когда поле listIterator присутствует в TestElement , операция pop_back в списке становится значительно медленнее. В частности:

• С полем listIterator: pop_back + delete занимает 289,316 мс.
• Без поля listIterator: та же операция занимает всего 0,0043 мс.

Поскольку pop_back должно быть константой- time для std::list, такое замедление кажется неожиданным.
Что я сделал?
Я создал std:: list, где каждый элемент в списке является указателем на TestElement.
Я добавил поле итератора к каждому TestElement, чтобы сохранить его позицию в std::list.
Я измерил время, затраченное на операцию pop_back как с полем listIterator, так и без него в TestElement.
Вот тестовая программа, которую я использовал:

Код: Выделить всё

#include 
#include 
#include 

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

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

std::list 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 duration = end - start;
totalDuration += duration.count();
}

std::cout 

Подробнее здесь: [url]https://stackoverflow.com/questions/79072879/why-does-adding-a-stdlistiterator-field-to-list-elements-significantly-slow[/url]