Search code examples
c++stlhashtableunordered-maptrie

Is it advised against to store a large STL object into std::unordered_map as value?

For example, consider the following trie implementation. 

struct Trie: unordered_map<char, pair<bool, Trie> >

Should a pointer to the struct Trie be stored instead?

struct Trie: unordered_map<char, pair<bool, Trie *> >

Since a struct Trie object can get quite large, will the first implementation be less efficient as the trie grows large?

Here, managing the internal memory alloc & dealloc of the Trie shouldn't be too much of a hassle, so not considering the trouble of manually new / delete, which implementation should be preferred?

Solution

    1. Since you apparently have enough of C++11 available to use std::unordered_map, you should strongly avoid owning raw pointers. Instead of pair<bool, Trie*>, use pair<bool, unique_ptr<Trie>>.

    2. You simply cannot use the first approach, as std::pair (and all standard library containers) requires its template arguments to be complete types, which is not true in your case - Trie is not completely defined yet.

    3. It's generally a bad idea to publically inherit from standard library containers; they are not designed for it and have no virtual interface. Prefer composition.