Толстый Лорри: Ага, все, понял. То есть не смотря на то, что чтобы вставить в середину нам нужно пройти по пусть 20 000 элементов, чтобы найти нужный итератор, но мы все равно получим выигрыш, т.к. во время вставки изменяться лишь указатели и не придется перемещать все остальные элементы как в векторе, верно?
Толстый Лорри: Хорошо, сама по себе вставка константа, это я уже понял. Спасибо) Но: "итератор туда еще потребуется получить" чтобы осуществить эту самую 'константную' вставку необходимо еще получить итератор, что занимает все равно линейное время, правильно?
То есть сам процесс вставки, к примеру, в 500-ую позицию все равно займет o(500) ? Т.к. it = begin()+500 - Будет проходить по всем этим элементам чтобы получить нужный итератор? А когда мы уже получили указатель it - только тогда вставка произойдет быстро?
Толстый Лорри: А, то есть сам процесс вставки, к примеру, в 500-ую позицию все равно займет o(500) ? Т.к. it = begi90n+500 - Будет проходить по всем этим элементам? А когда мы уже получить указатель it - только тогда вставка произойдет быстро?
Хорошо, кажется начинаю понимать. Значит верно, что листы в C++ нужно использовать когда необходимо часто делать вставки в середине? Т.к. они обеспечивают большую скорость?
Я не могу понять вот что, чтобы вставить на туже 5-ю позицию ведь все равно необходимо пройти до 5-го эл. чтобы потом связать указатели?
Я об этом же, но в cplusplus.com/reference/ рекомендуется использовать листы для вставки данных в середину, и написано, что доступ ко всем элементам занимает константное (одно) время: "Lists are sequence containers that allow constant time insert and erase operations anywhere within the sequence, and iteration in both directions."