Шрифт:
Для сравнения мы проделали то же самое с объектом класса
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
? Что произойдет после удаления последнего элемента вектора? Не было бы легче читать этот код, если бы мы использовали индексирование?