Программирование

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

  Объект класса list занимает по меньшей мере в три раза больше памяти, чем остальные три альтернативы, — в компьютере объект класса list использует 12 байтов на элемент; объект класса vector — один байт на элемент. Для большого количества символов это обстоятельство может оказаться важным. В чем заключается преимущество класса 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 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::erase(), копируя все элементы, расположенные после удаляемого элемента (переместить и удалить). Используя определение класса vector из раздела 19.3.6 с указанными добавлениями, получаем следующий код:

template

vector::iterator vector::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::insert() является немного более сложной.

template

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

{

  int index = p–begin();