регулярные выражения (например, [bB]w*ne — т.е. буква B в верхнем или нижнем регистре, за которой следует 0 или больше букв, за которыми следуют буквы ne; см. главу 23) и т.д. Покажем, как решить вторую задачу: найдем строку, используя нашу схему хранения объекта класса Document. Будем использовать простой — не оптимальный — алгоритм.
• Найдем первый символ искомой строки в документе.
• Проверим, совпадают ли эти и следующие символы с символами искомой строки.
• Если совпадают, то задача решена; если нет, будем искать следующее появление первого символа.
Для простоты примем правила представления текстов в библиотеке STL в виде последовательности, определенной парой итераторов. Это позволит нам применить функцию поиска не только ко всему документу, но и к любой его части. Если мы найдем нашу строку в документе, то вернем итератор, установленный на ее первый символ; если не найдем, то вернем итератор, установленный на конец последовательности.
Text_iterator find_txt(Text_iterator first,
Text_iterator last, const string& s)
{
if (s.size()==0) return last; // нельзя искать пустую строку
char first_char = s[0];
while (true) {
Text_iterator p = find(first,last,first_char);
if (p==last || match(p,last,s)) return p;
++first; // ищем следующий символ
}
}
Возврат конца строки в качестве признака неудачного поиска является важным соглашением, принятым в библиотеке STL. Функция match() является тривиальной; она просто сравнивает две последовательности символов. Попробуйте написать ее самостоятельно. Функция find(), используемая для поиска символа в последовательности, вероятно, является простейшим стандартным алгоритмом (раздел 21.2). Мы можем использовать свою функцию find_txt() примерно так:
Text_iterator p =
find_txt(my_doc.begin(), my_doc.end(),"secretnhomestead");
if (p==my_doc.end())
cout << "Не найдена ";
else {
// какие-то действия
}
Наш текстовый процессор и его операции очень просты. Очевидно, что мы хотим создать простой и достаточно эффективный, а не “навороченный” редактор. Однако не следует ошибочно думать, что эффективные вставка, удаление и поиск произвольного символа — тривиальные задачи. Мы выбрали этот пример для того, чтобы продемонстрировать мощь и универсальность концепций последовательности, итератора и контейнера (таких как list и vector) в сочетании с правилами программирования (приемами), принятыми в библиотеке STL, согласно которым возврат итератора, установленного на конец последовательности, является признаком неудачи. Обратите внимание на то, что если бы мы захотели, то могли бы превратить класс Document в контейнер STL, снабдив его итератором Text_iterator. Мы сделали главное для представления объекта класса Document в виде последовательности значений.
20.7. Классы vector, list и string
Почему для хранения строк мы используем класс list, а для символов — класс vector? Точнее, почему для хранения последовательности строк мы используем класс list, а для хранения последовательности символов — класс vector? Более того, почему для хранения строки мы не используем класс string?
Сформулируем немного более общий вариант этого вопроса. Для хранения последовательности символов у нас есть четыре способа.
• char[] (массив символов)
• vector<char>
• string
• list<char>
Какой из этих вариантов выбрать для решения конкретной задачи? Для действительно простой задачи все эти варианты являются взаимозаменяемыми; иначе говоря, у них очень похожие интерфейсы. Например, имея итератор, мы можем перемещаться по элементам с помощью операции ++ и использовать оператор * для доступа к символам. Если посмотреть на примеры кода, связанного с классом Document, то мы действительно можем заменить наш класс vector<char> классом list<char> или string без каких-либо проблем. Такая взаимозаменяемость является фундаментальным преимуществом, потому что она позволяет нам сделать выбор, ориентируясь на эффективность. Но, перед тем как рассматривать вопросы эффективности, мы должны рассмотреть логические возможности этих типов: что такого может делать каждый из них, чего не могут другие?
• Elem[]. Не знает своего размера. Не имеет функций begin(), end() и других контейнерных функций-членов. Не может систематически проверять выход за пределы допустимого диапазона. Может передаваться функциям, написанным на языке C или в стиле языка C. Элементы в памяти располагаются последовательно в смежных ячейках. Размер массива фиксируется на этапе компиляции. Операции сравнения (== и !=) и вывода (<<) используют указатель на первый элемент массива, а не на все элементы.
• vector<Elem>. Может выполнять практически все, включая функции insert() и erase(). Предусматривает индексирование. Операции над списками, такие как insert() и erase(), как правило, связаны с перемещением элементов (что может оказаться неэффективным для крупных элементов и при большом количестве элементов). Может проверять выход за пределы допустимого диапазона. Элементы в памяти располагаются последовательно в смежных ячейках. Объект класса vector может увеличиваться (например, использует функцию push_back()). Элементы вектора хранятся в массиве (непрерывно). Сравнение элементов осуществляется с помощью операторов ==, !=, <, <=, > и >=.
• string. Предусматривает все обычные и полезные операции, а также специфические манипуляции текстами, такие как конкатенация (+ и +=). Элементы хранятся в смежных ячейках памяти. Объект класса string можно увеличивать. Сравнение элементов осуществляется с помощью операторов ==, !=, <, <=, > и >=.
• list<Elem>. Предусматривает все обычные и полезные операции, за исключением индексирования. Операции insert() и delete() можно выполнять без перемещения остальных элементов. Для хранения каждого элемента необходимы два дополнительных слова (для указателей на узлы). Объект класса list можно увеличивать. Сравнение элементов осуществляется с помощью операторов (==, !=, <, <=, > и >=).
Как мы уже видели (см. разделы 17.2 и 20.5), массивы полезны и необходимы для управления памятью на самом нижнем уровне, а также для обеспечения взаимодействия с программами, написанными на языке C (подробнее об этом — в разделах 27.1.2 и 27.5). В отличие от этого, класс vector является более предпочтительным, потому что его легче использовать, к тому же он более гибкий и безопасный.
ПОПРОБУЙТЕ
Что означает этот список отличий в реальном коде? Определите массивы объектов типа char, vector<char>, list<char> и string со значением "Hello", передайте его в
