На этом шаге мы рассмотрим некоторые операции поиска.

    Множества и мультимножества оптимизированы для поиска элементов, поэтому в этих контейнерах определены специальные функции поиска (таблица 1). Эти функции представляют собой оптимизированные версии одноименных универсальных алгоритмов. Всегда используйте оптимизированные версии функций для множеств и мультимножеств, обеспечивающие логарифмическую сложность вместо линейной сложности универсальных алгоритмов. Например, поиск в коллекции из 1000 элементов требует в среднем 10 сравнений вместо 500 (смотри 42 шаг).

Таблица 1. Специальные операции поиска в множествах и мультимножествах

Операция	Описание
count(elem)	Возвращает количество элементов со значением elem
find(elem)	Возвращает позицию первого элемента со значением elem (или end())
lower_bound(elem)	Возвращает первую позицию, в которой может быть вставлен элемент elem (первый элемент >= elem)
upper_bound(elem)	Возвращает последнюю позицию, в которой может быть вставлен элемент elem (первый элемент > elem)
equal_range(elem)	Возвращает первую и последнюю позиции, в которых может быть вставлен элемент elem (интервал, в котором элементы == elem)

    Функция find() ищет первый элемент, значение которого передается в аргументе, и возвращает его позицию в виде итератора. Если поиск оказывается безуспешным, функция find() возвращает end().

    Функции lower_bound() и upper_bound() возвращают соответственно первую и последнюю позиции, в которых может быть вставлен элемент с заданным значением. Иначе говоря, lower_bound() возвращает позицию первого элемента, значение которого больше либо равно аргументу, а функция upper_bound() возвращает позицию последнего элемента, значение которого больше аргумента. Функция equal_range() возвращает значения lower_bound() и upper_bound() в виде объекта типа pair (тип pair описан на 56 шаге). Таким образом, функция возвращает интервал элементов, значения которых равны переданному аргументу. Если lower_bound() или первый компонент equal_range() совпадает с upper_bound() или вторым компонентом equal_range(), то в множестве или мультимножестве отсутствуют элементы с заданным значением. Естественно, в множестве интервал equal_range() содержит не более одного элемента.

    Следующий пример демонстрирует применение функций lower_bound(), upper_ bound() и equal_range().

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

#include <vcl.h>
#include <iostream>
#include <iterator>
#include <set>
#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[])
{
  set <int> c;

  c.insert(1);
  c.insert(2);
  c.insert(4);
  c.insert(5);
  c.insert(6);
 
  cout << "lower_bound(3): " << *c.lower_bound(3) << endl;
  cout << "upper_bound(3): " << *c.upper_bound(3) << endl;
  cout << "equal_range(3): " << *c.equal_range(3).first << " "
                             << *c.equal_range(3).second << endl;

  cout << endl;

  cout << "lower_bound(5): " << *c.lower_bound(5) << endl;
  cout << "upper_bound(5): " << *c.upper_bound(5) << endl;
  cout << "equal_range(5): " << *c.equal_range(5).first << " "
                             << *c.equal_range(5).second << endl;

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

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

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

    Если вместо множества использовать мультимножество, результат останется прежним.

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

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