Д. Стефенс - C++. Сборник рецептов

• Название: C++. Сборник рецептов
• Автор: Д. Стефенс
• Издательство: КУДИЦ-ПРЕСС
• Жанр: Программирование
• Год: 2007
• ISBN: 5-91136-030-6

Данная книга написана экспертами по C++ и содержит готовые рецепты решения каждодневных задач для программистов на С++. Один из авторов является создателем библиотеки Boost Iostreams и нескольких других библиотек C++ с открытым исходным кодом. В книге затрагивается множество тем, вот лишь некоторые из них: работа с датой и временем; потоковый ввод/вывод; обработка исключений; работа с классами и объектами; сборка приложений; синтаксический анализ XML-документов; программирование математических задач. Читатель сможет использовать готовые решения, а сэкономленное время и усилия направить на решение конкретных задач.

---

s1 = "abcdXXXabcd";

trim_if(s1, is_from_range('a', 'd'));

cout << "s1 = " << s1 << endl; // Теперь s1 = XXX

Заметьте, что эта конструкция чувствительна к регистру, так как диапазон от а до d не включает заглавных версий этих букв.

4.3. Хранение строк в последовательности

Проблема

Требуется сохранить набор строк в виде последовательности, которая ведет себя как массив.

Решение

Для хранения строк в виде массива используйте vector. Пример 4.6 показывает простой образец.

Пример 4 6. Хранение строк в векторе

#include <string>

#include <vector>

#include <iostream>

using namespace std;

int main() {

 vector<string> v;

 string s = "one";

 v.push_back(s);

 s = "two";

 v.push_back(s);

 s = "three";

 v.push_back(s);

 for (int i = 0; i < v.size(); ++i) {

  cout << v[i] << "\n";

 }

}

vector использует для произвольного доступа семантику массива (а также делает много другого), так что он прост и понятен в использовании. Однако vector — это только одна из многих последовательностей стандартной библиотеки. Чтобы узнать об этом побольше, читайте дальше.

Обсуждение

vector — это динамическая последовательность объектов, которая предоставляет произвольный доступ с помощью оператора в стиле массивов operator[]. Метод push_back при помощи копирующего конструктора копирует свой аргумент, добавляет копию в последний элемент вектора и увеличивает его размер на единицу. pop_back выполняет обратную операцию, удаляя последний элемент. Вставка и удаление элементов в конце вектора занимает постоянное время, а время вставки и удаления элементов в середине вектора линейно зависит от его размера. Это основы векторов. Кроме этого, они умеют еще много чего.

В большинстве случаев vector должен быть первым выбором вместо массива в стиле С. Во-первых, их размеры изменяются динамически, что означает, что эти размеры увеличиваются по мере необходимости. Не требуется проводить каких-либо исследований для выбора оптимального размера статического массива, как в случае с массивами С, — vector растет по мере надобности, а при необходимости может быть увеличен или уменьшен вручную. Во-вторых, vector при использовании метода at (но не при использовании operator[]) предлагает проверку границ, так что при ссылке на несуществующий индекс программа не обрушится и не продолжит выполнение с неверными данными. Посмотрите на пример 4.7, Он показывает, как работать с индексами, выходящими за границы массива.

Пример 4.7. Проверка границ для векторов

#include <iostream>

#include <vector>

#include <exception>

using namespace std;

int main() {

 char carr[] = {'a', 'b', 'c', 'd', 'e'};

 cout << carr[100000] << '\n'; // Оп, кто знает, что дальше

                               // произойдет

 vector<char> v;

 v.push_back('a');

 v.push_back('b');

 v.push_back('c');

 v.push_back('d');

 v push_back('e');

 try {

  cout << v.at(10000) << "\n"; // at проверяет границы и выбрасывает

 } catch(out_of_range& е) {    // out_of_range, если произошел выход за них

  cerr << e.what() << '\n';

 }

}

Перехват out_of_range, определенного в <stdexcept>, позволяет грамотно справиться с неправильными индексами. А также можно вызвать метод what, позволяющий в зависимости от используемой реализации получить осмысленное сообщение об ошибке, как возвращаемая в коде примера 4.7:

invalid vector<T> subscript

Однако vector не является единственной возможностью. В C++ имеется большое количество способов хранить последовательности. Кроме vector имеются list, set и двунаправленные очереди (deque — double-ended queue). Все они поддерживают множество одинаковых операций, и каждый поддерживает свои собственные. Кроме того, каждый имеет различную алгоритмическую сложность, требования по хранению и семантику. Так что имеется богатый выбор.

Посмотрите внимательно на пример 4.6. Вы, вероятно, обратите внимание, что я изменяю значение строки s до того, как добавляю ее в конец контейнера с помощью push_back. Логично ожидать такого вывода этого примера

three

three

three

Я поместил в вектор одну и ту же строку три раза, так что каждый раз, когда я переприсваиваю строку, разве не должны все элементы вектора указывать на одну и ту же строку? Нет. Это важный момент, касающийся контейнеров STL.

Контейнеры STL сохраняют копии объектов, помещаемых в них, а не сами объекты. Так что после помещения в контейнер всех трех строк в памяти остается четыре строки: три копии, созданные и хранящиеся в контейнере, и одна копия, которой присваиваются значения.

Ну и что? Было создано несколько новых копий: большое дело. Но это действительно большое дело, так как если используется большое количество строк, за каждую копию приходится платить процессорным временем, памятью или и тем и другим. Копирование элементов в контейнерах — это намеренное поведение STL, и все контейнеры организованы именно так.

Одним из решений (определенно не единственным) является хранение в контейнере указателей. Но помните, что контейнер не удаляет с помощью delete указатели при его уничтожении. Память для указателей выделяет ваш код, так что он и должен ее очищать. Это относится и к ситуации, когда происходит полное удаление контейнера и когда удаляется только один его элемент.

В целях создания альтернативного решения давайте рассмотрим еще одну возможность. Рассмотрим шаблон класса list, определенный в <list>, который является двусвязным списком (doubly linked list). Если планируется большое количество вставок и удалений элементов в середине последовательности или если требуется гарантировать, что итераторы, указывающие на элементы последовательности, не станут недействительными при ее изменении, используйте list. Пример 4.8 вместо vector для хранения нескольких строк типа string использует list. Также он для перебора этих строк и печати вместо оператора индекса, как это делается в случае с простыми массивами, использует for_each.

Пример 4.8. Хранение строк в списке

#include <string>

#include <list>

#include <algorithm>

#include <iostream>

using namespace std;

void write(const string& s) {

 cout << s << '\n';

}

int main() {

 list<string> lst;

 string s = "нож";

 lst.push_front(s);

 s = "вилка";

 lst.push_back(s);

 s = "ложка";

 lst.push_back(s);

 // У списка нет произвольного доступа, так что

 // требуется использовать for_each()

 for_each(lst.begin(), lst.end(), write);

}

Целью этого отступления от первоначальной проблемы (хранения строк в виде последовательностей) является краткое введение в последовательности STL. Здесь невозможно дать полноценное описание этого вопроса. За обзором STL обратитесь к главе 10 книги C++ in a Nutshell Рэя Лишнера (Ray Lischner) (O'Reilly).

4.4. Получение длины строки

Проблема

Требуется узнать длину строки.

Решение

Используйте метод length класса string.

std::string s = "Raising Arizona";

int i = s.length();

Обсуждение

Получение длины строки — это тривиальная задача, но она является хорошей возможностью обсудить схему размещения string (как узких, так и широких символов). string, в отличие от массивов строк, завершаемых нулем, в С являются динамическими и увеличиваются по мере надобности. Большая часть реализаций стандартной библиотеки начинают с относительно низкой емкости и увеличивают ее в два раза каждый раз, когда достигается предел. Знание того, как анализировать этот рост, если и не точного алгоритма, помогает диагностировать проблемы производительности, связанные со строками.

Символы в basic_string хранятся в буфере, который является единым фрагментом памяти статического размера. Этот буфер, используемый строкой, изначально имеет некий размер, и по мере добавления в строку символов он заполняется до тех пор, пока не будет достигнут предел его емкости. Когда это происходит, буфер увеличивается. В частности, выделяется новый буфер большего размера, символы копируются из старого буфера в новый, и старый буфер удаляется.

Определить размер буфера (не число символов, в нем содержащихся, а его максимальный размер) можно с помощью метода capacity. Если требуется вручную установить емкость и избежать ненужных копирований буфера, используйте метод reserve и передайте ему числовой аргумент, указывающий требуемый размер буфера. Также имеется максимально возможный размер буфера, получить который можно с помощью вызова max_size. Это все можно использовать, чтобы посмотреть на расходование памяти в данной реализации стандартной библиотеки. Посмотрите на пример 4.9, показывающий, как это сделать.