Примеры использования ассоциативных контейнеров. Примеры использования множеств и мультимножеств

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

   
Первый пример показывает, как происходит вставка элементов в множество и их последующий вывод с использованием итератора:

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

#include <vcl.h>
#include <iostream>
#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[])
{
  // Тип коллекции
  typedef std::set<int> IntSet;
  IntSet coll;   // Контейнер для целых чисел
  // Вставка элементов со значениями от 1 до 6:
  // значение 1 вставляется дважды
  coll.insert(3); 
  coll.insert(1); 
  coll.insert(5); 
  coll.insert(4); 
  coll.insert(1); 
  coll.insert(6);
  coll.insert(2);

  cout << ToRus("Элементы множества: ");
  // Вывод содержимого множества
  // - перебор всех элементов.
  IntSet::const_iterator pos;
  for (pos=coll.begin(); pos != coll.end(); ++pos) { 
    std::cout << *pos << ' ';
  }
  std::cout << std::endl;

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

Текст этого примера можно взять здесь.

   
Как обычно, следующая директива подгружает все необходимые определения типов и операций с множествами:

  #include <set>

   
Тип контейнера используется в нескольких местах программы, поэтому для удобства мы определяем для него сокращенное название:

  typedef std::set<int> IntSet;

   
Команда определяет тип IntSet как множество элементов типа int. Этот тип использует стандартный критерий
сортировки, при котором элементы сортируются оператором < (то есть упорядочиваются по возрастанию). Чтобы отсортировать
элементы по убыванию или использовать совершенно иной критерий сортировки, передайте его в качестве второго параметра шаблона.
Например, следующая команда определяет тип множества с сортировкой элементов по убыванию:

  typedef set<int,greater<int> > IntSet;

   Замечания.

  • Функцию greater<> мы рассмотрим позднее.
  • Обратите внимание на пробел между символами >. Последовательность > воспринимается компилятором как оператор
    сдвига, что приводит к синтаксической ошибке.
  •    
    Все ассоциативные контейнеры поддерживают функцию insert(), которая вставляет новый элемент:

      coll.insert(3); 
      coll.insert(1); 
      .   .   .   .
    

       
    Позиция нового элемента определяется автоматически в соответствии с критерием сортировки. Функции последовательных
    контейнеров push_back() или push_front() не поддерживаются ассоциативными контейнерами. В данном случае эти
    функции не имеют смысла, поскольку позиция нового элемента определяется автоматически.

       
    Состояние контейнера после вставки элементов в произвольном порядке (например: 4, 2, 1, 6, 3, 5) иллюстрирует рисунок 1.


    Рис.1. Множество из шести элементов

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

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

      IntSet::const_iterator pos;
      for (pos=coll.begin(); pos != coll.end(); ++pos) { 
        std::cout << *pos << ' ';
      }
    

       
    Так как итератор определяется самим контейнером, он справляется со своей задачей, хотя структура контейнера становится более
    сложной. Например, если итератор ссылается на третий элемент, то оператор ++ переместит его к четвертому (верхнему) элементу.
    После следующего вызова оператора ++ итератор будет ссылаться на пятый (нижний) элемент (рисунок 2).


    Рис.2. Перебор элементов множества с помощью итератора pos

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


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

       
    Чтобы вместо обычного множества использовалось мультимножество, достаточно изменить тип контейнера (заголовочный файл
    остается тем же):

      typedef multiset<int> IntSet;
    

    Мультимножество допускает присутствие дубликатов, поэтому контейнер будет содержать два элемента со значением 1.
    Таким образом, выходные данные программы будут выглядеть так:


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

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



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

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