На этом шаге мы познакомимся с особенностями использования интервалов.

    Любой алгоритм работает с одним или несколькими интервалами. Интервал может (хотя и не обязан) содержать все элементы контейнера. Чтобы алгоритм мог обрабатывать подмножество элементов контейнера, при вызове начало и конец интервала передаются в двух разных аргументах (вместо того, чтобы передавать всю коллекцию в одном аргументе).

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

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

  [начало,конец)

    Концепция полуоткрытых интервалов обладает рядом достоинств, тем не менее у нее также есть недостатки. Рассмотрим следующий пример:

//---------------------------------------------------------------------------

#include <vcl.h>
#include <iostream>
#include <list>
#include <algorithm>
#include <conio.h> //необходимо для getch()
#pragma hdrstop

//---------------------------------------------------------------------------

#pragma argsused
using namespace std;
std::string ToRus(const std::string &in)
{
  char *buff = new char [in.length()+1];
  CharToOem(in.c_str(),buff);
  std::string out(buff);
  delete [] buff;
  return out;
}

int main(int argc, char* argv[])
{
  list<int> coll;
  list<int>::iterator pos;

  // Вставка элементов от 20 до 40
  for (int i=20; i<=40; ++i) {
    coll.push_back(i);
  }

  // Поиск позиции элемента со значением, равным 3
  // - такой элемент отсутствует, поэтому pos присваивается coll.end()
  pos = find (coll.begin(), coll.end(),  // Интервал
     3);	// Значение

  // Перестановка элементов от найденного до конца интервала
  // - поскольку итератор pos равен coll.end().
  // перестановка производится в пустом интервале.
  reverse (pos, coll.end());

  // Поиск позиций со значениями 25 и 35
  list<int>::iterator pos25,pos35;
  pos25 = find (coll.begin(), coll.end(), // Интервал
      25); // Значение
  pos35 = find (coll.begin(), coll.end(), // Интервал
      35); // Значение
  // Вывод максимума ло полученному интервалу
  // - обратите внимание: интервал содержит позицию pos25.
  // но позиция pos35 в него не включается.

  cout << ToRus("максимум = ") << *max_element (pos25, pos35) << endl;
  // Включить в интервал последний элемент
  cout << ToRus("максимум = ") << *max_element (pos25, ++pos35) << endl;

  getch();
  return 0;
}
//---------------------------------------------------------------------------

    Результат работы программы выглядит так:

Рис.1. Результат работы приложения

    В этом примере коллекция заполняется целыми числами от 20 до 40. После того как поиск элемента со значением 3 завершается неудачей, find() возвращает конец обработанного интервала - в данном случае coll.end() - и присваивает его переменной pos. Использование возвращаемого значения в качестве начала интервала при вызове reverse() не вызывает проблем, поскольку это приводит к следующему вызову:

  reverse (coll.end(), coll.end());

    Происходит перестановка элементов в пустом интервале, поэтому никакие реальные действия не выполняются.

    Но если алгоритм find() используется для определения первого и последнего элементов в подмножестве, следует помнить, что при определении интервала на основании полученных итераторов последний элемент исключается. Рассмотрим первый вызов max_element():

  max_element (pos25, pos35);

    При этом вызове будет найдено максимальное значение 34 вместо 35:

  максимум = 34

    Чтобы включить в интервал последний найденный элемент, необходимо перевести итератор на одну позицию вперед:

  max_element (pos25, ++pos35);

    На этот раз результат будет правильным:

  максимум = 35

    В этом примере контейнером является список, поэтому для перевода pos35 к следующей позиции был применен оператор ++. Если бы мы использовали итератор произвольного доступа (как в случае вектора или дека), задача также решалась бы с помощью выражения pos35 + 1, поскольку итераторы произвольного доступа поддерживают математические операции.

    Конечно, итераторы pos25 и pos35 можно использовать для поиска в подмножестве элементов. Чтобы поиск производился с включением позиции pos35, следует сместить позицию итератора. Пример:

  // Увеличение pos35 для учета конца интервала при поиске
  ++pos35:
  pos30 = find(pos25, pos35,  // Интервал
    30); // Значение
  if (pos30 == pos35)  {
    cout << "Число 30 не входит в промежуток" << endl;
  } else {
    cout << "Число 30 входит в промежуток" << endl;
  }

    На следующем шаге мы закончим изучение этого вопроса.

Предыдущий шаг Содержание Следующий шаг