Контейнеры STL. Возможности списков

   
На этом шаге мы перечислим отличительные особенности списков.

   
По своей внутренней структуре списки полностью отличаются от векторов и деков. Важнейшие различия перечислены ниже.

  • Список не поддерживает произвольный доступ к элементам. Например, чтобы обратиться к пятому элементу, необходимо
    перебрать первые четыре элемента по цепочке ссылок. Это означает, что обращение к произвольному элементу списка выполняется
    относительно медленно.
  • Вставка и удаление элементов в любой позиции выполняются быстро, причем не только с концов контейнера. Вставка и
    удаление всегда выполняются с постоянным временем, поскольку не требуют перемещения других элементов. Во внутренней
    реализации изменяются только значения нескольких указателей.
  • В результате вставки и удаления элементов указатели, ссылки и итераторы, относящиеся к другим элементам, остаются
    действительными.
  • Обработка исключений в списках реализована так, что практически каждая операция завершается успешно или не вносит
    изменений. Иначе говоря, список не может оказаться в промежуточном состоянии, в котором операция завершена только наполовину.
    Эти принципиальные различия отражены в функциях списков, что делает их непохожими на функции векторов и деков.
  • Поскольку списки не поддерживают произвольный доступ к элементам, в них не определены ни оператор индексирования,
    ни функция at().
  • Списки не поддерживают операции, связанные с емкостью и перераспределением памяти, потому что такие операции просто
    не нужны. У каждого элемента имеется собственная память, которая остается действительной до удаления элемента.
  • Списки поддерживают много специальных функций для перемещения элементов. Эти функции класса представляют собой
    оптимизированные версии одноименных универсальных алгоритмов. Оптимизация основана на замене указателей вместо копирования
    и перемещения значений.

   
Со следующего шага мы начнем знакомиться с операциями над списками.



Вы можете оставить комментарий, или Трекбэк с вашего сайта.

Оставить комментарий