Книга: Эффективное использование STL

Совет 20. Определите тип сравнения для ассоциативного контейнера, содержащего указатели

Совет 20. Определите тип сравнения для ассоциативного контейнера, содержащего указатели

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

set<string*> ssp; // ssp = "set of string ptrs"
ssp.insert(new string("Anteater"));
ssp.insert(new string("Wombat"));
ssp.insert(new string("Lemur"));
ssp.insert(new string("Penguin"));

Следующий фрагмент выводит содержимое set. Предполагается, что строки будут выведены в алфавитном порядке — ведь содержимое контейнеров set автоматически сортируется!

for (set<string*>::const_iterator i = ssp.begin(); // Предполагаемый
 i!=ssp.end();                                     // порядок вывода:
 ++i)                                              // "Anteater", "Lemur"
 cout << *i << endl;                               // "Penguin", "Wombat"

Однако на практике ничего похожего не происходит. Вместо строк выводятся четыре шестнадцатеричных числа — значения указателей. Поскольку в контейнере set хранятся указатели, *i является не строкой, а указателем на строку. Пусть этот урок напоминает, чтобы вы следовали рекомендациям совета 43 и избегали написания собственных циклов. Использование алгоритма copy:

copy(ssp.begin(), ssp.end(),           // Скопировать строки.
 ostream_iterator<string>(cout,"n")); //содержащиеся в ssp, в cout
                                       //(не компилируется!)

не только делает программу более компактной, но и помогает быстрее обнаружить ошибку, поскольку вызов copy не компилируется. Итератор ostream_iterator должен знать тип выводимого объекта, поэтому когда компилятор обнаруживает расхождение между заданным в параметре шаблона типом string и типом объекта, хранящегося в ssp(string*), он выдает ошибку. Еще один довод в пользу сильной типизации…

Если заменить *i в цикле на **i, возможно, вы получите нужный результат — но скорее всего, этого не произойдет. Да, строки будут выведены, но вероятность их следования в алфавитном порядке равна всего 1/24. Контейнер ssp хранит свои элементы в отсортированном виде, однако он содержит указатели, поэтому сортироваться будут значения указателей, а не строки. Существует 24 возможных перестановки для четырех указателей, то есть 24 разных последовательности, из которых лишь одна отсортирована в алфавитном порядке[2].

Подходя к решению этой проблемы, нелишне вспомнить, что объявление

set<string*> ssp;

представляет собой сокращенную запись для объявления

set<string*, less<string*> > ssp;

Строго говоря, это сокращенная запись для объявления

set<string*, less<string*>, allocator<string*> > ssp;

но в контексте данного совета распределители памяти несущественны.

Если вы хотите сохранить указатели string* в контейнере set так, чтобы их порядок определялся значениями строк, стандартный функтор сравнения less<string*> вам не подойдет. Вместо этого необходимо написать собственный функтор сравнения, который получает указатели string* и упорядочивает их по содержимому строк, на которые они ссылаются. Пример:

struct StringPtrLess:
 public binary_function<const string*, // Базовый класс
 const string*,                        // описан в совете 40
 bool> {
 bool operator() (const string *ps1, const string *ps2) const {
  return *ps1 < *ps2:
 }
};

После этого StringPtrLess используется в качестве типа критерия сравнения ssp:

typedef set<string*, StringPtrLess> StringPtrSet;
StringPtrSet ssp; // Создать множество с объектами string
                  // и порядком сортировки, определяемым
                  // критерием StringPtrLess
                  // Вставить те же четыре строки

Теперь приведенный выше цикл будет работать именно так, как предполагалось (при условии, что ошибка была исправлена и вместо *i используется **i).

for (StringPtrSet::const_iterator i = ssp.begin();
 i != ssp.end();      // Порядок вывода:
 ++i)                 // "Anteater", "Lemur",
 cout << **i << endl; // "Penguin", "Wombat"

Если вы предпочитаете использовать алгоритм, напишите функцию, которая разыменовывает указатели string* перед выводом, а затем используйте ее в сочетании с for_each:

void print(const string *ps) // Вывести в cout объект,
{                            // на который ссылается ps
 cout << *ps << endl;
}
for_each(ssp.begin(), ssp.end(), print); // Вызвать print для каждого
                                         // элемента ssp

Существует более изощренное решение — обобщенный функтор разыменования, используемый с transform и ostream_iterator:

// Функтор получает T* и возвращает const T&
struct Dereference {
 template<typename T>
 const T& operator()(const T* ptr) const {
  return *ptr;
 }
};
transform(ssp.begin(), ssp.end(),      // "Преобразовать" каждый
 ostream.iterator<string>(cout, "n"), // элемент ssp посредством
 Dereference());                       // разыменования и записать
                                       // результаты в cout

Впрочем, замена циклов алгоритмами будет подробно рассматриваться позднее, в совете 43. А сейчас речь идет о том, что при создании стандартного ассоциативного контейнера указателей следует помнить: содержимое контейнера будет сортироваться по значениям указателей. Вряд ли такой порядок сортировки вас устроит, поэтому почти всегда определяются классы-функторы, используемые в качестве типов сравнения.

Обратите внимание на термин «тип сравнения». Возможно, вас интересует, зачем возиться с созданием функтора вместо того, чтобы просто написать функцию сравнения для контейнера set? Например, так:

bool stringPtrLess(const string* ps1, // Предполагаемая функция сравнения
 const string* ps2)                   // для указателей string*,
{                                     // сортируемых по содержимому строки
 return *ps1 < *ps2;
}
set<string, stringPtrLess> ssp; // Попытка использования stringPtrLess
                                // в качестве функции сравнения ssp.
// Не компилируется!!!

Проблема заключается в том, что каждый из трех параметров шаблона set должен быть типом. К сожалению, stringPtrLess — не тип, а функция, поэтому попытка задать stringPtrLess в качестве функции сравнения set не компилируется. Контейнеру set не нужна функция; ему нужен тип, на основании которого можно создатьфункцию.

Каждый раз, когда вы создаете ассоциативный контейнер указателей, помните о том, что вам, возможно, придется задать тип сравнения контейнера. В большинстве случаев тип сравнения сводится к разыменованию указателя и сравнению объектов, как это сделано в приведенном выше примере StringPtrLess. Шаблон для таких функторов сравнения стоит держать под рукой. Пример:

struct DereferenceLess {
 template <typename PtrType>
 bool operator()(PtrType pT1, // Параметры передаются по значению.
  PtrType рТ2) const          // поскольку они должны быть
 {                            // указателями (или по крайней мере
  return *рТ1 < *рТ2;         // вести себя, как указатели)
 }
};

Данный шаблон снимает необходимость в написании таких классов, как StringPtrLess, поскольку вместо них можно использовать DereferenceLess:

set<string*, DereferenceLess> ssp; // Ведет себя так же, как
                                   // set<string*, stringPtrLess>

И последнее замечание. Данный совет посвящен ассоциативным контейнерам указателей, но он в равной степени относится и к контейнерам объектов, которые ведут себя как указатели (например, умные указатели и итераторы). Если у вас имеется ассоциативный контейнер умных указателей или итераторов, подумайте, не стоит ли задать тип сравнения и для него. К счастью, решение, приведенное для указателей, работает и для объектов-аналогов. Если определение DereferenceLess подходит в качестве типа сравнения для ассоциативного контейнера T*, оно с большой вероятностью подойдет и для контейнеров итераторов и умных указателей на объекты T.

Оглавление книги