C++. Сборник рецептов

using namespace std;
int main() {
 set<string> setStr;
 string s = 'Bill';
 setStr.insert(s);
 s = 'Steve';
 setStr.insert(s);
 s = 'Randy';
 setStr.insert(s);
 s = 'Howard';
 setStr.insert(s);
 for (set<string>::const_iterator p = setStr.begin();
  p != setStr.end(); ++p)
  cout << *p << endl;
}

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

Bill
Howard
Randy
Steve

Обсуждение

set (набор) — это ассоциативный контейнер, который предоставляет логарифмическую сложность вставки и поиска и постоянную сложность удаления элементов (если требуется удалить найденный элемент), set — это уникальный ассоциативный контейнер, что означает, что никакие два элемента не могут быть равны, однако если требуется хранить несколько экземпляров одинаковых элементов, используйте multiset, set можно представить как набор в математическом смысле, т.е. коллекцию элементов, в дополнение обеспечивающую поддержание определенного порядка элементов.

Поддерживаются вставка и поиск элементов, но, как и список, набор не позволяет производить произвольный доступ к элементам. Если требуется получить что-то из набора, то можно найти элемент с помощью метода find или перебрать элементы с помощью set<T>::iterator или set<T>::const_iterator. Объявление набора имеет знакомый вид.

set<typename Key,                       // Тип элемента
 typename LessThanFun = std::less<Key>, // Функция/Функтор
                                        // используемый для сортировки
 typename Alloc = std::allocator<Key> > // Распределитель памяти

Указывать Key требуется всегда, иногда требуется предоставить собственную LessThanFun, а указывать собственный распределитель требуется очень редко (так что я не буду здесь его описывать).

Параметр шаблона Key — это, как и в случае с другими стандартными контейнерами, тип сохраняемых элементов. Для set он определяется через typedef как set<Key>::key_type, так что доступ к нему есть при выполнении программы. Класс Key должен обеспечивать конструктор копирования и присвоение, и все.

Пример 6.10 показывает, как использовать set для строк. Использование набора для хранения объектов других типов работает точно так же — объявите набор с именем класса в качестве параметра шаблона.

std::set<MyClass> setMyObjs;

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

Пример 6.11. Хранение указателей в set

#include <iostream>
#include <set>
#include <string>
#include <functional>
#include <cassert>
using namespace std;
// Класс для сравнения строк, переданных через указатели
struct strPtrLess {
 bool operator()(const string* p1,
  const string* p2) {
  assert(p1 && p2);
  return(*p1 < *p2);
 }
 int main() (
  set<string*, strPtrLess> setStrPtr; // Передаем специальный
                                      // «меньше чем» функтор
 string s1 = 'Tom';
 string s2 = 'Dick';
 string s3 = 'Harry';
 setStrPtr.insert(&s1);
 setStrPtr.insert(&s2);
 setStrPtr.insert(&s3);
 for (set<string*, strPtrLess>::const_iterator p =
  setStrPtr.begin(); p != setStrPtr.end(); ++p)
  cout << **p << endl; // Разыменовываем итератор и то, на что
                       // он указывает
}

strPtrLess возвращает истину, если строка, на которую указывает p1, меньше, чем та, на которую указывает p2. Это делает его двоичным предикатом, так как он принимает два аргумента и возвращает bool. Так как operator< определен для string, для сравнения я использую именно его. На самом деле, если требуется использовать более общий подход, используйте для предиката сравнения шаблон класса

template<typename T>
class ptrLess {
public:
 bool operator()(const T* p1,
  const T* p2) {
  assert(p1 && p2);
  return(*p1 < *p2);
 }
};