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

 class Text_iterator { // отслеживает позицию символа в строке
  list<Line>::iterator ln;
  Line::iterator pos;
 public:
  // устанавливает итератор на позицию pp в ll-й строке
  Text_iterator(list<Line>::iterator ll, Line::iterator pp)
  :ln(ll), pos(pp) { }

  char& operator* { return *pos; }
  Text_iterator& operator++;

  bool operator==(const Text_iterator& other) const
  { return ln==other.ln && pos==other.pos; }

  bool operator!=(const Text_iterator& other) const
  { return !(*this==other); }
 };

 Text_iterator& Text_iterator::operator++
 {
  if (pos==(*ln).end) {
++ln; // переход на новую строку
  pos = (*ln).begin;
  }
  ++pos; // переход на новый символ
  return *this;
 }

Для того чтобы класс Text_iterator стал полезным, необходимо снабдить класс Document традиционными функциями begin и end.

 struct Document {
  list<Line> line;
  Text_iterator begin // первый символ первой строки
  { return Text_iterator(line.begin,
  (*line.begin).begin); }
  Text_iterator end // за последним символом последней строки
  { return(line.end, (*line.end).end));}
 };

Мы использовали любопытную конструкцию (*line.begin).begin, потому что хотим начинать перемещение итератора с позиции, на которую ссылается итератор line.begin; в качестве альтернативы можно было бы использовать функцию line.begin–>begin, так как стандартные итераторы поддерживают операцию –>.

Теперь можем перемещаться по символам документа.

 void print(Document& d)
 {
  for (Text_iterator p = d.begin;
  p!=d.end; ++p) cout << *p;
 }
 print(my_doc);

Представление документа в виде последовательности символов полезно по многим причинам, но обычно мы перемещаемся по документам, просматривая более специфичную информацию, чем символ. Например, рассмотрим фрагмент кода, удаляющий строку n.

 void erase_line(Document& d, int n)
 {
  if (n<0 || d.line.size<=n) return; // игнорируем строки,
  // находящиеся
  // за пределами диапазона
  d.line.erase(advance(d.line.begin, n));
 }

Вызов advance(p,n) перемещает итератор p на n элементов вперед; функция advance — это стандартная функция, но мы можем сами написать подобный код.

 template<class Iter> Iter advance(Iter p, int n)
 {
while (n>0) { ++p; ––n; } // перемещение вперед
  return p;
 }

Обратите внимание на то, что функцию advance можно использовать для имитации индексирования. Фактически для объекта класса vector с именем v выражение *advance(v.begin,n) почти эквивалентно конструкции v[n]. Здесь слово “почти” означает, что функция advance старательно проходит по каждому из первых n–1 элементов шаг за шагом, в то время как операция индексирования сразу обращается к n– му элементу. Для класса list мы вынуждены использовать этот неэффективный метод. Это цена, которую мы должны заплатить за гибкость списка.

Если итератор может перемещаться вперед и назад, например в классе list, то отрицательный аргумент стандартной библиотечной функции advance означает перемещение назад. Если итератор допускает индексирование, например в классе vector, стандартная библиотечная функция advance сразу установит его на правильный элемент и не будет медленно перемещаться по всем элементам с помощью оператора ++. Очевидно, что стандартная функция advance немного “умнее” нашей. Это стоит отметить: как правило, стандартные средства создаются более тщательно, и на них затрачивается больше времени, чем мы могли бы затратить на самостоятельную разработку, поэтому мы отдаем предпочтение стандартным инструментам, а не “кустарным”.

ПОПРОБУЙТЕ

Перепишите нашу функцию 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; // ищем следующий символ