[] оператор для std :: list?

Question

Я нахожусь в ситуации, когда я не могу использовать vector, потому что я использую &element[x], затем добавляю больше элементов, чтобы указатель стал недействительным.Проблема в том, что std::list не перегружает operator [] и не обеспечивает метод at().Поэтому единственный способ, которым я могу смоделировать at(), - использовать итератор.Однако есть ли лучший способ сделать это?

Answer 1

Возможно, вам следует пересмотреть свой дизайн.

Попытка эмулировать operator[] или at для std::list приведет к падению производительности: эти операции потребуют O (N)и не время O (1), поскольку std::list::iterator является двунаправленным итератором, а не итератором произвольного доступа.Так что, если вы теперь перебираете контейнер и вызываете [] или at для каждого элемента, это приведет к O (N * N) вместо O (N).

Вот почему эти операции не предусмотреныstd::list.

Answer 2

#include <iterator>

std::list<int> l;
std::list<int>::iterator it = l.begin();
std::advance(it, 37);

Для итераторов без произвольного доступа (например, для list) это, конечно, займет линейное время.

Answer 3

Нет std :: list - это связанный список.Прямой доступ к одному элементу невозможен.Единственная возможность это перебирать элементы с самого начала.