Руководство по стандартной библиотеке шаблонов STL


Вектор (Vector) - часть 3


    insert (вставка) вызывает перераспределение, если новый размер больше, чем старая ёмкость. Если никакого перераспределения не происходит, все итераторы и ссылки перед точкой вставки остаются справедливыми. Вставка единственного элемента в вектор линейна относительно расстояния от точки вставки до конца вектора. Амортизированная сложность во время жизни вектора, вставляющего единственный элемент в свой конец, постоянна. Вставка множественных элементов в вектор с единственным вызовом вставляющей функции-члена линейна относительно суммы числа элементов плюс расстояние до конца вектора. Другими словами, намного быстрее вставить много элементов в середину вектора сразу, чем делать вставку по одному элементу. Шаблонная вставляющая функция-член предраспределяет достаточно памяти для вставки, если итераторы first и last относятся к последовательной, двунаправленной или произвольного доступа категориям. Иначе функция вставляет элементы один за другим и не должна использоваться для вставки в середину векторов.

    erase (стирание) делает недействительными все итераторы и ссылки после пункта стирания. Деструктор T вызывается столько раз, каково число стёртых элементов, а оператор присваивания T вызывается столько раз, каково число элементов в векторе после стёртых элементов.

    Чтобы оптимизировать распределение места, даётся определение для bool.

class vector { 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& x); template vector(InputIterator first, InputIterator last); ~vector(); vector& operator=(const vector& x); void reserve(size_type n); void swap(vector& 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 void insert(iterator position, InputIterator first, InputIterator last); void pop_back(); void erase(iterator position); void erase(iterator first, iterator last); }; void swap(vector::reference x, vector::reference y); bool operator==(const vector& x, const vector& y); bool operator& x, const vector& y);

    reference - класс, который имитирует поведение ссылок отдельного бита в vector.

    Ожидается, что каждое исполнение обеспечит определение vector для всех поддерживаемых моделей памяти.

Сейчас невозможно шаблонизировать определение. То есть мы не можем написать: template class Allocator == allocator> class vector { /* ... */ }; Поэтому обеспечивается только vector.



Начало  Назад  Вперед