Операции над множествами и мультимножествами. Специальные операции поиска

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

   
Множества и мультимножества оптимизированы для поиска элементов, поэтому в этих контейнерах определены специальные функции
поиска (таблица 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. Результат работы приложения

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

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



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

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