Контейнеры STL. Множества и мультимножества (общие сведения)

   
На этом шаге мы приведем общие сведения о множествах и мультимножествах.

   
Множества и мультимножества автоматически сортируют свои элементы по некоторому критерию. Они отличаются только тем, что
мультимножества могут содержать дубликаты, а множества - нет (рисунок 1).


Рис.1. Множество и мультимножество

   
Чтобы использовать множество или мультимножество в программе, необходимо включить в нее заголовочный файл <set>:

  #include <set>

   
Типы множества и мультимножества определяются как шаблоны классов в пространстве имен std:

namespace std {
  template <class Т,
            class Compare = less<T>,
            class Allocator = allocator<T> > 
  class set;

  template <class T,
            class Compare = less<T>,
            class Allocator = allocator<T> >
  class multiset;
}

   
Элементы множества или мультимножества относятся к произвольному типу Т, поддерживающему присваивание, копирование
и сравнение по критерию сортировки. Необязательный второй параметр шаблона определяет критерий сортировки. По умолчанию
используется критерий less. Объект функции less сортирует элементы, сравнивая их оператором <.
Необязательный третий параметр шаблона определяет модель памяти. По умолчанию используется модель allocator,
определенная в стандартной библиотеке C++.

   
Критерий сортировки должен определять "строгую квазиупорядоченность" (strict weak ordering). Строгая
квазиупорядоченность определяется тремя свойствами.

  • Асимметричность.
    • Для оператора <: если выражение х<у истинно, то выражение у<х ложно.
    • Для предиката ор(): если выражение ор(х,у) истинно, то выражение ор(у,х) ложно.
  • Транзитивность.
    • Для оператора <: если выражения х<у и y<z истинны, то выражение x<z истинно.
    • Для предиката ор(): если выражения ор(х,у) и op(y,z) истинны, то выражение op(x,z) истинно.
  • Иррефлексивность.
    • Для оператора <: выражение х<х всегда ложно.
    • Для предиката ор(): выражение ор(х,х) всегда ложно.

   
На основании этих свойств критерий сортировки используется также для проверки на равенство, а именно: два элемента равны,
если ни один из них не меньше другого (или если ложны оба выражения ор(х,у) и ор(у,х)).

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



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

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