Trie
(Mylib/String/trie.cpp)

• View this file on GitHub
• Last update: 2021-04-23 23:44:44+09:00

Operations

Requirements

Notes

Problems

• C - たんごたくさん
• Codeforces Round #542 (Div. 1) C. Morse Code
• dna - DNAの合成 (DNA Synthesizer)
• E - 宝くじ

References

Code

#pragma once
#include <map>
#include <string>
#include <vector>

namespace haar_lib {
  template <typename T>
  class trie_node {
    std::map<char, trie_node*> children_;
    T val_;

  public:
    trie_node() {}
    trie_node(T val) : val_(val) {}

    const T& value() const { return val_; }
    T& value() { return val_; }

    trie_node* insert(char c, const T& v) {
      if (children_.find(c) != children_.end()) {
        children_[c]->val_ = v;
      } else {
        children_[c] = new trie_node<T>(v);
      }

      return children_[c];
    }

    template <typename Iter>
    trie_node* insert(Iter first, Iter last, const T& v) {
      if (first == last) {
        val_ = v;
        return this;
      } else {
        const auto c = *first;
        if (children_.find(c) == children_.end()) {
          children_[c] = new trie_node(T());
        }

        return children_[c]->insert(first + 1, last, v);
      }
    }

    trie_node* find(char c) {
      if (children_.find(c) != children_.end())
        return children_[c];
      else
        return nullptr;
    }
  };

  template <typename T>
  struct trie {
    using node = trie_node<T>;

  private:
    node* root_;

  public:
    trie() : root_(new node(T())) {}

    node* root() const { return root; }

    template <typename Iter>
    node* insert(Iter first, Iter last, const T& v) {
      return root->insert(first, last, v);
    }
  };
}  // namespace haar_lib

#line 2 "Mylib/String/trie.cpp"
#include <map>
#include <string>
#include <vector>

namespace haar_lib {
  template <typename T>
  class trie_node {
    std::map<char, trie_node*> children_;
    T val_;

  public:
    trie_node() {}
    trie_node(T val) : val_(val) {}

    const T& value() const { return val_; }
    T& value() { return val_; }

    trie_node* insert(char c, const T& v) {
      if (children_.find(c) != children_.end()) {
        children_[c]->val_ = v;
      } else {
        children_[c] = new trie_node<T>(v);
      }

      return children_[c];
    }

    template <typename Iter>
    trie_node* insert(Iter first, Iter last, const T& v) {
      if (first == last) {
        val_ = v;
        return this;
      } else {
        const auto c = *first;
        if (children_.find(c) == children_.end()) {
          children_[c] = new trie_node(T());
        }

        return children_[c]->insert(first + 1, last, v);
      }
    }

    trie_node* find(char c) {
      if (children_.find(c) != children_.end())
        return children_[c];
      else
        return nullptr;
    }
  };

  template <typename T>
  struct trie {
    using node = trie_node<T>;

  private:
    node* root_;

  public:
    trie() : root_(new node(T())) {}

    node* root() const { return root; }

    template <typename Iter>
    node* insert(Iter first, Iter last, const T& v) {
      return root->insert(first, last, v);
    }
  };
}  // namespace haar_lib

Back to top page