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

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

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

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

#include

#include

#include

#include

using namespace std;

void write(const string& s) {

cout << s << '\n';

}

int main() {

list 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).

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

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

std::string s = "Raising Arizona";

int i = s.length();

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

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

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

Пример 4.9. Длина строки и ее емкость

#include

#include

using namespace std;

int main() {

string s = "";

string sr = "";

sr.reserve(9000);

cout << "s.length = " << s.length( ) << '\n';

cout << "s.capacity = " << s.capacity( ) << '\n';

cout << "s.max.size = " << s.max_size() << '\n';

cout << "sr.length = " << sr.length() << '\n';

cout << "sr.capacity = " << sr.capacity() << '\n';

cout << "sr.max_size = " << sr.max_size() << '\n';

for (int i = 0; i < 10000; ++i) {

if (s.length() == s.capacity()) {

cout << "s достигла емкости " << s.length() << увеличение... \n";

}

if (sr.length() == sr.capacity()) {

cout << "sr достигла емкости " << sr.length() << ", увеличение...\n";

}

s += 'x';

sr += 'x';

}

}

При использовании Visual C++ 7.1 вывод выглядит так.

s.length = 0

s.capacity = 15

s.max_size = 4294967294

sr.length = 0

sr.capacity = 9007

sr.max_size = 4294967294

s достигла емкости 15, увеличение...

s достигла емкости 31, увеличение...

s достигла емкости 47, увеличение...

s достигла емкости 70, увеличение...

s достигла емкости 105, увеличение...

s достигла емкости 157, увеличение...

s достигла емкости 235, увеличение...

s достигла емкости 352, увеличение...

s достигла емкости 528, увеличение...

s достигла емкости 792, увеличение...

s достигла емкости 1188, увеличение...

s достигла емкости 1782, увеличение...

s достигла емкости 2673, увеличение...

s достигла емкости 4009, увеличение...

s достигла емкости 6013, увеличение...

sr достигла емкости 9007, увеличение...

s достигла емкости 9019, увеличение...

Здесь происходит то, что буфер строки заполняется по мере добавления в него символов. Если буфер оказывается полон (т.е. длина = емкость), выделяется новый буфер, и символы оригинальной строки и новый добавляемый символ (или символы) копируются в этот новый буфер, sначинает заполняться с емкости 15 (зависит от компилятора), а затем увеличивается каждый раз примерно на 50%.

Если ожидается значительное увеличение строки или имеется большое количество строк, которые будут увеличиваться хотя бы немного, для минимизации числа перераспределений буфера используйте reserve. Также следует провести эксперименты с имеющейся реализацией стандартной библиотеки и посмотреть, как она выполняет увеличение строк.

Кстати, когда потребуется узнать, пуста ли строка, не сравнивайте ее размер с нулем, а просто вызовите метод empty. Это метод, который возвращает истину, если длина строки равна нулю.

Требуется обратить (реверсировать) строку.

Чтобы обратить строку «на месте», не используя временной строки, используйте шаблон функции reverse из заголовочного файла :