И снова мы оказались там, откуда начинали. Однако, в отличие от класса 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
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
, копируя все элементы, расположенные после удаляемого элемента (переместить и удалить). Используя определение класса vector
из раздела 19.3.6 с указанными добавлениями, получаем следующий код:
template
vector
{
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
является немного более сложной.
template
vector
{
int index = p–begin();