На этом шаге мы рассмотрим функцию, вычисляющую расстояние между итераторами.

    Функция distance() вычисляет разность между двумя итераторами:

  #include <iterator>
  Dist distance (InputIterator pos1, InputIterator pos2)

    Возвращает расстояние между итераторами ввода pos1 и pos2. Оба итератора должны ссылаться на элементы одного контейнера. Если итераторы не являются итераторами произвольного доступа, итератор pos2 должен быть доступен от pos1 (то есть должен находиться в той же или в одной из следующих позиций).

    Тип возвращаемого значения Dist определяет тип разности в соответствии с типом итераторов:

  iterator_traits<InputIterator>::difference_type

    При помощи итераторных тегов функция distance() выбирает оптимальную реализацию в соответствии с категорией итератора. Для итераторов произвольного доступа она просто возвращает pos2-pos1; следовательно, для таких итераторов функция distance() имеет постоянную сложность. Для остальных категорий итераторов функция distance() последовательно увеличивает pos1 до достижения pos2, после чего возвращается количество увеличений. В этом случае функция работает с линейной сложностью, и для таких категорий итераторов лучше воздержаться от ее использования. Таким образом, функция distance() обладает низким быстродействием для всех итераторов, кроме итераторов произвольного доступа.

    Ниже приведен пример ее использования.

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

#include <vcl.h>
#include <iostream>
#include <iterator>
#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;
  
  // Вставка элементов от -3 до 9 
  for (int i=-3; i<=9; ++i) {
    coll.push_back(i); 
  }

  list<int>::iterator pos;

  pos = find (coll.begin(), coll.end(),  // Интервал
              5); // Значение

  if (pos != coll.end()) {
    // Вычисление и вывод расстояния от начала коллекции 
    cout << ToRus("Расстояние от начала коллекции до 5: ") << 
           distance(coll.begin(),pos) << endl;
  } else {
      cout << "5 не найдено" << endl;
  }

  getch();
  return 0;
}

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

    Функция find() присваивает итератору pos позицию элемента со значением 5. Функция distance() использует эту позицию для вычисления разности между позицией и началом коллекции. Результат выполнения программы выглядит так:

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

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

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

    В первых версиях STL использовалась другая сигнатура функции distance(). Вместо того чтобы возвращать разность, функция передавала ее в третьем аргументе. Эта версия была крайне неудобной, поскольку не позволяла напрямую вызывать функцию в выражениях. Если у вас устаревшая версия, воспользуйтесь простым обходным решением:

  template <class Iterator>
  inline long distance (Iterator pos1, Iterator pos2)
  {
    long d = 0:
    distance (pos1, pos2, d);
    return d; 
  }

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

    На следующем шаге мы рассмотрим перестановку элементов функцией iter_swap().

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