Почему Erase(std::remove(…), end()) иногда работает быстрее, чем Vector::erase(iterator) для удаления среднего элемента? ⇐ C++

[Anonymous]

Я работаю над проектом C++, в котором мне часто приходится удалять элементы из середины std::vector. Я всегда понимал, что вектор::erase(iterator) — это операция O(N), поскольку она должна сдвигать все последующие элементы, чтобы заполнить пробел. Однако я наткнулся на необычную проблему с производительностью в конкретном сценарии и изо всех сил пытаюсь понять, почему это происходит, особенно после того, как я понял точное поведение std::remove.
Для определения времени я теперь использую std::chrono::steady_lock, чтобы обеспечить монотонные измерения времени, признавая потенциальные несоответствия std::chrono::high_solve_lock для таких тестов.

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

#include 
#include 
#include 
#include 

int main() {
std::vector data;
// Populate vector with a large number of elements
for (int i = 0; i < 1000000; ++i) {
data.push_back(i);
}

// Scenario 1: Erasing a single element from the middle (expected O(N))
auto start1 = std::chrono::steady_clock::now();
auto it1 = data.begin() + 500000;
data.erase(it1); // This shifts subsequent elements to fill the gap.
auto end1 = std::chrono::steady_clock::now();
std::chrono::duration diff1 = end1 - start1;
std::cout 

Подробнее здесь: [url]https://stackoverflow.com/questions/79796150/why-is-erasestdremove-end-sometimes-faster-than-vectoreraseiterator[/url]