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

  // на 5-й элемент

 p = v.insert(p,99); // итератор p ссылается на вставленный элемент

Теперь итератор q является неправильным. При увеличении размера вектора элементы могли быть перемещены в другое место. Если вектор v имеет запас памяти, то он будет увеличен на том же самом месте, а итератор q скорее всего будет ссылаться на элемент со значением 3, а не на элемент со значением 4, но не следует пытаться извлечь из этого какую-то выгоду.

 p = v.erase(p); // итератор p ссылается на элемент,
  // следующий за стертым

Иначе говоря, если за функцией insert следует функция erase, то содержание вектора не изменится, но итератор q станет некорректным. Однако если между ними мы переместим все элементы вправо от точки вставки, то вполне возможно, что при увеличении размера вектора v все элементы будут размещены в памяти заново.

Для сравнения мы проделали то же самое с объектом класса list:

 list<int>::iterator p = v.begin; // получаем список
 ++p; ++p; ++p; // устанавливаем итератор
  // на 4-й элемент
 list<int>::iterator q = p;
 ++q; // устанавливаем итератор
  // на 5-й элемент

 p = v.insert(p,99); // итератор р ссылается на вставленный элемент

Обратите внимание на то, что итератор q по-прежнему ссылается на элемент, имеющий значение 4.

 p = v.erase(p); // итератор р ссылается на элемент, следующий
  // за удаленным

И снова мы оказались там, откуда начинали. Однако, в отличие от класса vector, работая с классом list, мы не перемещали элементы, и итератор q всегда оставался корректным.

Объект класса list<char> занимает по меньшей мере в три раза больше памяти, чем остальные три альтернативы, — в компьютере объект класса list<char> использует 12 байтов на элемент; объект класса vector<char> — один байт на элемент. Для большого количества символов это обстоятельство может оказаться важным. В чем заключается преимущество класса vector над классом string? На первый взгляд, список их возможностей свидетельствует о том, что класс string может делать все то же, что и класс vector, и даже больше. Это оказывается проблемой: поскольку класс string может делать намного больше, его труднее оптимизировать. Оказывается, что класс vector можно оптимизировать с помощью операций над памятью, таких как push_back, а класс string — нет. В то же время в классе string можно оптимизировать копирование при работе с короткими строками и строками в стиле языка C. В примере, посвященном текстовому редактору, мы выбрали класс vector, так как использовали функции insert и delete. Это решение объяснялось вопросами эффективности. Основное логическое отличие заключается в том, что мы можем создавать векторы, содержащие элементы практически любых типов. У нас появляется возможность выбора, только если мы работаем с символами. В заключение мы рекомендуем использовать класс vector, а не string, если нам нужны операции на строками, такие как конкатенации или чтение слов, разделенных пробелами.

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).

Как правило, люди не пишут операции над списками, такие как 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;
 }

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

Код функции 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); // убедимся, что
  // есть место
  // сначала копируем последний элемент в неинициализированную ячейку: