Скотт Мейерс - Эффективное использование STL

• Название: Эффективное использование STL
• Автор: Скотт Мейерс
• Издательство: Питер
• Жанр: Программирование
• Год: 2002
• ISBN: 5-94723-382-7

В этой книге известный автор Скотт Мейерс раскрывает секреты настоящих мастеров, позволяющие добиться максимальной эффективности при работе с библиотекой STL.

Во многих книгах описываются возможности STL, но только в этой рассказано о том, как работать с этой библиотекой. Каждый из 50 советов книги подкреплен анализом и убедительными примерами, поэтому читатель не только узнает, как решать ту или иную задачу, но и когда следует выбирать то или иное решение — и почему именно такое.

---

Сначала выясним, почему элементы set и multiset не имеют атрибута const. Допустим, у нас имеется класс Employee:

class Employee {

public:

 …

 const string& name() const; // Возвращает имя работника

 void setName(const string& name); // Задает имя работника

 const string& title() const; // Возвращает должность

 void setTitle(const string& title); // Задает должность

 int idNumber() const; // Возвращает код работника

 …

}

Объект содержит разнообразные сведения о работнике. Каждому работнику назначается уникальный код, возвращаемый функцией idNumber. При создании контейнера set с объектами Employee было бы вполне разумно упорядочить его по кодам работников:

struct IDNumberLess:

 public binary_function<Employee, Employee, bool> { // См. совет 40

 bool operator() (const Employees lhs, const Employees rhs) const {

  return lhs.idNumber() < rhs. IdNumber();

 }

}

typedef set<Employee, IDNumberLess> EmplIDSet;

EmplIDSet se; // Контейнер set объектов

              // Employee, упорядоченных

              // по коду

С практической точки зрения код работника является ключомдля элементов данного множества, а остальные данные вторичны. Учитывая это обстоятельство, ничто не мешает перевести работника на более интересную должность. Пример:

Employee selectedID; // Объект работника с заданным кодом

…

EmpIDSet::iterator = se.find(selectedID);

if (i!=se.end()) {

 i->setTitle("Corporate Deity"); // Изменить должность

}

Поскольку мы всего лишь изменяем вторичный атрибут данных, не влияющий на порядок сортировки набора, этот фрагмент не приведет к порче данных, и он вполне допустим.

Спрашивается, почему нельзя применить ту же логику к ключам контейнеров map и multimap? Почему бы не создать контейнер map, ассоциирующий работников со страной, в которой они живут; контейнер с функцией сравнения IDNumberLess, как в предыдущем примере? И почему бы в таком контейнере не изменить должность без изменения кода работника, как в предыдущем примере?

Откровенно говоря, мне это кажется вполне логичным, однако мое личное мнение в данном случае несущественно. Важно то, что Комитет по стандартизации решил, что ключи map/multimap должны быть неизменными (const), а значения set/multiset — не должны.

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

Впрочем, не все так просто. Хотя элементы set/multiset и не являются неизменными, реализации могут предотвратить их возможную модификацию. Например, оператор * для set<T>::iterator может возвращать const T&, то есть результат разыменования итератора set может быть ссылкой на const-элемент контейнера! При такой реализации изменение элементов set и multiset невозможно, поскольку при любом обращении к элементу автоматически добавляется объявление const.

Законны ли такие реализации? Может, да, а может — нет. По этому вопросу Стандарт высказывается недостаточно четко, и в соответствии с законом Мерфи разные авторы интерпретируют его по-разному. В результате достаточно часто встречаются реализации STL, в которых следующий фрагмент компилироваться не будет (хотя ранее говорилось о том, что он успешно компилируется):

EmplIDSet se; // Контейнер set объектов

              // Employee, упорядоченных

              // по коду

Employee selectedID; // Объект работника с заданным кодом

…

EmpIDSet::iterator = se.find(selectedID);

if (i!=se.end()) {

 i->setTitle("Corporate Deity"); // Некоторые реализации STL

};                               // выдают ошибку в этой строке

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

Что из этого следует? К счастью, ничего особенно сложного:

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

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

Кстати, о преобразованиях. Вы убедились в том, что изменение вторичных данных элемента set/multiset может быть вполне оправданно, поэтому я склонен показать, как это делается — а точнее, делается правильно и переносимо. Сделать это нетрудно, но при этом приходится учитывать тонкость, о которой забывают многие программисты — преобразование должно приводить к ссылке. В качестве примера рассмотрим вызов setTitle, который, как было показано, не компилируется в некоторых реализациях:

EmpIDSet::iterator i = se.find(selectedID);

if (i != se.end()) {

 i->setTitle("Corporate Deity"); // Некоторые реализации STL

}                                // выдают ошибку в этой строке,

                                 // поскольку *i имеет атрибут const

Чтобы этот фрагмент нормально компилировался и работал, необходимо устранить константность *i. Правильный способ выглядит так:

if (i != se.end()){                                     // Устранить

 const_cast<Empioyee&>(*i).setTitle("Corporate Deity"); // константность *i

}

Мы берем объект, на который ссылается i, и сообщаем компилятору, что результат должен интерпретироваться как ссылка на (неконстантный) объект Employee, после чего вызываем setTitle для полученной ссылки. Я не буду тратить время на долгие объяснения и лучше покажу, почему альтернативное решение работает совсем не так, как можно было бы ожидать.

Многие программисты пытаются воспользоваться следующим кодом:

if (i != se.end()){                                     // Преобразовать *i

 static_cast<Employee>(*i).setTitle("Corporate Deity"); // к Employee

}

Приведенный фрагмент эквивалентен следующему:

if (i != se.end()){                            // То же самое,

 ((Employee)(*i)).setTitle("Corporate Deity"); // но с использованием

}                                              // синтаксиса С

Оба фрагмента компилируются, но вследствие эквивалентности работают неправильно. На стадии выполнения объект *i не модифицируется, поскольку в обоих случаях результатом преобразования является временный анонимный объект — копия *i, и setTitle вызывается для анонимного объекта, а не для *i! Обе синтаксические формы эквивалентны следующему фрагменту:

if (i != se.end()) {

 Employee tempCopy(*i);                // Скопировать *i в tempCopy

 tempCopy.setTitle("Corporate Deity"); // Изменить tempCopy

}

Становится понятно, почему преобразование должно приводить именно к ссылке — тем самым мы избегаем создания нового объекта. Вместо этого результат преобразования представляет собой ссылку на существующийобъект, на который указывает i. При вызове setTitle для объекта, обозначенного ссылкой, функция вызывается для *i, чего мы и добивались.

Все сказанное хорошо подходит для контейнеров set и multiset, но при переходе к map/multimap ситуация усложняется. Вспомните, что map<K, V> и multimap<K, V> содержат элементы типа pair<const K, V>. Объявление const означает, что первый компонент пары определяетсякак константа, а из этого следует, что любые попытки устранить его константность приводят к непредсказуемому результату. Теоретически реализация STL может записывать такие данные в область памяти, доступную только для чтения (например, в страницу виртуальной памяти, которая после исходной записи защищается вызовом системной функции), и попытки устранить их константность в лучшем случае ни к чему не приведут. Я никогда не слышал о реализациях, которые бы поступали подобным образом, но если вы стремитесь придерживаться правил, установленных в Стандарте, — никогдане пытайтесь устранять константность ключей в контейнерах map и multimap.