Почему нет оператора [] для std :: list?

Question

Может кто-нибудь объяснить, почему оператор [] не реализован для std :: list? Я искал немного, но не нашел ответа. Это не было бы слишком сложно реализовать, или я что-то упустил?

Answer 1

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

 std::list<int> xs;
 for (int i = 0; i < xs.size(); ++i) {
     int x = xs[i];
     ...
 }

что O (n ^ 2) - очень противно. Поэтому в стандарте ISO C ++ конкретно упоминается, что все последовательности STL, которые поддерживают operator[], должны делать это в амортизированном постоянном времени (23.1.1 [lib.sequence.reqmts] / 12), что достижимо для vector и deque, но не list.

Для случаев, когда вам действительно нужны такие вещи, вы можете использовать std::advance алгоритм:

int iter = xs.begin();
std::advance(iter, i);
int x = *iter;

Answer 2

Это не будет слишком сложно (для разработчика), но это будет слишком сложно во время выполнения, поскольку производительность в большинстве случаев будет ужасной. Принуждение пользователя просматривать каждую ссылку сделает более очевидным, что там происходит, чем «myList [102452]».

Answer 3

Я думаю, что нашел ответ в другом сообщении SO Расширение std :: list

"ваш оператор [] имеет время O (N)" - именно поэтомуон не включен в стандарт std :: list <>.- Майкл Барр, 14 декабря в 17: 29

И все же, это единственная причина?

РЕДАКТИРОВАТЬ: Кажется, что, как уже упоминали люди, это больше вопрос согласованности в отношении производительности, чемстрого производительность.

Answer 4

На самом деле, нет абсолютно никаких причин не указывать оператор [] или хотя бы метод в (int) по двум причинам:

• Это двойной связанный список, поэтому вам нужно переместить самое большее size () / 2, чтобы разместить ваш итератор для получения индекса, а затраты на внутреннее хранение нескольких фиксированных итераторов очень малы. И, наконец, библиотека Qt предоставляет оператор [] и at, и я не вижу затрат на производительность при ее использовании.
• принуждение людей что-либо не использовать - очень плохая привычка программирования, потому что список будет очень полезным контейнером, если у вас есть «произвольный доступ» рядом со связанным доступом, есть множество примеров, когда вам нужны оба доступа, в зависимости какая точка выполнения.