Интервалы (окончание)

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

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

   
Предположим, мы не знаем, что элемент со значением 25 предшествует элементу со значением 35. Более того, нельзя
исключать, что одно или оба значения отсутствуют в контейнере. При использовании итератора произвольного доступа
проверка выполняется оператором <:

  if (pos25 < pos35) {
    .   .   .   . // Действителен интервал [pos25.pos35)
  }
  else if (pos35 < pos25) {
    .   .   .   . // Действителен интервал [pos35.pos25)
    else {
      .   .   .   .// Итераторы равны; следовательно, оба итератора 
                  // находятся в позиции end()
    }

   
Без итераторов произвольного доступа не существует простого и быстрого способа определить порядок следования
итераторов. Единственное разумное решение - провести поиск одного итератора в интервале от начала до другого
итератора или от другого итератора до конца. В этом случае алгоритм слегка изменяется: вместо того чтобы искать
оба значения во всем исходном интервале, мы пытаемся определить, какое значение встречается первым. Пример:

  pos25 = find (coll.begin(). coll.end(),   // Интервал
    25);  // Значение
  pos35 = find (coll .begin(). pos25,    // Интервал
    35);  // Значение
  if (pos35 != pos25) {
    // pos35 предшествует pos25: следовательно, 
    // действителен только интервал [pos35,pos25) 
    .   .   .   .
  }
else {
  pos35 = find (pos25, coll.end(),   // Интервал
    35);  // Значение
  if (pos35 != pos25) {
    // pos25 предшествует pos35: следовательно,
    // действителен только интервал [pos25,pos35) 
    .   .   .   .
  }
 else {
    // Итераторы равны: следовательно, оба итератора 
    // находятся в позиции end()
    .   .   .   .
  }

   
В отличие от предыдущей версии поиск значения 35 производится не во всем множестве элементов coll.
Сначала поиск ведется от начала до pos25. Если значение не найдено, поиск производится среди элементов,
находящихся после pos25. В результате мы выясняем, какой итератор встречается раньше и какой интервал
действителен.

   
Эффективность подобной реализации оставляет желать лучшего. Более эффективный способ найти первый элемент
со значением 25 или 35 заключается в том, чтобы поиск выполнялся именно по такому условию. Для этого придется
задействовать некоторые еще не упоминавшиеся возможности STL:

  pos = find_if (coll .begin(), coll.end(),  // Интервал
    compose_f_gx_hx(logical_or<bool>0,     // Критерий 
                  bind2nd(equal_to<int>(),25), 
                  bind2nd(equal_to<int>(),35))); 
  switch (*pos) { 
    case 25: 
      // Первым обнаружен элемент со значением 25
      pos25 = pos;				
      pos35	= find (++pos, coll.end(),  // Интервал
                  35);  // Значение
      .    .    .    .
      break; 
    case 35:
      // Первым обнаружен элемент со значением 35 
      pos35 = pos;
      pos25 = find (++pos,coll.end(),   // Интервал
                  25);  // Значение
      .    .    .    .
      break; 
    default: 
      // Элементы со значениями 25 и 35 не найдены
      .    .    .    .
      break; 
  }

   
В качестве критерия поиска передается специальное выражение для нахождения первого элемента со значением 25
или 35. В этом выражении объединены несколько стандартных объектов функций и вспомогательный объект функции
compose_f_gx_hx.

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



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

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