Интервалы

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

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

   
Такой интерфейс чрезвычайно гибок, но потенциально опасен. Вызывающая сторона должна проследить за тем,
чтобы первый и второй аргументы определяли действительный интервал, то есть итератор мог перейти от начала
к концу интервала в процессе перебора элементов. А это означает, что оба итератора должны принадлежать одному
контейнеру, а начало интервала не должно находиться после его конца. Если это условие не выполняется,
возможны непредсказуемые последствия, включая зацикливание или нарушение защиты памяти.
В этом отношении итераторы так же ненадежны, как обычные указатели. Однако из неопределенности поведения
также следует, что реализации 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;
  }

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



Вы можете оставить комментарий, или Трекбэк с вашего сайта.

Оставить комментарий