C++17 STL Стандартная библиотека шаблонов — страница 18 из 119

< "): " << value << "} ";
  }
  std::cout << '\n';
}

7. Компиляция и запуск программы дадут следующий результат:

$ ./custom_type_unordered_map
{(2, 1): 3} {(0, 1): 2} {(0, 0): 1}

Как это работает

Обычно при создании экземпляра ассоциативного массива, основанного на хеше, например std::unordered_map, мы пишем следующую команду:

std::unordered_map my_unordered_map;

Не вполне очевиден тот факт, что при создании компилятором контейнера уточненного типа std::unordered_map за кулисами творится настоящее волшебство. Поэтому взглянем на полное определение шаблонного типа:

template<
  class Key,
  class T,
  class Hash = std::hash,
  class KeyEqual = std::equal_to,
  class Allocator = std::allocator< std::pair>
> class unordered_map;

В качестве первых двух типов шаблона мы выбрали coord иint, здесь все просто и очевидно. Три остальных типа шаблона являются необязательными, так что автоматически заполняются существующими стандартными шаблонными классами, которые сами принимают типы шаблонов. В случае если последние аргументы заполняются значениями по умолчанию, в качестве типов шаблонов передаются те типы, которые мы указали в первых двух аргументах.

Для нас сейчас особый интерес представляет шаблонный параметр class Hash: когда мы не указываем явно что-то другое, он будет специализирован как std::hash. STL уже содержит специализации std::hash, std::hash, std::hash и многие другие. Эти классы знают, как работать с подобными конкретными типами, что позволяет вычислять оптимальные хеш-значения.

Однако STL пока не знает, как рассчитывать хеш-значение на основе нашей структуры coord. Мы лишь определили еще одну специализацию, которая знает, как это делается. Компилятор теперь может пройти по списку всех известных специализаций для контейнера std::hash и найти нашу реализацию, что позволит соотнести ее с типом, который мы выбрали для ключа.

Если бы мы не добавили новую специализацию std::hash, а назвали бы имеющуюся вместо этого my_hash_type, то нам пришлось бы использовать следующую строку для создания объекта:

std::unordered_map my_unordered_map;

Очевидно, что таким образом придется набирать больше кода. Кроме того, при этом подходе код тяжелее читать, в отличие от ситуации, когда компилятор самостоятельно находит правильную реализацию хеш-функции. 

Отсеиваем повторяющиеся слова из пользовательского ввода и выводим их на экран в алфавитном порядке с помощью контейнера std::set

 Контейнер std::set довольно странный. Принцип его работы похож на принцип работы контейнера std::map. Однако std::set содержит только ключи в качестве значений, а не пары «ключ — значение». Поэтому он не очень подходит для соотношения значения одного типа со значениями другого. Поскольку способы применения этого контейнера не вполне очевидны, многие разработчики даже не знают о его существовании. Они часто начинают реализовывать похожие механизмы самостоятельно, хотя в некоторых ситуациях контейнер std::set оказался бы отличным подспорьем.

В этом разделе будет показано, как применить контейнер std::set, на примере, в котором мы получаем потенциально большое количество разных элементов. Мы отфильтруем их и выведем на экран уникальные элементы.

Как это делается

В этом примере мы считаем поток слов из стандартного средства ввода. Все уникальные слова будут помещены в экземпляр класса std::set. Таким образом мы сможем перечислить все уникальные слова из потока[1].

1. Мы используем несколько разных типов STL, для чего включим некоторые заголовочные файлы:

#include 
#include 
#include 
#include 

2. Чтобы сэкономить немного времени на наборе текста, объявим об использовании пространства имен std:

using namespace std;

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

int main()
{
  set s;

4. Далее получим данные от пользователя. Просто считаем их из стандартного потока ввода с помощью удобного итератора istream_iterator:

  istream_iterator it {cin};
  istream_iterator end;

5. Имея начальный и конечный итераторы, которые представляют данные, введенные пользователем, можем просто заполнить множество на основе этих данных с помощью std::inserter:

  copy(it, end, inserter(s, s.end()));

6. На этом, в общем-то, все. Чтобы увидеть, какие уникальные слова мы получили из стандартного ввода, просто выведем на экран содержимое нашего множества:

  for (const auto word : s) {
    cout << word << ", ";
  }
  cout << '\n';
}

7. Скомпилируем и запустим программу с нашими входными данными. Взглянем на полученный результат, из которого были удалены все дубликаты, а уникальные слова теперь отсортированы по алфавиту:

$ echo "a a a b c foo bar foobar foo bar bar" | ./program
a, b, bar, c, foo, foobar,

Как это работает

В данной программе можно отметить два интересных момента. Первый из них состоит в том, что мы применяем итератор std::istream_iterator, чтобы получить доступ к данным, введенным пользователем. Второй момент: для записи этих данных в наш контейнер std::set мы задействуем алгоритм std::copy, который обернули в экземпляр класса std::inserter! Может показаться удивительным то, что всего одна строка кода выполняет всю работу по токенизации входных данных, помещению их во множество, отсортированное по алфавиту, и отсечению дубликатов.

std::istream_iterator

Этот класс очень интересен в тех случаях, когда мы хотим обрабатывать большие объемы однотипных данных, получаемые из потока, чему и посвящен наш пример: мы анализируем все входные данные слово за словом и помещаем их в множество в виде экземпляров класса std::string.

Итератор std::istream_iterator принимает один шаблонный параметр с необходимым нам типом. Мы выбрали тип std::string, поскольку ожидаем, что будем работать со словами, но это могут быть, например, и числа с плавающей точкой. По сути, здесь годится любой тип, для которого можно записать cin>>var;. Конструктор принимает экземпляр класса istream. Стандартный поток ввода представляется глобальным объектом потока ввода std::cin, который вполне подходит для нашего случая.

istream_iterator it {cin};

К созданному итератору потока ввода применимы две операции. Во-первых, при разыменовании (*it) он возвращает текущий введенный символ. Поскольку мы указали, что итератор соотнесен с типом std::string с помощью шаблонного параметра, этот символ будет содержать одно слово. Во-вторых, при инкременте (++it) итератор переходит на следующее слово, к которому мы также можем получить доступ путем разыменования.