справедливыми. Вставка единственного элемента в вектор линейна относительно расстояния от точки вставки до конца вектора. Амортизированная сложность во время жизни вектора, вставляющего единственный элемент в свой конец, постоянна. Вставка множественных элементов в вектор с единственным вызовом вставляющей функции-члена линейна относительно суммы числа элементов плюс расстояние до конца вектора. Другими словами, намного быстрее вставить много элементов в середину вектора сразу, чем делать вставку по одному элементу. Шаблонная вставляющая функция-член предраспределяет достаточно памяти для вставки, если итераторы first и last относятся к последовательной, двунаправленной или произвольного доступа категориям. Иначе функция вставляет элементы один за другим и не должна использоваться для вставки в середину векторов.
erase (стирание) делает недействительными все итераторы и ссылки после пункта стирания. Деструктор T вызывается столько раз, каково число стёртых элементов, а оператор присваивания T вызывается столько раз, каково число элементов в векторе после стёртых элементов.
Чтобы оптимизировать распределение места, даётся определение для bool.
class vector‹bool, allocator› {
public:
// битовая ссылка (bit reference):
class reference {
public:
~reference();
operator bool() const;
reference& operator=(const bool x);
void flip(); // инвертирует бит (flips the bit)
};
// определения типов (typedefs):
typedef bool const_reference;
typedef iterator;
typedef const_iterator;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
typedef bool value_type;
typedef reverse_iterator;
typedef const_reverse_iterator;
// размещение/освобождение (allocation/deallocation):
vector();
vector(size_type n, const bool& value = bool());
vector(const vector‹bool, allocator›& x);
template ‹class InputIterator›
vector(InputIterator first, InputIterator last);
~vector();
vector‹bool, allocator›& operator=(const vector‹bool, allocator›& x);
void reserve(size_type n);
void swap(vector‹bool, allocator›& x);
// средства доступа (accessors):
iterator begin();
const_iterator begin() const;
iterator end();
const_iterator end() const;
reverse_iterator rbegin();
const_reverse_iterator rbegin();
reverse_iterator rend();
const_reverse_iterator rend();
size_type size() const;
size_type max_size() const;
size_type capacity() const;
bool empty() const;
reference operator[](size_type n);
const_reference operator[](size_type n) const;
reference front();
const_reference front() const;
reference back();
const_reference back() const;
// вставка/стирание (insert/irase):
void push_back(const bool& x);
iterator insert(iterator position, const bool& x = bool());
void insert(iterator position, size_type n, const bool& x);
template ‹class InputIterator›
void insert(iterator position, InputIterator first, InputIterator last);
void pop_back();
void erase(iterator position);
void erase(iterator first, iterator last);
};
void swap(vector‹bool, allocator›::reference x, vector‹bool, allocator›::reference y);
bool operator==(const vector‹bool, allocator›& x, const vector‹bool, allocator›& y);
bool operator‹(const vector‹bool, allocator›& x, const vector‹bool, allocator›& y);
reference - класс, который имитирует поведение ссылок отдельного бита в vector‹bool›.
Ожидается, что каждое исполнение обеспечит определение vector‹bool› для всех поддерживаемых моделей памяти.
Сейчас невозможно шаблонизировать определение. То есть мы не можем написать:
template ‹template ‹class U› class Allocator = allocator›
class vector‹bool, Allocator› {/*… */};
Поэтому обеспечивается только vector‹bool, Allocator›.
Список (List)
list - вид последовательности, которая поддерживает двунаправленные итераторы и позволяет операции вставки и стирания с постоянным временем в любом месте последовательности, с управлением памятью, обрабатываемым автоматически. В отличие от векторов и двусторонних очередей, быстрый
