6.8. Хранение объектов в упорядоченном виде

6.8. Хранение объектов в упорядоченном виде

Проблема

Требуется сохранить набор объектов в заданном порядке, например с целью доступа к упорядоченным диапазонам этих объектов без их пересортировки при каждом таком обращении.

Решение

Используйте ассоциативный контейнер set, объявленный в <set>, который хранит элементы в упорядоченном виде. По умолчанию он использует стандартный шаблон класса less (который для своих аргументов вызывает operator<), а можно передать в него собственный предикат сортировки. Пример 6.10 показывает, как сохранить строки в set.

Пример 6.10. Хранение строк в set

#include <iostream>

#include <set>

#include <string>

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);

 }

};

Это работает для указателей на любые объекты, для которых определен operator<. Объявление набора с его использованием имеет такой вид.

set<string*, ptrLess<string> > setStrPtr;

set поддерживает многие из функций, поддерживаемых другими стандартными последовательными контейнерами (например, begin, end, size, max_size) и другими ассоциативными контейнерами (например, insert, erase, clear, find).

При использовании set помните, что при каждом изменении состояния набора выполняется его сортировка. Когда число его элементов велико, логарифмическая сложность добавления или удаления элементов может оказаться очень большой — вам действительно требуется, чтобы объекты сортировались каждый раз? Если нет, то для повышения производительности используйте vector или list и сортируйте его только тогда, когда это необходимо, что обычно имеет сложность порядка n*log(n).