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

функцию в качестве аргумента, напишите количество символов в передаваемой строке, попытайтесь сравнить его со строкой "Hello" в функции (чтобы убедиться, что вы действительно передали строку "Hello"), а затем сравните аргумент со строкой "Howdy", чтобы увидеть, какое из этих слов появляется в словаре первым. Скопируйте аргумент в другую переменную того же типа.

ПОПРОБУЙТЕ

Выполните предыдущее задание ПОПРОБУЙТЕ для массива объектов типа int, vector<int> и list<int> со значениями { 1, 2, 3, 4, 5 } . 

20.7.1. Операции insert и erase

 

 В качестве контейнера по умолчанию используется стандартный класс vector. Он имеет большинство желательных свойств, поэтому альтернативу следует использовать только при необходимости. Его основной недостаток заключается в том, что при выполнении операций, характерных для списка (insert() и erase()), в векторе происходит перемещение остальных элементов; это может оказаться связано с неприемлемыми затратами, если вектор содержит большое количество элементов или элементы вектора сами являются крупными объектами. Однако слишком беспокоиться об этом не следует. Мы без заметных проблем считали полмиллиона значений с плавающей точкой в вектор, используя функцию push_back(). Измерения подтвердили, что предварительное выделение памяти не приводит к заметным последствиям. Прежде чем вносить значительные изменения, стремясь к эффективности, проведите измерения (угадать степень эффективности кода трудно даже экспертам).

 

 Как указывалось в разделе 20.6, перемещение элементов связано с логическим ограничением: выполняя операции, характерные для списков (такие как insert(), erase(), and push_back()), не следует хранить итераторы или указатели на элементы вектора. Если элемент будет перемещен, ваш итератор или указатель будет установлен на неправильный элемент или вообще может не ссылаться на элемент вектора. В этом заключается принципиальное преимущество класса list (и класса map; см. раздел 21.6) над классом vector. Если вам необходима коллекция крупных объектов или приходится ссылаться на объекты во многих частях программы, рассмотрите возможность использовать класс list.

Сравним функции insert() и erase() в классах vector и list. Сначала рассмотрим пример, разработанный специально для того, чтобы продемонстрировать принципиальные моменты.

vector<int>::iterator p = v.begin();  // получаем вектор

++p; ++p; ++p;                        // устанавливаем итератор

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

vector<int>::iterator q = p;

++q;                                  // устанавливаем итератор

                                      // на 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; // количество элементов плюс количество свободных ячеек