Как работает std::list?

Question

[Junior007]

Как реализуется контейнер std::list в C++?

Конкретно, не могу понять эти строки:
1) "Список представляет собой контейнер, который поддерживает быструю вставку и удаление элементов из любой позиции в контейнере.

Lists are sequence containers that allow constant time insert and erase operations anywhere within the sequence, and iteration in both directions."

2) "Быстрый произвольный доступ не поддерживается.

The main drawback of lists and forward_lists compared to these other sequence containers is that they lack direct access to the elements by their position

Любая позиция и произвольный доступ не одно и тоже?

Исходя из первого утверждения, если напишу:

myList.emplace(it, 5, "Value"); // То это должно быть очень быстро

А судя по второму, такая запись должна работать за O(n)

Answer 1

[Толстый Лорри]

Произвольный доступ - это доступ по индексу, с константной сложностью (O(1)), когда вычисляется смещение и мы можем сразу перейти к нужному элементу, как в std::vector через [] или метод at(index).

В std::list, чтобы попасть (вставить, удалить и т.п.) куда-то в середину, мы должны в это место попасть, попутно обойдя все ниже(выше) лежащие элементы, один за другим. Это достаточно медленно (O(n)). Но сама вставка будет дешевой в любом месте (O(1)).

Comments

[Junior007]

Я об этом же, но в cplusplus.com/reference/ рекомендуется использовать листы для вставки данных в середину, и написано, что доступ ко всем элементам занимает константное (одно) время: "Lists are sequence containers that allow constant time insert and erase operations anywhere within the sequence, and iteration in both directions."

[Толстый Лорри]

Junior007: вставка легкая потому, что нет необходимости смещать "хвост" при каждой вставке. Про константную сложность _доступа_ внутри std::list там ничего не написано. Вставка по итератору - константная сложность, но этот итератор нужно предварительно найти =)

*сорри за правки*

[Junior007]

Толстый Лорри: А, то есть сам процесс вставки, к примеру, в 500-ую позицию все равно займет o(500) ? Т.к. it = begi90n+500 - Будет проходить по всем этим элементам? А когда мы уже получить указатель it - только тогда вставка произойдет быстро?

[Толстый Лорри]

Junior007: Если у вас есть итератор на нужную позицию, то затратиться лишь время, необходимое на создание копии в листе и переопределении ссылок на него у предыдущего и последующего элементов. Вне зависимости от места вставки, т.е. сложность вставки константна. А если вы захотите вставить новый элемент _на шестую позицию_, то итератор туда еще потребуется получить, пройдя с начала до нынешнего 6го элемента.

[Junior007]

Толстый Лорри: Хорошо, сама по себе вставка константа, это я уже понял. Спасибо) Но: "итератор туда еще потребуется получить" чтобы осуществить эту самую 'константную' вставку необходимо еще получить итератор, что занимает все равно линейное время, правильно?

[Толстый Лорри]

Junior007: В общем случае - да. Но стоит учитывать, что итераторы в std::list не "бьются" при вставке, как это происходит в std::vector, это удобно в некоторых ситуациях. Если нет каих-то особых требований, то лучше использовать std::vector, этого чаще всего хватает. Потом уже нужно смотреть на списки (дешвые вставки в середину, долкий рандомный доступ), дэки (компромисс между доступом и вставкой), хэш-таблицы (быстрый доступ, быстрая вставка, огормный расход памяти)...

[Junior007]

Толстый Лорри: Ага, все, понял. То есть не смотря на то, что чтобы вставить в середину нам нужно пройти по пусть 20 000 элементов, чтобы найти нужный итератор, но мы все равно получим выигрыш, т.к. во время вставки изменяться лишь указатели и не придется перемещать все остальные элементы как в векторе, верно?

[Толстый Лорри]

Junior007: Да. Но еще раз акцентирую: std::list - это не серебряная пуля и в большинстве случаев для небольшой коллекции мелких объектов он будет проигрывать std::vector как по производительности, так и по расходу памяти.

[Junior007]

Толстый Лорри: Это я знаю, спасибо за разъяснения

Answer 2

[Xano]

Лист - не упорядоченный в памяти массив, связь между элементами осуществляется путем сохранения указателя на следующий и/или предыдущий элемент. При удалении или добавлении элемента всего лишь меняются эти самые указатели - это объясняет "поддерживает быструю вставку и удаление элементов из любой позиции в контейнере".

"myList.emplace(it, 5, "Value"); " отработает следующим образом ( условно )
auto item = new ItemType( 5, "Value" );
item->next = it->next;
it->next = item;

Быстрый произвольный доступ - подразумевает доступ к N элементу за константное время. Лист же предоставляет доступ лишь за линейное время, т.к. для доступа к N элементу необходимо перебрать все предыдущие элементы.

Comments

[Junior007]

Хорошо, кажется начинаю понимать. Значит верно, что листы в C++ нужно использовать когда необходимо часто делать вставки в середине? Т.к. они обеспечивают большую скорость?
Я не могу понять вот что, чтобы вставить на туже 5-ю позицию ведь все равно необходимо пройти до 5-го эл. чтобы потом связать указатели?

[Junior007]

То есть сам процесс вставки, к примеру, в 500-ую позицию все равно займет o(500) ? Т.к. it = begin()+500 - Будет проходить по всем этим элементам чтобы получить нужный итератор? А когда мы уже получили указатель it - только тогда вставка произойдет быстро?

[abcd0x00]

Junior007: в списке ты можешь один раз долго идти до пятого элемента, а потом тысячу раз там быстро вставить элемент.
В векторе (vector) наоборот - ты можешь быстро дойти до пятого элемента, но при вставке там нового элемента нужно сдвигать все правые элементы вправо, чтобы освободить место для вставляемого. Тысяча таких вставок будет очень долгой.

[Junior007]

abcd0x00: вставка 20000 элементов в листе: 0.1 с, в векторе: 0.2 с, но за аналогию спасибо

[abcd0x00]

Junior007:
Вот этот запусти, прекрасно видно разницу.

#include <iostream>
#include <vector>
#include <list>

using namespace std;

int main()
{
    list<int> l;
    vector<int> v;

    for (int i = 0; i < 100000; i++) {
        l.push_back(i + 1);
        v.push_back(i + 1);
    }

    cout << "list insert start" << endl;
    for (int i = 0; i < 100000; i++) {
        l.insert(l.begin(), 5);
    }
    cout << "list insert end" << endl;

    cout << "vector insert start" << endl;
    for (int i = 0; i < 100000; i++) {
        v.insert(v.begin(), 5);
    }
    cout << "vector insert end" << endl;

    return 0;
}

[Junior007]

abcd0x00: Вижу разницу во времени. Здесь происходит вставка 5*100000 = 500 000 эл. верно?

[abcd0x00]

Junior007: 100000 раз вставляется число 5 в начало. Эта разница есть на любом количестве элементов. Просто, чтобы её увидеть натурально в консоли, делается 100000 вставок.