1

I am trying to solve a Trie problem, for which I create a TrieNode class as below:

class TrieNode {
    public:
    bool isWord;
    TrieNode* children[26];
    TrieNode() {
        isWord=false;
        memset(children, NULL, sizeof(children));    //results in warning
    };
};

This results in a warning:

warning: passing NULL to non-pointer argument 2 of 'void* memset(void*, int, size_t)' [-Wconversion-null]

Replacing it with nullptr results in a compile time error:

error: cannot convert 'std::nullptr_t' to 'int' for argument '2' to 'void* memset(void*, int, size_t)'

So my question is, how do I initialize all the values in children to NULL/nullptr? I tried a few options such as children[26]={ nullptr };, but those all resulted in runtime errors (worked fine only with memset(children, NULL, sizeof(children));).

Eventually, while building the trie, I wish to have the following logic:

if(!curr->children[index]) {
    curr->children[index]=new TrieNode();
}
curr=curr->children[index];
Someone
  • 611
  • 4
  • 13
  • `children[26]={ nullptr };` sets the 27th element, but there are only 26 elements! – MSalters Oct 27 '21 at 15:20
  • Also, things would be a lot easier if you used `std::unique_ptr`. It has a default constructor. You could even use `std::map` but that's a bit cheating (since the map itself uses a red-black tree) – MSalters Oct 27 '21 at 15:22
  • @MSalters Simpler? No, though the seeming safety-net is often appreciated. The owner should really have a custom dtor linearizing the trie and deleting in a loop, without any recursion. Unless a very limited depth is actually guaranteed. – Deduplicator Oct 27 '21 at 16:11

3 Answers3

3

You might do:

class TrieNode
{
public:
    bool isWord = false;
    TrieNode* children[26]{};

    TrieNode() = default;
};
Jarod42
  • 203,559
  • 14
  • 181
  • 302
  • Simplifying even more: `struct TrieNode { bool isWord {}; TrieNode* children[26]{}; };` Or considering it is value-initialized, one could also remove the in-class initializers... – Deduplicator Oct 27 '21 at 16:04
  • @Deduplicator: That simplification changes also the "semantic" though, as aggregate initialization can occurs... – Jarod42 Oct 27 '21 at 16:16
  • Considering how it seems to be used, that doesn't seem to matter. Still, I should have thought of it... – Deduplicator Oct 27 '21 at 16:49
  • @Jarod42, could you please explain it? I don't follow what `TrieNode() = default;` does. If it value initializes the elements, then why do we need to set `isWord` to `false` explicitly? If it doesn't, then why don't we have to set each element of `children` to `nullptr`? – Someone Mar 21 '22 at 23:54
  • @Someone: `children` defaults to `{}`. Since that has less than 26 elements (in fact, zero), the "remaining" 26 elements are set to `nullptr`. – MSalters Mar 22 '22 at 09:39
  • @Someone: [Default constructor](https://en.cppreference.com/w/cpp/language/default_constructor) `TrieNode() = default;` will [default construct](https://en.cppreference.com/w/cpp/language/default_initialization) their members, and not do [value initialization](https://en.cppreference.com/w/cpp/language/value_initialization). so build-in types such as `bool` or array of pointer need initialization. `TrieNode* children[26]{}` set each pointer to `nullptr`. – Jarod42 Mar 22 '22 at 10:26
1

The easiest C++ option is std::fill(std::begin(array), std::end(array), nullptr).

Jarod42
  • 203,559
  • 14
  • 181
  • 302
MSalters
  • 173,980
  • 10
  • 155
  • 350
  • Ah, I had tried this one, but I used `NULL` instead of `nullptr` and it result in compile time error. – Someone Oct 27 '21 at 15:25
  • `NULL` is a MACRO which might be `0` (so deduced as `int`) or `((void*)0)` (deduced as `void*`) which are problematic for assignment. – Jarod42 Mar 22 '22 at 09:13
  • @Jarod42: Incorrect, `void*` is not a valid type. `NULL` could be `nullptr` - deduced as `nullptr_t` - in which case it would have worked, but from the failure we can deduce that `NULL` was defined on that compiler as integral zero. – MSalters Mar 22 '22 at 09:35
0

One of the way to bypass the problem is passing 0 in place of NULL, since second parameter suppose to be a integer as per function prototype.

memset(children, 0, sizeof(children));

Refer to this in case confusion with 0 vs NULL: What is the difference between NULL, '\0' and 0?

Deepankar Chaudhary
  • 11
  • 1