🔥 std::list - когда он действительно нужен

Проблема: Многие выбирают std::list думая, что вставка O(1) всегда лучше, но забывают про cache locality.


✏️ Когда list ДЕЙСТВИТЕЛЬНО лучше:


1️⃣ Частые вставки/удаления в середине + большие объекты:

struct HeavyObject { 
    std::array<double, 1000> data; 
};

std::list<HeavyObject> items; // Не перемещаем данные
auto it = items.begin();
std::advance(it, 5);
items.insert(it, HeavyObject{}); // Быстро!

2️⃣ Когда нужна стабильность итераторов:

std::list<int> data = {1, 2, 3};
auto it = data.begin();
data.push_back(4); // it все ещё валиден!

3️⃣ В 90% случаев vector быстрее list:

// vector выигрывает благодаря cache:
std::vector<int> fast;  // Данные подряд в памяти
std::list<int> slow;    // Прыжки по указателям

Библиотека C/C++ разработчика

#буст