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

Символы в 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( ) << '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. Это метод, который возвращает истину, если длина строки равна нулю.

4.5. Обращение строк

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

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

std::reverse(s.begin(), s.end());

reverse работает очень просто: она изменяет диапазон, переданный ей, так, что его порядок меняется на обратный оригинальному. Время, необходимое для этого, линейно зависит от длины диапазона.

В случае, если требуется скопировать строку в другую строку, но в обратном порядке символов, используйте реверсивные итераторы, как здесь:

std::string s = "Los Angeles";

std::string rs;

rs.assign(s.rbegin(), s.rend());

rbegin и rend возвращают реверсивные итераторы. Реверсивные итераторы ведут себя так, как будто они просматривают последовательность в обратном порядке. rbegin возвращает итератор, который указывает на последний элемент, a rend возвращает итератор, указывающий на позицию перед первым элементом. Это в точности обратно тому, что делают begin и end.

Но должны ли вы обращать строку? С помощью rbegin и rend для обратной строки можно использовать все методы или алгоритмы, работающие с диапазонами итераторов. А если требуется выполнить поиск в строке, то можно использовать rfind, которая делает то же, что и find, но начинает с конца строки и движется к ее началу. Для больших строк или большого количества строк обращение может оказаться очень дорогостоящим, так что при возможности избегайте его.

4.6. Разделение строки

Требуется разделить строку с разделителями на несколько строк. Например, может потребоваться разделить строку "Name|Address|Phone" на три отдельных строки — "Name", "Address" и "Phone", удалив при этом разделитель.

Для перехода от одного вхождения разделителя к следующему используйте метод find класса basic_string, а для копирования каждой подстроки используйте substr. Для хранения результатов используйте любую стандартную последовательность. Пример 4.10 использует vector.

Пример 4.10. Разделение строки с разделителями

#include <string>

#include <vector>

#include <functional>

#include <iostream>

using namespace std;

void split(const string& s, char c, vector<string>& v) {

 string::size_type i = 0;

 string::size_type j = s.find(c);

 while (j != string::npos) {

  v.push_back(s.substr(i, j-i));

  i = ++j;

  j = s.find(c, j);

  if (j == string::npos)

   v.push_back(s.substr(i, s.length()));

 }

}

int main() {

 vector<string> v;

 string s = "Account Name|Address 1|Address 2 |City";

 split(s, '|', v);

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

  cout << v[i] << 'n';

 }

}

Превращение приведенного выше примера в шаблон функции, принимающий любой тип символов, тривиально — просто параметризуйте тип символов и замените случаи использования string на basic_string<T>.

template<typename T>

void split(const basic_string<T>& s, T c,

 vector<basic_string<T> >& v) {

 basic_string<T>::size_type i = 0;

 basic_string<T>::size_type j = s.find(c);

 while (j != basic_string<T>::npos) {

  v.push_back(s.substr(i, j-i));

  i = ++j;

  j = s.find(c, j);

  if (j == basic_string<T>::npos)

   v.push back(s.substr(i, s.length()));

 }

}

Логика при этом не меняется.

Однако обратите внимание, что между двумя последними угловыми скобками в последней строке заголовка функции добавлен один пробел. Это требуется для того, чтобы сказать компилятору, что это не оператор сдвига вправо.

Пример 4.10 разбивает строку с помощью простого алгоритма. Начиная с начала строки, он ищет первое вхождение разделителя с, а затем считает, что все, что стоит после начала строки или предыдущего найденного вхождения и до этого вхождения, является очередным фрагментом текста. Для поиска первого вхождения символа в оригинальной строке string пример использует метод find, а для копирования символов диапазона в новую string, помещаемую в vector, — метод substr. Это тот же самый принцип, который используется в функциях разбиения строк большинства скриптовых языков и является специальным случаем разделения строки текста на лексемы (tokenizing), описываемого в рецепте 4.7.

Разделение строки, использующей единственный символ-разделитель, является очень распространенной задачей, и неудивительно, что ее решение есть в библиотеке Boost String Algorithms. Оно просто в использовании. Чтобы увидеть, как разделить строку с помощью функции split из Boost, посмотрите на пример 4.11.