C++. Сборник рецептов

 // У списка нет произвольного доступа, так что
 // требуется использовать 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, показывающий, как это сделать.

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

#include <string>
#include <iostream>
using namespace std;
int main() {
 string s = '';
 string sr = '';
 sr.reserve(9000);
 cout << 's.length = ' << s.length( ) << '
';
 cout << 's.capacity = ' << s.capacity( ) << '
';
 cout << 's.max.size = ' << s.max_size() << '
';
 cout << 'sr.length = ' << sr.length() << '
';
 cout << 'sr.capacity = ' << sr.capacity() << '
';
 cout << 'sr.max_size = ' << sr.max_size() << '
';
 for (int i = 0; i < 10000; ++i) {
  if (s.length() == s.capacity()) {
   cout << 's достигла емкости ' << s.length() << увеличение... 
';
  }
  if (sr.length() == sr.capacity()) {
   cout << 'sr достигла емкости ' << sr.length() << ', увеличение...
';
  }
  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. Также следует провести эксперименты с имеющейся реализацией стандартной библиотеки и посмотреть, как она выполняет увеличение строк.