C++17 STL Стандартная библиотека шаблонов

3. Код для добавления новых последовательностей элементов выглядит довольно просто. Пользователь предоставляет пару итераторов (начальный и конечный), и мы проходим по ним рекурсивно. Если он ввел данные {1, 2, 3}, то мы ищем значение 1 в поддереве, а затем ищем значение 2 в следующем поддереве, чтобы получить поддерево для значения 3. Какое-то из этих поддеревьев, ранее не существовавшее, будет добавлено с помощью оператора [] контейнера std::map.

public:

  template

  void insert(It it, It end_it) {

    if (it == end_it) { return; }

    tries[*it].insert(next(it), end_it);

  }

4. Для удобства определим также отдельные функции, они дают пользователю возможность получить контейнер элементов, которые будут автоматически опрошены на предмет итераторов:

  template

  void insert(const C &container) {

    insert(begin(container), end(container));

  }

5. Чтобы позволить пользователю написать конструкцию my_trie.insert({"a", "b", "c"});, мы должны немного помочь компилятору вывести все типы из данной строки, поэтому добавляем функцию, которая перегружает интерфейс insert параметром типа initializer_list:

  void insert(const initializer_list &il) {

    insert(begin(il), end(il));

  }

6. Мы также хотим видеть содержимое дерева, поэтому нужна функция print. Для вывода содержимого дерева на экран можно выполнить поиск в глубину. На пути от корневого узла к первому листу мы записываем все элементы с полезной нагрузкой, которые мы уже встречали. Таким образом, мы получим полную последовательность, как только достигнем листа, и вывести ее на экран будет нетрудно. Мы видим, что достигли листа, когда функция tries.empty() возвращает значение true. После рекурсивного вызова функции print мы снова выталкиваем последний элемент с полезной нагрузкой.

  void print(vector &v) const {

    if (tries.empty()) {

      copy(begin(v), end(v), ostream

          _iterator{cout, " "});

      cout << '\n';

    }

    for (const auto &p : tries) {

      v.push_back(p.first);

      p.second.print(v);

      v.pop_back();

    }

  }

7. Рекурсивная функция print передает ссылку на выводимый на экран список элементов, но пользователь должен вызывать ее без всяких параметров. Поэтому определяем функцию print без параметров, в которой создается вспомогательный объект списка:

  void print() const {

    vector v;

    print(v);

  }

8. Теперь, когда мы научились создавать деревья и выводить их на экран, может понадобиться выполнить поиск по поддеревьям. Идея заключается в следующем: если дерево содержит последовательности наподобие {a,b,c} {a,b,d,e} и мы передаем ему последовательность {a,b} для поиска, то поиск вернет поддерево, которое содержит части {c} и {d, e}. При обнаружении поддерева возвращаем ссылку const на нее. Существует вероятность того, что такого поддерева не существует, если дерево не содержит искомой последовательности. В подобных случаях все равно нужно что-то вернуть. Здесь пригодится функция std::optional, поскольку можно вернуть пустой необязательный объект при отсутствии совпадения.

  template

  optional>

  subtrie(It it, It end_it) const {

    if (it == end_it) { return ref(*this); }

    auto found (tries.find(*it));

    if (found == end(tries)) { return {}; }

    return found->second.subtrie(next(it), end_it);

  }

9. Аналогично методу insert предоставляем версию метода subtrie с одним параметром, которая автоматически принимает итераторы из входного контейнера:

  template

  auto subtrie(const C &c) {

    return subtrie(begin(c), end(c));

  }

};

10. На этом все. Воспользуемся нашим новым классом trie в функции main, создав экземпляр класса trie, работающего с объектами класса std::string, и заполнив его каким-нибудь содержимым:

int main()

{

  trie t;

  t.insert({"hi", "how", "are", "you"});

  t.insert({"hi", "i", "am", "great", "thanks"});

  t.insert({"what", "are", "you", "doing"});

  t.insert({"i", "am", "watching", "a", "movie"});

11. Сначала выведем на экран все дерево:

  cout << "recorded sentences:\n";

  t.print();