C++. Сборник рецептов - Д. Стефенс

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

6.9. Хранение контейнеров в контейнерах

Имеется несколько экземпляров стандартного контейнера (list, set и т.п.) и требуется сохранить их в еще одном контейнере.

Сохраните в главном контейнере указатели на остальные контейнеры. Например, можно использовать map для хранения ключа типа string и указателя на set как значения. Пример 6.12 показывает простой класс журналирования транзакций, который хранит данные как map из пар, состоящих из string и указателей на set.

Пример 6.12. Хранение набора указателей в отображении

#include <iostream>

#include <set>

#include <map>

#include <string>

using namespace std;

typedef set<string> SetStr

typedef map<string, SetStr*> MapStrSetStr;

// Фиктивный класс базы данных

class DBConn {

public:

 void beginTxn() {}

 void endTxn() {}

 void execSql(string& sql) {}

};

class SimpleTxnLog {

public:

 SimpleTxrLog() {}

 ~SimpleTxrLog() {purge();}

 // Добавляем в список выражение SQL

 void addTxn(const string& id

  const string& sql) {

  SetStr* pSet = log_[id]; // Здесь создается запись для

  if (pSet == NULL) {      // данного id, если ее еще нет

   pSet = new SetStr();

   log_[id] = pSet;

  }

  pSet->insert(sol);

 }

 // Применение выражений SQL к базе данных, по одной транзакции

 // за один раз

 void apply() {

  for (MapStrSetStr::iterator p = log_.begin();

   p != log_.end(); ++p) {

   conn_->beginTxn();

   // Помните, что итератор отображения ссылается на объект

   // типа pair<Key,Val>. Указатель на набор хранится в p->second.

   for (SetStr::iterator pSql = p->second->begin();

    pSql != p->second->end(); ++pSql) {

    string s = *pSql;

    conn_->execSql(s);

    cout << "Executing SQL: " << s << endl;

   }

   conn_->endTxn();

   delete p->second;

  }

  log_.clear();

 }

 void purge() {

  for (MapStrSetStr::iterator p = log_.begin();

   p != log_.end(); ++p)

   delete p->second;

  log_.clear();

 }

 //...

private:

 MapStrSetStr log_;

 DBConn* conn_;

};

Пример 6.12 предлагает ситуацию, где может потребоваться хранение одного контейнера в другом. Представьте, что требуется сохранить набор выражений SQL в виде пакета, выполнить их в будущем все сразу для реляционной базы данных. Именно это делает SimpleTxnLog. Чтобы сделать его еще полезнее, можно добавить в него другие методы, а для обеспечения безопасности — добавить обработку исключений, но целью этого примера является показать, как хранить один тип контейнеров в другом.

Для начала я создаю несколько typedef, облегчающих чтение кода.

typedef std::set<std::string> SetStr;

typedef std::map<std::string, SetStr*> MapStrSetStr;

При использовании шаблонов шаблонов (шаблонов… и т.д.) объявления становятся очень длинными, что затрудняет их чтение, так что облегчите себе жизнь, использовав typedef. Более того, использование typedef облегчает внесение изменений в объявление шаблонов, избавляя от необходимости выполнять поиск и замену во многих местах большого количества исходных файлов.

Класс DBConn — это фиктивный класс, который представляет подключение к реляционной базе данных. Интересно здесь то, как в SimpleTxnLog определяется метод addTxn. В начале этой функции я смотрю, существует ли уже объект набора для переданного id.

SetStr* pSet = log_[id];

log_ — это map (см. рецепт 6.6), так что operator[] выполняет поиск id и смотрит, связаны ли с ним какие-либо данные. Если да, то возвращается объект данных, и pSet не равен NULL. Если нет, он создается, и возвращается указатель, который будет равен NULL. Затем я проверяю, указывает ли на что-то pSet, и определяю, требуется ли создать еще один набор.

if (pSet == NULL) {

 pSet = new SetStr(); // SetStr = std::set<std::string>

 log_[id] = pSet;

}

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

pSet->insert(sql);

Выполнив указанные шаги, я в один контейнер (map) добавил указатель на адрес другого контейнера (set). Что я не делал — это добавление объекта set в map. Разница очень существенна. Так как контейнеры обладают семантикой копирования, следующий код приведет к копированию всего набора s в map.