6

我今天正在解决一个问题。但我被卡住了。我知道 trie 是如何工作的，但问题是我知道如何使用静态数组和类来实现它。今天在网上冲浪时，我读到有一种方法可以使用 stl::map 实现尝试。我今天尝试了，但我仍然不知道如何在 int 上插入元素。这种结构。

Edit1：我正在尝试解决这个问题：spoj.com/problems/TAP2012D 我想知道如何使用 edit2 将单词添加到 trie 中：我知道地图是如何工作的，我只是不知道带有地图的 trie作品。我想要知道尝试的人。

这是我到目前为止所做的

const int ALPH_SIZE = 26;
using namespace std;

struct trie{
    map<char,int> M;
    int x,y;
    trie();
};

trie T[1000000];


trie::trie()
{
    x=y=0;
}
int maximo;


void addtrie(string palabra)
{
    int tam=palabra.size();
    int pos=0;
    for(int i=0;i<tam;i++)
    {
        if(T[pos].M.find(palabra[i])==T[pos].M.end())
        {
            T[pos].M[palabra[i]]=new trie();
            T[pos].M[palabra[i]]=
        }

    }

}
4

5 回答 5

8

trie 节点存储现有输出字符的映射和指示该节点是否对应于 trie 中的单词的标志。

struct Node
{   map<char, Node*> a;
    bool flag;

    Node() { flag = false; }
};

现在插入类似于您对静态数组所做的操作，不同之处在于您在此处使用地图。

void insert(Node *x, string s)
{   for(int i = 0; i < s.size(); i++)
    {   if(x->a.count(s[i]) == 0)
        /* no outgoing edge with label = s[i] so make one */
        {   x->a[ s[i] ] = new Node;
        }
        x = x->a[ s[i] ];
    }
    x->flag = true; /* new word */
}
于 2015-01-21T20:32:33.547 回答
1

在我看来，使用 unordered_map 更好。

    struct TrieNode {
        char c;
        unordered_map<char, TrieNode*>links;
        bool end;
    };

    TrieNode* insert(TrieNode* root, string word) {
        TrieNode* current  = root;

        for (auto it: word) {
           if (current->links.find(it) == current->links.end()) {
           TrieNode* node = new TrieNode(); // possible memory leak?
           node->c = it;
           node->links = {};
           node->end = false;

           current->links[it] = node;
           }

        current = current->links[it];
       }

    current->end = true;
    return root;
    };

当然，使用 new 运算符创建的 TrieNode 可能存在内存泄漏问题。也许某种树遍历（基于 DFS）以自下而上的方式访问所有节点并删除它们，可以帮助避免内存泄漏。

于 2015-11-18T15:21:55.717 回答
0

使用地图的问题是你失去了位置。除了缩小可能的键之外，拥有一个实际的字母表并没有任何好处。

一次解析一个字符会在内存中跳跃。如果字符串一次解析三个字符，那么对于给定字符串的序列加载以及在其保留在缓存中时廉价加载其邻居的机会都会有更高的局部性。

这也利用了一些后来的语言特性，其中大部分可以通过手动加载 char<256> 轻松完成。可能还有更好的方法来做到这一点。

#include <map>
#include <array>
#include <string>
#include <cstddef>
#include <cstdint>
#include <iostream>

// MAP
template<char ... Args>
class mkmap;

// Walk the tuple
template<char count, char tuple_sz, char tuple_cnt, char grab, char ... alpha>
class mkmap<count, tuple_sz, tuple_cnt, grab, alpha...> {
public:
    static constexpr void map(std::array<char, 256>& map) {
        map[grab] = count;
        mkmap<count, tuple_sz, tuple_cnt - 1, alpha...>::map(map);
    }
};

// Next tuple
template<char count, char tuple_sz, char grab, char ... alpha>
class mkmap<count, tuple_sz, 1, grab, alpha...> {
public:
    static constexpr void map(std::array<char, 256>& map) {
        map[grab] = count;;
        mkmap<count + 1, tuple_sz, tuple_sz, alpha...>::map(map);
    }
};

// End recursion
template<char count, char tuple_sz, char tuple_cnt>
class mkmap<count, tuple_sz, tuple_cnt> {
public:
    static constexpr void map(std::array<char, 256>& map) {
    }
};

template<int tuple_sz, char ... alpha>
class cvtmap {
public:
    constexpr cvtmap() : map{} {
        mkmap<1, tuple_sz, tuple_sz, alpha...>::map(map);
    }
    constexpr char operator[](char input) const {
        return map[input];
    }
    std::array<char, 256> map;
};

// UNMAP
template<char ... Args>
class mkunmap;

// Walk the tuple
template<char count, char tuple_sz, char tuple_cnt, char grab, char ... alpha>
class mkunmap<count, tuple_sz, tuple_cnt, grab, alpha...> {
public:
    static constexpr void map(std::array<std::array<char, tuple_sz>, 256>& map) {
        map[count][tuple_sz - tuple_cnt] = grab;
        mkunmap<count, tuple_sz, tuple_cnt - 1, alpha...>::map(map);
    }
};

// Next tuple
template<char count, char tuple_sz, char grab, char ... alpha>
class mkunmap<count, tuple_sz, 1, grab, alpha...> {
public:
    static constexpr void map(std::array<std::array<char, tuple_sz>, 256>& map) {
        map[count][tuple_sz - 1] = grab;;
        mkunmap<count + 1, tuple_sz, tuple_sz, alpha...>::map(map);
    }
};

// End recursion
template<char count, char tuple_sz, char tuple_cnt>
class mkunmap<count, tuple_sz, tuple_cnt> {
public:
    static constexpr void map(std::array<std::array<char, tuple_sz>, 256>& map) {
    }
};

template<int tuple_sz, char ... alpha>
class cvtunmap {
public:
    constexpr cvtunmap() : map{} {
        mkunmap<1, tuple_sz, tuple_sz, alpha...>::map(map);
    }
    constexpr std::array<char, tuple_sz> operator[](char input) const {
        return map[input];
    }
    std::array<std::array<char, tuple_sz>, 256> map;
};

template<int tuple_sz, char ... alpha>
class cvt
{
public:
    enum consts : char { SENTINAL = 0 };

    static constexpr int size() { return sizeof...(alpha) / tuple_sz + 1; }
    cvt(char c) : a{ map[c] } {
    }
    char to_char()
    {
        return unmap[a][0];
    }
    unsigned short value() const {
        return a;
    }
private:
    char a;
    static const cvtmap<tuple_sz, alpha...> map;
    static const cvtunmap<tuple_sz, alpha...> unmap;
};

template<int tuple_sz, char ... alpha>
const cvtmap<tuple_sz, alpha...> cvt<tuple_sz, alpha...>::map;

template<int tuple_sz, char ... alpha>
const cvtunmap<tuple_sz, alpha...> cvt<tuple_sz, alpha...>::unmap;

using ASCII_ignore_case = cvt <2,
    'a', 'A', 'b', 'B', 'c', 'C', 'd', 'D', 'e', 'E', 'f', 'F', 'g', 'G', 'h', 'H', 'i', 'I', 'j', 'J', 'k', 'K', 'l', 'L', 'm', 'M', 'n', 'N', 'o', 'O', 'p', 'P', 'q', 'Q', 'r', 'R', 's', 'S', 't', 'T', 'u', 'U', 'v', 'V', 'w', 'W', 'x', 'X', 'y', 'Y', 'z', 'Z'
>;

template <class alphabet>
class Node {
public:
    enum consts { SHIFT = 32 };
    static short make_key(alphabet a, alphabet b, alphabet c) {
        // max is Z (26) * 27 * 27 == 18954 which fits under SHRT_MAX (32767)
        return
            a.value() * SHIFT * SHIFT
            + b.value() * SHIFT
            + c.value();
    }
    static std::array<char, 3> to_string(short x) {
        char a = (x / (SHIFT * SHIFT)) & 0xFF;
        x -= a * SHIFT * SHIFT;
        char b = (x / SHIFT) &0xFF;
        x -= b * SHIFT;
        char c = x &0xFF;
        return { a,b,c };
    }
    Node* add(short key) {
        if (idx.contains(key)) {
            return idx[key];
        }
        Node* ret = new Node;
        idx[key] = ret;
        return ret;
    }
    static Node* sentinal() {
        static Node fixed;
        return &fixed;
    }
    void add_final(short key) {
        if (!idx.contains(key)) {
            idx[key] = sentinal();
        }
    }
    const Node* get(short key) const {
        auto it = idx.find(key);
        if (it != idx.end()) { // avoid creating nodes
            return it->second;
        }
        return 0;
    }
    bool is_final(short key) const {
        auto it = idx.find(key);
        if (it != idx.end()) { // avoid creating nodes
            return it->second == sentinal();
        }

        return false;
    }
    ~Node() = default;
private:
    std::map <short, Node*> idx;
};

template <class alphabet>
class TriTrie {
public:
    void add(std::string& str) {
        std::string::iterator i = str.begin();
        const std::string::iterator e = str.end();
        Node<alphabet>* where = &top;
        for (;;) {
            std::size_t len = e - i;
            alphabet a = alphabet::SENTINAL;
            alphabet b = alphabet::SENTINAL;
            alphabet c = alphabet::SENTINAL;
            switch (len)
            {
            default: [[likely]] {
                a = alphabet(*(i++));
                b = alphabet(*(i++));
                c = alphabet(*(i++));

                short key = Node<alphabet>::make_key(a,b,c);
                where = where->add(key);
            }
                   break;
            case 3:
                c = alphabet(*(i + 2));
                [[fallthrough]];
            case 2:
                b = alphabet(*(i + 1));
                [[fallthrough]];
            case 1:
                a = alphabet(*i);
                [[fallthrough]];
            case 0: {
                short key = Node<alphabet>::make_key(a, b, c);
                where->add_final(key);
                return;
            }
            }
        }
    }
    bool contains(std::string& str) const {
        std::string::iterator i = str.begin();
        const std::string::iterator e = str.end();
        const Node<alphabet>* where = &top;
        while (where) {
            std::size_t len = e - i;
            alphabet a = alphabet::SENTINAL;
            alphabet b = alphabet::SENTINAL;
            alphabet c = alphabet::SENTINAL;
            switch (len) {
                default: [[likely]] {
                    a = alphabet(*(i++));
                    b = alphabet(*(i++));
                    c = alphabet(*(i++));

                    short key = Node<alphabet>::make_key(a,b,c);
                    where = where->get(key);
                }
                    break;
                case 3:
                    c = alphabet(*(i + 2));
                    [[fallthrough]];
                case 2:
                    b = alphabet(*(i + 1));
                    [[fallthrough]];
                case 1:
                    a = alphabet(*i);
                    [[fallthrough]];
                case 0: {
                    short key = Node<alphabet>::make_key(a, b, c);
                    return where->is_final(key);
                }
            }
        }
        return false;
    }
private:
    Node<alphabet> top;
};

using ASCII_TriTrie = TriTrie<ASCII_ignore_case>;


int main()
{
    ASCII_TriTrie tt;

    for (std::string s : {
        "hello", "goodbye", "big", "little", "hi", "hit", "hitch", "him"
    }) {
        std::cout << s << ":" << std::endl;
        if (tt.contains(s)) {
            return -1;
        }
        tt.add(s);
        if (!tt.contains(s)) {
            return -2;
        }
    }

    return 0;
}
于 2021-10-18T02:53:16.850 回答
0

在我看来，我认为你也可以在添加元素之前加上一个检查。

    StrCheck(str); // check string is empty

    if (root == nullptr) // check root is nullptr
    {
        root = new Node<T>;
    }

void StrCheck(string str)
 {  
    if (str.empty())
    {
        throw exception("str is empty!");
    }
  }
于 2022-03-05T14:15:03.397 回答
-5

将元素插入 stl::map 的正确方法应按以下方式完成 

std::map<char,int> M;


  M.insert ( std::pair<char,int>('aaa',1) );
  M.insert ( std::pair<char,int>('bbb',2) );
于 2013-02-15T02:45:18.027 回答