Программирование. Принципы и практика использования C++ Исправленное издание
вернуться

Страуструп Бьерн
Шрифт:

ПОПРОБУЙТЕ

Перепишите нашу функцию

advance
так, чтобы, получив отрицательный аргумент, она выполняла перемещение назад.

Вероятно, поиск — это самый очевидный вид итерации. Мы ищем отдельные слова (например,

milkshake
или
Gavin
), последовательности букв (например,
secret\nhomestead
— т.е. строка, заканчивающаяся словом
secret
, за которым следует строка, начинающаяся словом
homestead
), регулярные выражения (например,
[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,"secret\nhomestead");

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. Элементы в памяти располагаются последовательно в смежных ячейках. Размер массива фиксируется на этапе компиляции. Операции сравнения (
==
и
!=
) и вывода (
<<
) используют указатель на первый элемент массива, а не на все элементы.