Работа со строками в C++. Часть 1: Основы

Среди всего спектра программного обеспечения, которое было разработано или же разрабатывается в настоящее время, вы вряд ли сможете найти сколь бы то ни было значимое число, не использующих текстовую информацию. Какие-то программы используют текст только для отображения названия элементов, другие являются приложениями для составления текстов, третьи принимают на вход один текст, а на выходе дают другой – вариантов ПО масса. Важно то, что так или иначе практически любое ПО использует в своей работе текст, а значит в языке, на котором программа пишется, должна присутствовать полноценная поддержка текста(строк). Конечно, сложно сравнивать программу, которая использует строки только для отображения элементов графического интерфейса и программу, которая анализирует входной текст и вычленяет некоторые его элементы – эти программы требует абсолютно разного уровня поддержки операций над текстом.

Принято считать(по крайней мере я с этим сталкивался), что C++ для этих целей не очень подходит и вместо C++ всегда предлагается python или еще какой-нибудь язык. Чтобы разобраться так это или нет нужно понимать какие возможности мы имеем с C++. Этому я и решил посвятить несколько статей(как минимум 3, а там посмотрим) – рассмотреть, что же можно сделать со строками на C++, насколько это удобно, и правда ли, что лучше использовать другой язык, когда речь заходит о сложной работе с текстом. В настоящей статье мы рассмотрим основы строк в C++: как они устроены, и что за базовые операция они предоставляют.

Строки в C++

Строки в C++ могут быть разделены на C-строки и C++-строки, где к первым относятся различные вариации char*, а ко вторым относятся вариации std::basic_string<…>. В рамках данного цикла мы будем рассматривать только C++-строки так как C-строки, по большей части, существуют как наследие C и самостоятельного интереса не представляют.

Итак, давайте разберемся, что из себя представляют строки в C++. Все C++-строки представлены как псевдонимы(alias) stb::basic_string<…>, созданные с различными параметрами, а параметров у basic_string три:

  1. Тип символа – т.е. то, чем будет является(его физическое представление) каждый символ составляющий строку.
  2. Тип представляющий характеристики символа. Т.е. то, как символы должны сравниваться между собой и т.п.
  3. Тип распределителя памяти(allocator) – позволяет задавать различные методы выделения памяти под строку. В рамках данного цикла статей, это параметр нам не интересен.

Таким образом basic_string есть ничто иное, как коллекция символов, с информацией о том, как можно соотносить символы между собой. В этом и заключается вся мощь basic_string, но тут же лежит и основная слабость. Вы можете создать строку из каких угодно символов, с каким угодно поведением и это, безусловно, весьма полезная особенность. Но это навсегда останется лишь коллекцией символов, в то время как строка текста не всегда может быть представлена просто набором символов. Любая много-байтовая кодировка делает basic_string как минимум не удобным в использовании классом, а если говорить откровенно, то сам класс basic_string, для много-байтовой кодировки, ни чем не лучше чем std::vector, т.е. простая, обобщённая коллекция.

Поясню на примере: самой базовой операцией, которую поддерживает basic_string есть получение длины строки. Так, если мы создали basic_string для кодировки, в которой каждый логический символ представлен одним физическим символом, то у нас всё в порядке. К примеру, мы создаём basic_string<Utf32> – в UTF-32 каждый логический символ представлен одной физической последовательностью битов длиной 32. С таким типом basic_string всегда сможет вернуть корректный размер строки, т.к. физический размер строки, всегда равен логическому. С другой стороны, мы можем взять UTF-8, где каждый логический символ, может быть представлен несколькими физическим символами(для UTF-8 это байты). Таким образом, если мы имеем basic_string<Utf8>, которая содержит не только ASCII(которая представлена одним байтом в UTF-8), то мы получим размер basic_string отличающийся от реального количества логических символов. Таким образом, basic_string не может быть использован как самостоятельный класс строки, когда разговор идёт о много-байтовой кодировке – в этом случае basic_string вырождается в простое хранилище символов. Подводя черту, можно сформулировать basic_string как хранилище для физического представления символов, которое работает как строка лишь в том случае, когда логический и физический размер символов совпадают.

Псевдонимы

Многие, возможно, никогда и не видели, basic_string<…>, зато вряд ли найдётся С++-программист, который не использовал бы std::string. Но string, есть ни что иное как псевдоним basic_string, для символов размером в один байт(char):

namespace std
{
    ...
    using string = basic_string<char, char_traits<char>, allocator<char>>
    ...
}

Кроме string, есть и несколько других псевдонимов:

namespace std
{
    ...
    using wstring = basic_string<wchar_t, char_traits<wchar_t>,
        allocator<wchar_t>>
    using u16string = basic_string<char16_t, char_traits<char16_t>,
         allocator<char16_t>>
    using u32string = basic_string<char32_t, char_traits<char32_t>, 
        allocator<char32_t>>
    ...
}

Но кроме того, что они представляют собой строки с физическим размером символа отличным от string, они не предоставляют никакого отличного функционала. Таким образом мы будем рассматривать только псевдоним string, подразумевая, что в любом примере его можно заменить на любой другой. Кроме того, чтобы упростить понимание, я буду использовать string вместо basic_string, на протяжении всего цикла статей.

Как устроена строка?

Рассмотрев что из-себя представляет строка в С++, давайте рассмотрим как она может быть реализована. Конечно, реализация не диктуется стандартом, но так сложилось, что реализации более-менее схожи в различных реализациях стандартной библиотеки. Итак, в простейшем случае класс string может быть представлен следующим образом:

simplest_string

Как и следовало ожидать, у нас есть указатель на буфер расположенный в памяти(куче). Но зачем нам 2 поля, отвечающих за размер? Дело в том, что размер выделенного буфера под строку и длина непосредственно строки могут различаться, именно поэтому мы должны хранить как размер самой строки, так и размер буфера. В общем случае, мы могли бы иметь объект string состоящий только из одного указателя, условившись всегда хранить нуль-символ(какой-бы он ни был для того или иного типа символа) в конце строки, а также условившись, что размер буфера всегда равен размеру строки. Это, безусловно, сделало бы наш объект более лёгким, но каждый раз, когда нам нужно было бы узнать размер строки он бы вычислялся по-новой. Т.к. получение размера строки операция весьма популярная, то подобная “оптимизация” вряд ли будет нам на руку.

Если с очевидностью хранения размера строки, всё более-менее понятно, то хранение размера буфера может вызывать вопросы. Возможность иметь буфер больше, чем размер текущей строки позволяет оптимизировать расширение строки. Не стоит забывать, что строки в С++ это контейнеры, в которые можно “докладывать” новую информацию. В частности, по отношению к строке, мы можем добавить новые символы к существующей строке или приклеить одну строку к другой. И если мы всегда имеем размер буфера равный размеру строки, то мы будем вынуждены заново выделять память и перемещать символы на каждой операции изменения размера строки. Вместо этого, практически все реализации striing имеют более умную систему, при которой буфер всегда выделяется больше, чем строка, которую нужно хранить. И в том случае, когда даже эти излишки уже истощены и новое выделение требуется, новый буфер будет опять больше, чем нужно для присоединения другой строки. Таким образом, хранение размера буфера, хоть и увеличивает размер строки, но позволяет сократить число выделений памяти и переноса символов.

Конечно, хранение этого поля и больший буфер не актуальны для константных строк. Но, к сожаление, C++ не разделяет строки на константные и нет.

Хотя предыдущая схема членов string имеет право на жизнь, если рассматривать современную реализацию string, то она, скорее всего, будет больше похожа на следующую схему:

sso_string

На картинке вы можете видеть, что указатель утопает в неком массиве. Таким образом я изобразил объединение(union), в котором хранится указатель и массив, где размер массива превышает размер указателя(это не обязательно так, но скорее всего так и будет). Зачем это нужно, зачем размер объекта string ещё больше увеличили? Всё дело в том, что согласно статистике(я её не видел, но у меня нет причин не верить) большинство строк в программах довольно малого размера и именно поэтому, разработчики библиотеки используют это трюк с объединением. Если строка может целиком поместиться в массив, то никакого дополнительного буфера не выделяется, а строка хранится в самом объекте string:

sso_dominates

С другой стороны, если длина строки превышает некое заданное число, тогда массив отходит на второй план, в куче выделяется буфер и указатель становится связующим звеном объекта string с буфером. При этом, к сожалению, размер объекта string не уменьшается ни на йоту:

no_sso

Зачем нужна подобная оптимизация? Причина проста, точнее их две:

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

Это может показаться мелочью, но, я полагаю, при большом количестве небольших строк прирост может быть значительным. Но нет смысла гадать, когда можно измерить!

Для измерений я использовал следующий код и MSVC 2013 Update 3:

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <chrono>
#include <iomanip>

int main()
{
    std::string abcPart(15, 'a');
    std::iota(abcPart.begin(), abcPart.end(), 'a');
    std::vector<std::string> shortStrs;
    std::vector<std::string> midStrs;
    std::vector<std::string> longStrs;
    for(size_t i = 0; i < 10000000; ++i)
    {
        shortStrs.push_back(abcPart);
        midStrs.push_back(abcPart + "n");
        longStrs.push_back(abcPart + "nn");
        std::next_permutation(abcPart.begin(), abcPart.end());
    }
    auto start = std::chrono::high_resolution_clock::now();
    std::sort(shortStrs.begin(), shortStrs.end());
    auto shortStrElapsed = (std::chrono::high_resolution_clock::now() - start).count();
    start = std::chrono::high_resolution_clock::now();
    std::sort(midStrs.begin(), midStrs.end());
    auto midStrElapsed = (std::chrono::high_resolution_clock::now() - start).count();
    start = std::chrono::high_resolution_clock::now();
    std::sort(longStrs.begin(), longStrs.end());
    auto longStrElapsed = (std::chrono::high_resolution_clock::now() - start).count();
    std::cout << "Short strings time elapsed: " << shortStrElapsed << "\n";
    std::cout << "Middle strings time elapsed: " << midStrElapsed << "\n";
    std::cout << "Long strings time elapsed: " << longStrElapsed << "\n";
    float shortToMid = static_cast<float>(midStrElapsed)/shortStrElapsed;
    float midToLong = static_cast<float>(longStrElapsed)/midStrElapsed;
    std::cout.precision(2);
    std::cout << std::fixed;
    std::cout << "Short strings are " << shortToMid << "x faster than middle\n";
    std::cout << "Middle strings are " << midToLong << "x faster than long\n";

    return 0;
}

В коде используются знания о том, что MSVC использует 16(15 символов + нуль символ) в качестве ограничения на длину строк, которые подпадают под понятие “короткая”. Запустив этот код несколько раз я получил следующие результат: сортировка коротких строк в 1.7 раза быстрее, чем сортировка “обычных” строк. Это не сильно показательно и, в идеале, тестов нужно было бы провести больше, но я получил то, что хотел – подобная оптимизация оправдывает себя.

Если взять полные результаты, то я получил увеличение производительности в 1.76 раза между первым и вторым случаями и никакой разницы(в пределах погрешности) между вторым и третьим случаями.

Выигрыш, в целом, ясен, а насколько увеличивается размер объекта string? В MSVC 2013 Update 3, с целевой компиляцией в 64 бита, размер string равен 32-м байтам. Исходя из полей string можно заметить, что оптимизация раздувает каждый объект на 8 байтов или на на 25%. Критично ли это? Не знаю, всё зависит от ситуации. Но лучше знать об этом. Правда даже зная об этом, вы ничего не можете с этим поделать – MSVC не позволяет отключить эту оптимизацию. Так что если размер объектов стал для вас узким местом, то единственный выход это использовать другую реализацию(либо другая библиотека, либо велосипед). Но не забудьте для начала всё измерить! В общем же случае, на мой взгляд, данная оптимизация оправдана.

Сравниваем строки

Если вы заглядывали в предыдущий код, то могли видеть, что в коде используется сортировка. А это значит, что у строки определён оператор <(т.к. std::sort по умолчанию сортирует с помощью std::less). Но как происходит сравнение строк? Происходит оно согласно специальному, лексикографическому порядку и это регламентировано стандартом. Лексикографический порядок определяется следующим образом: если две строки имеют одинаковый размер и они посимвольно равны, значит ни одна из них не меньше другой лексикографически. Если одна строка является префиксом другой, тогда она лексикографически меньше другой. В противном случае результат определяется путём сравнением первого символа, который различен в строках.

Пример:

std::string obscene{"obscene"};
std::string obscenity{"obscenity"};
assert(obscene < obscenity);
assert(!(obscene < obscene) && !(obscene > obscene));
assert(!(obscenity < obscene));

Как вы можете видеть, “obscene и “obscenity” имеют общий префикс “obscen”, но после этого префикса они расходятся и ‘e’ идёт в алфавите раньше ‘i’(имеет меньший ASCII код), следовательно строка “obscene“ считается меньше строки “obscenity”.

Ещё пример:

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

int main()
{
    std::vector<std::string> dictionary = {"obscene",
        "obscenity",
        "alphabet",
        "row",
        "column", 
        "rowboat"};
    std::sort(dictionary.begin(), dictionary.end());
    std::cout << "Sorted by < operator: \n";
    for(auto str : dictionary)
        std::cout << str << "\n";
    return 0;
}

Вывод:

Sorted by < operator:
alphabet
column
obscene
obscenity
row
rowboat

Ищем в строке

Одной из самых востребованных операций над строками является операция поиска подстроки. Так как строка в C++ является контейнером, и имеет соответствующий интерфейс, то для поиска в строке, можно использовать стандартные алгоритмы C++:

  • std::find, std::find_if, std::find_if_not – различные вариации поиска символа в строке.
  • std::adjacent_find – поиск двух одинаковых, смежных символа.
  • std::search – поиск первого вхождения подстроки в строку.
  • std::find_end - поиск последнего вхождения подстроки в строку
  • std::find_first_of – поиск одного из заданных символов в строке
  • std::search_n – поиск n одинаковых символов подряд.
  • std::mismatch – ищет несовпадение в двух строках

Кроме функций из стандартной библиотеки, string, также, содержит и свой набор методов:

  • std::string::find, std::string::rfind – поиск символа, или под-строки в строке. Первая версия для поиска первого вхождения, а вторая для поиска последнего вхождения
  • std::string::find_first_of – поиск первого вхождения одного из заданных символов
  • std::string::find_last_of – поиск последнего вхождения одного из заданных символов
  • std::string::find_first_not_of – поиск первого символа, который не представлен в заданном списке
  • std::string::find_last_not_of – поиск последнего символа, который не представлен в заданном списке

Как вы можете видеть, методы string фактически повторяют те, что уже есть в стандартной библиотеке. Таким образом мы могли бы обойтись и без них. С другой стороны, иногда методы string более удобны, т.к. сделаны специально для работы со строками. Кроме того, в отличии от обобщённых алгоритмов, методы string возвращают численную позицию символа в строке, где для не найденного символа(эквивалент end() итератора) существует специальная константа: std::string::npos.

Рассмотрим примеры применения вышеназванных функций:

Для работы примеров нам понадобятся следующие заголовки:

#include <iostream>
#include <string>
#include <algorithm>
#include <cassert>

Также, в большинстве примеров будут использованы одни и те же объекты, поэтому я приведу их определение лишь один раз:

std::string first{"Long Sleeve the Kin"};
std::string second{"ABBA BABBAB"};
decltype((first.cbegin()) iter;
size_t position = 0;

Начнём наши примеры, с рассмотрения поиска символа в подстроке:

iter = std::find(first.cbegin(), first.cend(), 'n');
position = std::distance(first.cbegin(), iter);
std::cout << "First 'n' position is: "<< position << "\n";
assert(position == first.find('n'));

Вывод:

First 'n' position is: 2

L

o

n

g

 

S

l

e

e

v

e

 

t

h

e

 

K

i

n

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

Как вы можете видеть в примере выше, мы использовали как std::find, так и std::string::find и их результат, безусловно, идентичен. Кроме того, запись вызова обобщённого алгоритма уступает специализированному в лаконичности.

Теперь рассмотрим поиск с условием:

iter = std::find_if(first.cbegin(), first.cend(), [](char symbol){return symbol > 'p'; });
position = std::distance(first.cbegin(), iter);
std::cout << "First greater than 'p' symbol's position is: "<< position << "\n";
iter = std::find_if_not(first.cbegin(), first.cend(),
    [](char symbol){return symbol > 'p'; });
position = std::distance(first.cbegin(), iter);
std::cout << "First lesser or equal to 'p' symbol's position is: "<< position << "\n";

Вывод:

First greater than 'p' symbol's position is: 9
First lesser or equal to 'p' symbol's position is: 0

L

o

n

g

 

S

l

e

e

v

e

 

t

h

e

 

K

i

n

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

В примере выше мы использовали одну и ту же лямбда-функция для поиска разных символов, в первом случае мы искали первый символ, чей ASCII код будет больше чем ‘p‘. Во втором случае мы искали первый символ с кодом меньше. Подобный поиск можно выполнить только с применением обобщённых алгоритмов, т.к. сам класс string не содержит ничего подобного. Это, в целом, довольно легко объяснить – условный поиск по строке мне видится несколько надуманным. Не вижу реального применения такому.

Следующим рассмотрим поиск одинаковых, смежных символов:

iter = std::adjacent_find(first.cbegin(), first.cend());
position = std::distance(first.cbegin(), iter);
std::cout << "Position of the first symbol in an adjacent pair is: "<< position << "\n";

Вывод:

Position of the first symbol in an adjacent pair is: 7

L

o

n

g

 

S

l

e

e

v

e

 

t

h

e

 

K

i

n

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

Подобной функции в самом классе string тоже нет.

Теперь перейдём к более приземлённой и часто необходимой операции – поиск подстроки в строке:

std::string eve{"eve"};
iter = std::search(first.cbegin(), first.cend(), eve.cbegin(), eve.cend());
position = std::distance(first.cbegin(), iter);
std::cout << R"(Position of the "eve" substring is: )"<< position << "\n";
assert(position == first.find("eve"));

Вывод:

Position of the "eve" substring is: 8

L

o

n

g

 

S

l

e

e

v

e

 

t

h

e

 

K

i

n

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

Как вы можете видеть из примера, вызов обобщенной функции search несколько перегружен. Кроме того, мы не можем просто передать строку в качестве параметра функции – нам необходимо создавать строку отдельно и передавать искомую подстроку через итераторы; не самый удобный способ, согласитесь. А всё из-за того, что алгоритм search создан для последовательностей, а в общем случае последовательность, конечно же, будет представлена итераторами. С другой стороны, у класса string есть собственный метод для поиска подстроки – string::find. Мы уже видели его ранее, когда искали символ. Как можно заметить использование string::find гораздо удобнее – нам не надо думать об итераторах, мы просто передаём ту строку, что нам надо найти. Более того, использование string::find может быть более эффективно за счёт того, что string::find имеет перегруженную версию, которая принимает указатель на литерал, что позволяет не создавать лишний string.

Теперь поищем последнее вхождение заданной подстроки. Конечно, мы могли бы использовать search + std::reverse_iterator, но т.к. есть отдельная функция для этого – грех ей не воспользоваться.

std::string bb{"BB"};
iter = std::search(second.cbegin(), second.cend(), bb.cbegin(), bb.cend());
position = std::distance(second.cbegin(), iter);
std::cout << R"(Position of the first "BB" substring is: )"<< position << "\n";
assert(position == second.find("BB"));
iter = std::find_end(second.cbegin(), second.cend(), bb.cbegin(), bb.cend());
position = std::distance(second.cbegin(), iter);
std::cout << R"(Position of the last "BB" substring is: )"<< position << "\n";
assert(position == second.rfind("BB")););

Вывод:

Position of the first "BB" substring is: 1
Position of the last "BB" substring is: 7

A

B

B

A

 

B

A

B

B

A

B

0

1

2

3

4

5

6

7

8

9

10

Первоначально мы нашли первую позицию BB, чтобы лучше увидеть разницу – функции действительно нашли разные позиции. Кроме того, как вы можете видеть мы использовали string::rfind, для получения того же самого результата, но, как и раньше, в гораздо более лаконичной форме.

Интересно наблюдать, насколько имена алгоритмов C++ не соответствуют друг другу – то search, то find. То first, то вообще без уточнения. То last, то end, то просто префикс r. И это в языке, который так жёстко рецензируется перед публикацией! Конечно же этот момент весьма неприятен, т.к. не добавляет простоты в использовании стандартной библиотеки.

Далее переходим к поиску позиции первого символа, который входит(или не входит) в заданное множество символов:

std::string symbols{"g K"};
iter = std::find_first_of(first.cbegin(), first.cend(), symbols.cbegin(), symbols.cend());
position = std::distance(first.cbegin(), iter);
std::cout << R"(Position of the first symbol from "g K" set is: )"<< position << "\n";
assert(position == first.find_first_of(symbols));
position = first.find_first_not_of("gnolL");
std::cout << R"(Position of the first symbol different from "gnolL" is: )" 
    << position << "\n";

Вывод:

Position of the first symbol from "g K" set is: 3
Position of the first symbol different from "gnolL" is: 4

L

o

n

g

 

S

l

e

e

v

e

 

t

h

e

 

K

i

n

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

Как и ранее, специализированная версия поиска символа более лаконичная. Более того, тогда как в string есть версия, которая позволяет найти первый отличный от множества символ, обобщённого алгоритма для этого случая нет. Конечно, вы всегда можете использовать std::find_first_of передав туда предикат, но это сделает его запись ещё более громоздкой.

Найдя первую позиция, найдём и последнюю:

iter = std::find_first_of(first.crbegin(), first.crend(), symbols.cbegin(),
    symbols.cend()).base();
position = std::distance(first.cbegin(), iter) - 1;
std::cout << R"(Position of the last symbol from "g K" set is: )"<< position << "\n";
assert(position == first.find_last_of(symbols));
position = first.find_last_not_of("niK ");
std::cout << R"(Position of the last symbol different from "niK " is: )" 
    << position << "\n";

Вывод:

Position of the last symbol from "g K" set is: 16
Position of the last symbol different from "niK " is: 14

L

o

n

g

 

S

l

e

e

v

e

 

t

h

e

 

K

i

n

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

В отличии от string, обобщённого алгоритма для поиска последнего символа из множества не существует, поэтому нам пришлось использовать обратные итераторы. Как и в предыдущем примере, если бы мы захотели использовать обобщённый алгоритм для поиска последней позиции символа отличного от символов множества, нам бы пришлось добавить предикат.

Теперь найдём последовательность заданной длины, состоящую из одинаковых символов.

iter = std::search_n(first.cbegin(), first.cend(), 2, 'e');
position = std::distance(first.cbegin(), iter);
std::cout << "Position of the first symbol in sequence of 2 'e' is: " << position << "\n";
assert(position == first.find(std::string(2, 'e')));

Вывод:

Position of the first symbol in sequence of 2 'e' is: 7

L

o

n

g

 

S

l

e

e

v

e

 

t

h

e

 

K

i

n

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

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

Последним рассмотрим пример поиска расхождения между двумя строками:

std::string trueStatement{"ABBA is the most famous Sweden band."};
std::string falseStatement{"ABBA is the most famous American band."};
auto ret = std::mismatch(trueStatement.begin(), trueStatement.end(),
    falseStatement.begin());
assert(ret.first != trueStatement.end());
assert(ret.second != falseStatement.end());
size_t posInFirst = std::distance(trueStatement.begin(), ret.first);
size_t posInSecond = std::distance(falseStatement.begin(), ret.second);
assert(posInFirst == posInSecond);
std::cout << "Position of the first symbol in mismatch is: "<< posInFirst << "\n";

Вывод:

Position of the first symbol in mismatch is: 24

Так как мы используем строки одинаковый длины, которые имеют одинаковое начало, то и позиция где они расходятся будет идентичной. Поиск расхождения двух строк может быть осуществлён только с помощью обобщённого алгоритма, так как метода для такой операции в классе string нет.

Исходя из вышеописанных примеров и их скромного анализа, можно составить следующую таблицу соответствия методов string, обобщённым алгоритмам:

Стандартные алгоритмы

Методы string

find

find

find_if

X

find_if_not

X

adjacent_find

X

search

find

find_end

rfind

find_first_of

find_first_of

search_n

find

mismatch

X

Хотя может показаться, что обобщённые алгоритмы покрывают гораздо больше функционала, на мой взгляд, это совершенно не критично. И единственным значимым алгоритмом, который отсутствует в string является mismatch.

Расчленяем и изменяем строку

Хотя различные операции поиска весьма важны при работе со строками, они, всё же, редко применяются в изоляции. К примеру, когда мы ищем позиции некоторого символа, или строки в другой строке, следующим шагом, зачастую, является использование найденной позиции для выделения части строки в отдельную. Для этих целей в классе string есть целых 2 операции:

  • string::copy – выделение под-строки в стиле C – копирует под-строку в буфер.
  • string::substr – выделение под-строки в стиле C++ – возвращает под-строку в виде объекта string.
#include <iostream>
#include <string>

int main()
{
    std::string chemicals{"Argentum Mercury Ferrum"};
    char ferrum[7]{};
    auto mercury = chemicals.substr(chemicals.find('M'), 7);
    chemicals.copy(ferrum, 6, chemicals.find('F'));
    std::cout << "C++ string: " << mercury << "\n";
    std::cout << "C string: " << ferrum << "\n";
    return 0;
}

Вывод:

C++ string: Mercury
C string: Ferrum

Заметьте, что порядок аргументов {позиция, число символов}, в copy и substr разный. Ещё один момент, где надо быть начеку. Правда это немного смягчается тем фактом, что copy в современном коде использоваться вообще не должен – зачем? copy это пережиток прошлого, и, скорее всего, существует как мост к старым C-программам – избегайте использования этого метода.

Ещё одна операция, которая довольно часто встречается при работе со строками это операция замены. Для этих целей в string существует метод replace. Но, к сожалению, он крайне не самостоятелен и, следовательно, крайне не удобен. Вместо того, чтобы иметь сигнатуру подобную (что_заменить, на_что_заменить) этот метод представлен целым букетом сигнатур, где что_заменить представлено либо итераторами, либо позициями, но не строкой! Поэтому, вместо того, чтобы написать:

std::string chemicals{"Argentum Mercury Ferrum"};
chemicals.replace("Argentum ", "");
chemicals.replace(" Ferrum", ", Freddy");

мы вынуждены писать следующий код:

#include <iostream>
#include <string>

int main()
{
    std::string chemicals{"Argentum Mercury Ferrum"};
    auto mPos = chemicals.find('M');
    chemicals.replace(chemicals.begin(), chemicals.begin() + mPos, "");
    auto fPos = chemicals.find('F');
    chemicals.replace(chemicals.begin() + fPos - 1, chemicals.end(), ", Freddie");
    std::cout << "New string: " << chemicals << "\n";
    return 0;
}

Вывод:

New string: Mercury, Freddie

Конечно, мы могли бы также уложиться в две строчки, но они стали бы ещё длиннее и непонятнее. Кроме того, даже те строки с replace, что присутствуют сейчас в коде, заставляют остановиться и задуматься, тогда как “идеальный” синтаксис поглощается без остановок. Более того, с помощью replace мы можем заменить только одно вхождение некой строки(символа), ни о каком “заменить всё”, без явного цикла, и речи быть не может.  На мой взгляд, функционал замены, представленный в классе string является огромным упущение со стороны комитета.

Другой операцией, которая также встречается очень часто, является соединение(конкатенация) строк. Для этого в классе string существует целый букет методов:

  • operator+= – добавляет строку(символ) к концу строки.
  • operator+ – соединяет две строки, возвращая третью
  • append – добавляет строку(символ) к концу строки. Метод похож на operator+=, но даёт чуть больше свободы
  • push_back – добавляет символ в конец строки.
  • insert – вставляет строку(символ) в произвольную позицию в строке.

Все вышеперечисленные методы, которые работают со строкой, могут добавлять как C-строки, так и C++-строки. Возможность соединения string с C-строкой позволяет присоединять литералы, без создания временных объектов класса string.

Рассмотрим пример в котором, в частности, рассмотрим и то как выполняется оптимизация описанная ранее. Условимся, что наша реализация класса string использует оптимизацию для коротких строк, а также выделяет буфер размера больше, чем требуется для содержания текущей строки.

std::string helloWorld{"Hello"};
char exclamation{'!'};
helloWorld += " World";
helloWorld.push_back(exclamation);

HelloPWorld

Как вы можете видеть, все три наших слияния прошли довольно легко – символы из приклеиваемых строк просто были скопированы внутрь строки. Но что если бы мы добавили ещё одну строку:

helloWorld += " Wow!";

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

  1. Рассчитать размер минимального буфера, который необходим для хранения новой строки.
  2. [Оптимизация] Добавить к этому размеру некое число, чтобы уменьшить количество перераспределений памяти в дальнейшем.
  3. Выделить буфер необходимого размера в куче.
  4. Скопировать все данные из внутреннего буфера в новый, выделенный на куче, буфер.
  5. Поместить указатель на новый буфер в объединение, затерев часть данных, что мы там хранили. Эти данные нам больше не нужны.
  6. Скопировать символы из строки “ Wow!” в наш новый буфер.

Как вы видите, вместо одного шага(шестого в этом списке) нам необходимо выполнить шесть(!). Об этом стоит помнить, если вы довольно интенсивно используете слияние строк.

Еще интереснее ситуация с operator+, к примеру:

std::string helloWorld{"Hello"};
helloWorld = helloWorld + " World" + "!";

Вот что происходит в этом коде:

  1. helloWorld + “ World” – результатом выражения будет временный объект string, назовём его tempStr
  2. tempStr + “!” – результатом выражения будет временный объект string, назовём его tempStr2
  3. helloWorld = tempStr2 – поместим результирующую строку в наш объект helloWorld.

Так вот, до C++11 tempStr и tempStr2 были разными строками, которые создавались в теле operator+, а потом удалялись. Слово “поместим”, в 3-м шаге можно было бы заменить на “скопируем” для C++ кода, предшествующего новому стандарту. Таким образом для такого простого случая мы имели: создание 2-х объектов string и одно копирование.

Сейчас же ситуация изменилась в лучшую сторону,- благодаря семантике перемещения tempStr и tempStr2 будут представлены одной и той же строкой, а слово “поместим” из шага 3, мы можем заменить на “переместим”, что будет означать просто перемещение указателя на буфер временной строки в helloWorld. Выигрыш благодаря новому стандарту может быть весьма ощутим, т.к. в идеальной ситуации нам нужен только один буфер на сколь угодно длинное выражение содержащие соединение строк. Конечно, мир не идеален и в силу того, что размер буфера временной строки может быть в любой момент превышен, то и сохранить один буфер на длинных выражениях будет сложнее. Тут уже на ведущие роли выходит стратегия выделения памяти для буфера – от этого зависит как часто придётся перераспределять память.

Конвертируем строку

Еще одной весьма популярной операцией, при работе со строками, является преобразование строки в число и числа в строку. До C++11 в стандартной библиотеке не было никаких средств для совершения подобных преобразований, которые бы работали с объектами класса string. С появлением нового стандарта эта ситуация изменилась и мы получили следующие функции для преобразования строки в число:

  • std::stoi, std::stol, std::stoll – строка в знаковое целое
  • std::stoul, std::stoull – строка в беззнаковое целое
  • std::stof, std::stod, std::stold – строка в вещественное число

И одну функцию для преобразования числа в строку: std::to_string. Почему в одну сторону мы имеем много функций, тогда как обратное преобразование обходится одной? Ответ прост – в C++ перегрузка разрешена только по аргументам функции, но не по её возвращаемому значение. Это позволяет иметь много перегруженных функций с одним именем – to_string. Почему нельзя было сделать шаблонную функцию from_string, с явным указанием возвращаемого значения, для меня загадка. На мой взгляд, это было бы удобнее, чем иметь кучу функций с разными именами.

Пример:

#include <iostream>
#include <string>

int main()
{
    std::string one{"1"};
    std::string fifteen{"F"};
    std::string fourteen{"1110"};
    double real = 12.567890;
    std::cout << "One to integer: " << std::stoi(one) << "\n";
    std::cout << "Fifteen to integer: " << std::stol(fifteen, nullptr, 16) << "\n";
    std::cout << "Fourteen to integer: " << std::stoull(fourteen, nullptr, 2) << "\n";
    std::cout << "Real to string: " << std::to_string(real) << "\n";
    return 0;
}

Вывод:

One to integer: 1
Fifteen to integer: 15
Fourteen to integer: 14
Real to string: 12.567890

До того, как в стандарте появились новые функция для преобразований между строкой и числом весьма популярной была функция из boostlexical_cast. Она легка в использовании и, как утверждается, быстрее чем любой другой стандартный подход. Но, на мой взгляд, с появлением новых функций, lexical_cast более не представляет интереса, так как новые функции не менее удобны. Более того, в отличии от lexical_cast, новые функции могут учитывать систему счисления преобразовываемого числа, в чём мы убедились ранее. А что насчёт производительности? В тестах для lexical_cast нет колонки с новыми функциями, а значит есть смысл проверить самостоятельно. Возьмём следующий код:

#include <iostream>
#include <string>
#include <vector>
#include <chrono>
#include <boost/lexical_cast.hpp>

int main()
{
    std::vector<std::string> strings;
    for(size_t i = 0; i < 1000000; ++i)
        strings.push_back(std::to_string(i));

    size_t sum = 0;
    auto start = std::chrono::high_resolution_clock::now();
    for(auto& str : strings)
        sum += std::stoul(str);
    auto stdElapsed = (std::chrono::high_resolution_clock::now() - start).count();
    start = std::chrono::high_resolution_clock::now();
    for(auto& str : strings)
        sum += boost::lexical_cast<unsigned long>(str);
    auto boostElapsed = (std::chrono::high_resolution_clock::now() - start).count();
    
    std::cout << "Standard way took: " << stdElapsed << "\n";
    std::cout << "Boost way took: " << boostElapsed << "\n";
    float ratio = std::max<float>(stdElapsed, boostElapsed)/
        std::min<float>(stdElapsed, boostElapsed);
    std::string relation = stdElapsed < boostElapsed ?
        std::string("faster") : std::string("slower");
    std::cout << "Standard way is " << ratio << " " << relation << "!\n";
    return 0;
}

Его вывод:

Standard way took: 450124
Boost way took: 1070272
Standard way is 2.37773 faster!

В среднем я получил двукратное превосходство стандартного подхода(MSVC 2013 Update3). На онлайн компиляторах я получил ещё большее превосходство. Конечно, мой тест далеко не полный и не отражает всевозможных конвертаций(в отличии от того, что представлен на сайте boost), но, как минимум, это показывает, что стандартный подход не уступает подходу с использованием boost, а, возможно, его даже превосходит.