Программирование. Принципы и практика использования C++ Исправленное издание, стр. 282

20.8. Адаптация нашего класса vector к библиотеке STL

После добавления функций

begin()
,
end()
и инструкций
typedef
в разделе 20.5 в классе vector не достает только функций
insert()
и
erase()
, чтобы стать близким аналогом класса
std::vector
.

template<class T, class A = allocator<T> > class vector {

  int sz;    // размер

  T* elem;   // указатель на элементы

  int space; // количество элементов плюс количество свободных ячеек

  A alloc;   // использует распределитель памяти для элементов

public:

  // ...все остальное описано в главе 19 и разделе 20.5...

  typedef T* iterator; // T* — максимально простой итератор

  iterator insert(iterator p, const T& val);

  iterator erase(iterator p);

};

Здесь мы снова в качестве типа итератора использовали указатель на элемент типа

T*
. Это простейшее из всех возможных решений. Разработку итератора, проверяющего выход за пределы допустимого диапазона, читатели могут выполнить в качестве упражнения (упр. 20).

 

Программирование. Принципы и практика использования C++ Исправленное издание - _001.png
 Как правило, люди не пишут операции над списками, такие как
insert()
и
erase()
, для типов данных, хранящихся в смежных ячейках памяти, таких как класс
vector
. Однако операции над списками, такие как
insert()
и
erase()
, оказались несомненно полезными и удивительно эффективными при работе с небольшими векторами или при небольшом количестве элементов. Мы постоянно обнаруживали полезность функции
push_back()
, как и других традиционных операций над списками.

По существу, мы реализовали функцию

vector<T,A>::erase()
, копируя все элементы, расположенные после удаляемого элемента (переместить и удалить). Используя определение класса
vector
из раздела 19.3.6 с указанными добавлениями, получаем следующий код:

template<class T, class A>

vector<T,A>::iterator vector<T,A>::erase(iterator p)

{

  if (p==end()) return p;

  for (iterator pos = p+1; pos!=end(); ++pos)

    *(pos–1) = *pos; // переносим элемент на одну позицию влево

  alloc.destroy(&*(end()-1)); // уничтожаем лишнюю копию

                              // последнего элемента

  ––sz;

  return p;

}

Этот код легче понять, если представить его в графическом виде.

Программирование. Принципы и практика использования C++ Исправленное издание - _233.png

Код функции

erase()
довольно прост, но, возможно, было бы проще попытаться разобрать несколько примеров на бумаге. Правильно ли обрабатывается пустой объект класса
vector
? Зачем нужна проверка
p==end()
? Что произойдет после удаления последнего элемента вектора? Не было бы легче читать этот код, если бы мы использовали индексирование?

Реализация функции

vector<T,A>::insert()
является немного более сложной.

template<class T, class A>

vector<T,A>::iterator vector<T,A>::insert(iterator p, const T& val)

{

  int index = p–begin();

  if (size()==capacity())

    reserve(size() = 0 ? 8 : 2*size()); // убедимся, что

                                        // есть место

  // сначала копируем последний элемент в неинициализированную ячейку:

  alloc.construct(elem+sz,*back());

  ++sz;

  iterator pp = begin()+index; // место для записи значения val

  for (iterator pos = end()–1; pos!=pp; ––pos)

    *pos = *(pos–1); // переносим элемент на одну позицию вправо

  *(begin()+index) = val; // "insert" val

  return pp;

}

Обратите внимание на следующие факты.

• Итератор не может ссылаться на ячейку, находящуюся за пределами последовательности, поэтому мы используем указатели, такие как

elem+space
. Это одна из причин, по которым распределители памяти реализованы на основе указателей, а не итераторов.

• Когда мы используем функцию

reserve()
, элементы могут быть перенесены в новую область памяти. Следовательно, мы должны запомнить индекс вставленного элемента, а не итератор, установленный на него. Когда элементы вектора перераспределяются в памяти, итераторы, установленные на них, становятся некорректными — их можно интерпретировать как ссылки на старые адреса.

• Наше использование распределителя памяти

A
является интуитивным, но не точным. Если вам придется реализовывать контейнер, то следует внимательно изучить стандарт.

• Тонкости, подобные этим, позволяют избежать непосредственной работы с памятью на нижнем уровне. Естественно, стандартный класс

vector
, как и остальные стандартные контейнеры, правильно реализует эти важные семантические тонкости. Это одна из причин, по которым мы настоятельно рекомендуем использовать стандартную библиотеку, а не “кустарные” решения.

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

insert()
и
erase()
к среднему элементу вектора, состоящего из 100 тыс. элементов; для этого лучше использовать класс
list
(и класс map; см. раздел 21.6). Однако операции
insert()
и
erase()
можно применять ко всем векторам, а их производительность при перемещении небольшого количества данных является непревзойденной, поскольку современные компьютеры быстро выполняют такое копирование (см. упр. 20). Избегайте (связанных) списков, состоящих из небольшого количества маленьких элементов.