26 Containers library [containers]

Контейнер последовательности организует конечный набор объектов одного типа в строго линейную структуру. Библиотека обеспечивает четыре основных видов контейнеров последовательности: vector,forward_­list,list, иdeque. Кроме того, array предоставляется как контейнер последовательности, который обеспечивает ограниченные операции последовательности, поскольку он имеет фиксированное количество элементов. Библиотека также предоставляет адаптеры контейнеров, которые упрощают создание абстрактных типов данных, таких какstacks илиqueues, из основных типов контейнеров последовательностей (или из других типов контейнеров последовательностей, которые может определить пользователь).

Контейнеры последовательностей предлагают программисту различные компромиссы сложности и должны использоваться соответственно. vector илиarray - это тип контейнера последовательности, который следует использовать по умолчанию. list илиforward_­list должен использоваться, когда есть частые вставки и удаления из середины последовательности. deque - это предпочтительная структура данных, когда большинство вставок и удалений происходит в начале или в конце последовательности.

В таблицах87 и88, X обозначает класс контейнера последовательности, a обозначает значение типа ,X содержащего элементы типаT, u обозначает имя переменной объявляется, A означает ,X​::​allocator_­type если qualified-idX​::​allocator_­type является действительным , и обозначает тип ([temp.deduct]) , а allocator<T> не тогда , когда это произойдет, i иj обозначают итераторы удовлетворение требований входного итератора и ссылка на элементы, неявно конвертируемые вvalue_­type, [i, j) обозначает допустимый диапазон, il обозначает объект типаinitializer_­list<value_­type>, n обозначает значение типаX​::​size_­type, p обозначает допустимый итератор константы для a,q обозначает допустимый разыменовываемый итератор константы a,[q1, q2) обозначает допустимый диапазон констант итераторы в a,t обозначает lvalue или const rvalue для X​::​value_­typeиrv обозначает неконстантное rvalue дляX​::​value_­type. Args обозначает пакет параметров шаблона; args обозначает пакет параметров функции с шаблономArgs&&.

Сложность выражений зависит от последовательности.

Итератор вернулся из a.insert(p, t) точек в копию, t вставленную в a.

Итератор вернулся изa.insert(p, rv) точек в копию,rv вставленную вa.

Итератор вернулся изa.insert(p, n, t) точек в копию первого вставленного элементаa, илиp ifn == 0.

Итератор вернулся изa.insert(p, i, j) точек в копию первого вставленного элементаa, илиp ifi == j.

Итератор вернулся изa.insert(p, il) точек в копию первого вставленного элементаaилиp еслиil он пуст.

Итератор вернулся изa.emplace(p, args) точек в новый элемент, созданный изargs вa.

Итератор вернулся из a.erase(q) точек в элемент, следующий непосредственно за q стираемым элементом. Если такого элемента не существует, a.end() возвращается.

Итератор, возвращаемый a.erase(q1, q2) точкой, указывает элемент, на который указывает q2 до того, как какие-либо элементы будут удалены. Если такого элемента не существует, a.end() возвращается.

Для каждого контейнера последовательности, определенного в этом Пункте и Пункте[strings]:

• (13.1)

  Если конструктор

  template <class InputIterator>
    X(InputIterator first, InputIterator last,
      const allocator_type& alloc = allocator_type());

  вызывается с типомInputIterator , который не квалифицируется как итератор ввода, то конструктор не должен участвовать в разрешении перегрузки.

• (13.2)

  Если функции-члены форм:

  template <class InputIterator>
    return-type F(const_iterator p,
                  InputIterator first, InputIterator last);       // such as insert
  
  template <class InputIterator>
    return-type F(InputIterator first, InputIterator last);       // such as append, assign
  
  template <class InputIterator>
    return-type F(const_iterator i1, const_iterator i2,
                  InputIterator first, InputIterator last);       // such as replace
  

  вызываются с типомInputIterator , который не квалифицируется как итератор ввода, то эти функции не должны участвовать в разрешении перегрузки.

• (13.3)

  Руководство по дедукции для контейнера последовательности не должно участвовать в разрешении перегрузки, если у него естьInputIterator параметр шаблона и для этого параметра выводится тип, который не квалифицируется как итератор ввода, или если у него естьAllocator параметр шаблона и тип, который не соответствует требованиям. как распределитель для этого параметра.

В таблице88 перечислены операции, которые предусмотрены для одних типов контейнеров последовательностей, но не для других. Реализация должна обеспечивать эти операции для всех типов контейнеров, показанных в столбце «контейнер», и должна реализовывать их так, чтобы использовать амортизированное постоянное время.

Функция-член at() обеспечивает доступ к элементам контейнера с проверкой границ. at() кидает out_­of_­range если n >= a.size().