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()); // убедимся, что
// есть место
// сначала копируем последний элемент в неинициализированную ячейку:
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). Избегайте (связанных) списков, состоящих из небольшого количества маленьких элементов.
