Почему не следует использовать std::set (и что стоит использовать вместо)

Этот пост является переводом статьи Мэтта Остерна: Why you shouldn't use set (and what you should use instead).
Все, что находится в стандартной библиотеке С++, находится там по какой-то причине, но это не всегда очевидно, по какой именно. Стандарт - это не руководство, в нем не проводится разделения между базовыми компонентами, которые используются постоянно, и теми компонентами, которые были добавлены в стандарт для редких и специфичных случаев.
Один из примеров - это ассоциативный контейнер std::set (и родственные ему map, multiset, multimap). Иногда использование set действительно имеет смысл, но не так часто, как вы могли бы подумать. Стандартная библиотека предоставляет и другие инструменты, позволяющие хранить данные и совершать выборку данных, и часто можно достичь тех же целей, что достигаются при использовании set, используя при этом более простые, более легковесные и более быстрые структуры данных.

Что такое set?

Set - это контейнер STL, позволяющий хранить данные и совершать быстрый поиск данных. Например, можно создать set, состоящий из объектов string:

?

1	std::set<std::string> S;

Можно добавить новый элемент в set, написав:

?

1	S.insert("foo");

В set не может быть двух элементов с одинаковым ключом, поэтому вызов insert ничего не добавит в контейнер S, если строка "foo" уже в нем содержится; вместо этого будет произведен поиск существущего элемента. В возвращаемом значении присутствует стутас-код, показывающий, был ли добавлен новый элемент.
Как и во всех STL контейнерах, в set можно последовательно получить доступ ко всем элементам с помощью итераторов. S.begin() вернет итератор, указывающий на первый элемент контейнера, а S.end() - итератор, указывающий на область памяти непосредственно следующую за последним элементом контейнера. Элементы внутри set всегда отсортированы по возразстанию - поэтому в методе insert нет параметра, отвечающего за то, куда конкретно должне быть вставлен новый элемент. Новый элемент будет автоматически вставлен в нужное место.
То, что set является ассоциативным контейнером, означает, что можно выбрать из него элемент по значению, написав:

?

1	i = S.find("foo");

Если элемент с таким значением был найден, find вернет итератор, указывающий на найденный элемент в контейнере. Если элемента с заданным занчением нет в контейнере, find вернет итератор S.end(), который не указывает ни на один элемент.
Что если нам нужно, чтобы элементы были отсортированы в ином порядке, нежели по возрастанию, или мы хотим создать set из элементов, для которых не определена опрецаия "less than"? В этом случае следует использовать второй параметр шаблона set - функциональный объект (функтор), который определяет, какой из двух объектов должен находиться раньше другого в контейнере. По умолчанию этим объектом является std::less<T>, что означает, что меньший элемент будет идти первым. Можно создать set, состоящий из объектов string, которые будут отсортированы по убыванию, используя нестандартный функтор для сравнения элементов контейнера:

?

1	std::set< std::string, std::greater< std::string > > S;

или можно хранить объекты string отсортированными без учета регистра, реализовав собственный функтор:

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

struct less_nocase {     static bool compare_chars( char x, char y )     {         return std::toupper( x ) < std::toupper( y );     }     bool operator( )( const string& x, const string& y ) const     {         return std::lexicographical_compare( x.begin( ), x.end( ),                                              y.begin( ), y.end( ),                                              compare_chars );     } };   std::set < std::string, less_nocase > S;

Предостережение: сравнение объектов string без учета регистра немного сложнее, чем выглядит на первый взгляд и код, приведенный выше, немного неправильный. В этой статье Мэтта Остерна объясняется, что с ним не так и как его нужно переписать: How to do case-insensitive string comparison (англ.).
В более общем случае можно хранить в set некоторые сложные структуры данных и использовать для сравнения только их определнные свойства:

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

struct Client {     unsigned long id;     string last_name, first_name;     ... };   struct id_compare {     bool operator( )( const Client& x, const Client& y ) const     {         return x.id < y.id;     } }; std::set< Client, id_compare > clients;

Конечно, описание set этим не ограничивается. У set есть обычные функции-члены STL контейнера и еще ряд собственых функций-членов. Но основное предназначение set - это управление коллекцией элементов которые могут быть выбраны по значению. (Ассоциативный контейнер map очень похож на set за исключением того, что в set элементы являются своими собственными ключами, тогда как в map элементы - это объекты типа pair; первый член такого объекта - это ключ, а второй - это значение, соответсвующее ключу.)

Что не так?

Строго говоря, все так, просто описание не совсем полное. Я привел описание set, но не назвал ни одной причины, по которой вам следовало бы использовать этот контейнер. В конце концов, вам не нужны специальные структуры данных или функции-члены чтобы вставлять элементы или производить выборку. Имея любой STL контейнер C вы можете выбрать из него элемент с помощью функции find: 

?

1	i = std::find( C.begin( ), C.end( ), "foo" );

Так же как и функция-член set::find эта фнкция вернет итератор, указывающий на искомый элемент или С.end( ), если элемент не был найден. Единственное важное отличие заключается в том, что std::find выполняет линейный поиск (полный перебор), поэтому время затраченное на поиск будет пропорционально N (где N - количество элементов в контейнере), тогда как время, затраченное set::find будет пропорционально logN. То есть, если N - большое, set::find потратит гораздо меньше времени. Ключевая идея set и других ассоциативных контейнеров в в стандартной библиотеке С++ заключается в том, что они дают определнные гарантии по производительности: гарантируется, что время, затраченное на поиск элемента, будет пропорционально logN, где N - количество элементов в контейнере, а также то, что время на вставку элемента будет тоже пропорционально logN. Также есть дополнительные гарантии, касающиеся безопасности исключений и недействительных итераторов; эти гарантии также иногда важны.
Но если вам не нужны все эти свойства, то вы будете платить за что-то, что вы не используете. Структура данных, которая обеспечивает быструю вставку и быструю выборку обязательно является довольно сложной; set обычно реализуется с помощью красно-черных деревьев, что влечет за собой существенные накладные расходы по памяти и производительности. Каждый элемент требует больше трех дополнительных машинных слов в памяти (цветовой маркер и указатели на двух потомков и родителя). Процедура вставки требует перебалансировки дерева, а процедуры поиска и последовательного прохода по всем элементам требуют разыменования указателей.
Если вам действительно необходимо, чтобы время поиска и вставки было пропорционально logN, set - это разумный выбор. Но если это не обязательно, то у вас есть и другие опции. Представьте, например, что вы готовы пожертвовать гарантией вставки за время logN. Это совсем не редкая ситуация - вполне возможно, что вам необходимо осуществлять поиск элементов гораздо чаще, чем вставку.
Красно-черные деревья - не единственная структура данных, которая обеспечивает поиск за логарифмическое время. Один из базовых алгоритмов в информатике - это двоичный поиск, идея которого состоит в последовательном делении диапазона поиска пополам. Алгоритм работает за время, пропорциональное logN, и ему не нужны хоть сколько-нибудь сложные структуры данных для работы - достаточно просто отсортированной коллекции элементов. Двоичный поиск представлен в STL - не как часть какого-то контейнера, а в виде общих алгоритмов lower_bound, upper_bound, equal_range и binary_search. На практике  lower_bound выглядит наиболее полезным. Если [first, last) - это диапазон итераторов, и если элементы в этом диапазона отсортированы по возрастанию, тогда
std::lower_bound(first, last, x);
вернет итератор, указывающий на элемент, эквивалентный x (если такой элемент существует), или, если такого элемента нет в диапазоне, итератор, указывающий на позицию, где такой элемент должен был бы находиться. Вы можете использовать ту структуру данных, которая вам удобна, если она предоставляет STL итератор; обычно проще всего использовать массив из C или vector.
Обе функции, std::lower_bound и std::find, требуют для выполнения время, пропорциональное logN, но константные множители довольно сильно отличаются. При использовании g++ и Pentium III 450MHz требуется 0,9 секунды, чтобы выполнить поиск миллион раз в отсортированном контейнере vector< double > содержащем миллион элементов,  и почти в два раза больше - 1,71 секунды, чтобы сделать то же самое с set. Более того, решение с set  использует почти в три раза больше памяти (48 миллионов байт), нежели решение с vector (16,8 миллионов байт).
Если вам необходимо вставить новые элементы, конечно, необходимо их вставлять на правильную позицию - lower_bound вернет неправильный результат, если заданный диапазон поиска не отсортирован. Правильная позиция - это как раз то, что lower_bound и возвращает:

?

1 2 3 4 5 6 7 8

void insert_into_vector( Vector& v, const T& t ) {     typename Vector::iterator i = std::lower_bound( v.begin( ), v.end( ), t );     if ( i == v.end( ) || t < *i )     {         V.insert( i, t );     } }

Эта вспомогательная функция проверяет, присутствует ли элемент t в контейнере перед тем, как совершить вставку. Если предполагается хранение дубликатов как в multiset, то можно убрать эту проверку.
Использование отсортированного вектора вместо set дает более быстрый поиск элементов и гораздо более быструю итерацию по элементам за счет более медленной вставки. Вставка в set с помощью set::insert потребует время, пропорциональное logN, а вставка в отсортированный вектор с помощью insert_into_vector - время, пропорциональное N. Когда вы вставляете какой-либо элемент в vector, метод vector::insert должен освободить место для нового эллемента, сдинув все элементы, которык должны следовать за ним. Если новый элемент с одинаковой вероятностью попадает на любую позицию в векторе, среднее количество сдвигов будет N/2.
Существует два особых случая когда дополнительные накладные расходы будут не такими большими. Во-первых, в случае, когда элементы, которые вы вставляете в vector, всегда попадают в конец. Действительно, если вы вставляете элементы в правильном порядке, методу vector::insert никогда не придется передвигать имеющиеся элементы. (И "практически в правильном порядке" практически так же хорошо, как и в "правильном порядке"!) Во-вторых, возможно, вы можете заполнить коллекцию целиком до того, как вам придется что-то в ней искать; например, программа проверки правописания изначально имеет огромный словарь и лишь иногда добавляет в него новые слова. Вектору необязательно быть отсортированным до того, как вам понадобится выполнить поиск элемента внутри него, поэтому вы можете быстро создать неотсортированную коллекцию, используя для вставки vector::push_back вместо insert_into_vector, и затем отсортировать весь вектор с помощью:

?

1	std::sort( v.begin( ), v.end( ) );.

Иногда удобно собрать это все воедино в небольшом классе-адаптере. Ради сохранения места я опущу код, необходимый для соответствия полному интерфейсу STL контейнера. Основные части при этом довольно просты.

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66

template < class T, class Compare = std::less< T > > struct sorted_vector {     using std::vector;     using std::lower_bound;       vector< T > V;     Compare cmp;       typedef typename vector< T >::iterator iterator;     typedef typename vector< T >::const_iterator const_iterator;       iterator begin( )     {         return V.begin( );     }       iterator end( )     {         return V.end( );     }           const_iterator begin( ) const     {         return V.begin( );     }       const_iterator end( ) const     {         return V.end( );     }       ...       sorted_vector( const Compare& c = Compare( ) )         : V( )         , cmp( c )     {}       template < class InputIterator >     sorted_vector( InputIterator first, InputIterator last,                    Const Compare& c = Compare( ) )         : V( first, last )         , cmp( c )     {         std::sort( begin( ), end( ), cmp );     }       ...       iterator insert( const T& t )     {         iterator i = lower_bound( begin( ), end( ), t, cmp );         if ( i == end( ) || cmp( t, *i ) )         {             V.insert( i, t );             return i;         }     }       const_iterator find( const T& t ) const     {         const_iterator i = lower_bound( begin( ), end( ), t, cmp );         return i == end( ) || cmp( t, *i ) ? end( ) : i;     } };

Этот класс не удовлетворяет требованиям для стандартного ассоциативного контейнера, так как ассимптотическая сложность метода insert - O(N) вместо O(logN), но помимо этого это практически эквивалентная замена set.

Для каких целей хорош set?

Идея статьи не в том, что set бесполезен - существуют ситуации в которых set - правильный выбор. Наконец, мы можем выписать условия, при которых set - это лучший выбор, нежели sorted_vector или его эквивалент.

• Коллекция может дорасти до таких размеров, когда разница между O(N) и O(logN) будет существенной.
• Число операций поиска является величиной того же порядка, что и число операций вставки; число операций вставки не настолько мало, что скорость вставки перестает иметь значение.
• Элементы добавляются в контейнер в случайном порядке, а не отсортированными.
• Операции вставки и поиска перемешаны между собой; невозможно выделить отдельные фазы наполнения контейнера и фазы поиска элементов в контейнере.

Иногда все четыре условия выполняются. В этом случае следует использовать set - он был спроектирован как раз для этого случая. Но если хотя бы одного из условий не выполняется, использование такой сложной стрктуры данных теряет смысл, и вы получите лучшую по производительности реализацию, использовав отсортированный вектор.
Все компоненты в стандартной библиотеке С++ находятся там, потому что они полезны в той или иной ситуациях, но иногда эти ситуации являются узкоспециализированными и редко встречающимися. Общее же правило можно сформулировать следующим образом: всегда следует использовать наиболее простую структуру данных, которая удовлетворяет вашим нуждам. Чем структура данных сложнее, тем более вероятно, что она не должна использоваться так часто, как может показаться.