What is the problem with fill() here ? I used normal for loop for assigning NULL and it worked , with fill() it was giving error

useraQX61 0
Viewed 28

The code below is a Trie implementation in C++. Kindly checkout what is the problem in using fill(). And if any suggestions improving my implementation are welcome

Commented fill() in the TrieNode constructor function function is giving compile time error as mentioned in the snippet . Why this is behaving wierd with fill , standard for loop is doing the same job as expected.

 class TrieNode {
    public : 
    vector<TrieNode *>vec;
    bool end ;
    TrieNode(){
        vec.resize(26); end = false; 
        // fill(vec.begin() , vec.end() , NULL); // did not worked
        for(int i = 0; i<vec.size(); i++){
            vec[i] = NULL;
        }
    }
    bool exist(char x){
        return vec[x - 'a']!=NULL;
    }
};

class Trie{
    public :
    TrieNode * head ;

       Trie(){
        head = new TrieNode();
       }
       void insert(string st){
          TrieNode * curr = head;
          for(int i = 0; i<st.length() ; i++){
            if(curr->exist(st[i])){
                curr = curr->vec[st[i]-'a'];
            }
            else{
                curr->vec[st[i]-'a'] = new TrieNode();
                curr = curr->vec[st[i]-'a'];
            }
          }

          curr->end = 1;
       }

       bool exist(string st){
          TrieNode * curr = head;
          for(int i = 0; i<st.length(); i++){
            if(curr->exist(st[i])){
                curr = curr->vec[st[i] - 'a'];
            }
            else{
                return false;
            }
          }
          return curr->end;
       }
};

 class Solution{
   public : 
     vector<vector<int> >palindromePairs(vi& vec){
          Trie tree;

          tree.insert("boys");
          tree.insert("boysx");
          cout << tree.exist("man");
           cout << tree.exist("boys") << ' ' << tree.exist("boysd");


           return {{2,3} , {1 , 2}};
     }   
};

error snippet

trie fill c++
1 Answers

First, we convert your code tor a MRE.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

class TrieNode {
public:
    std::vector<TrieNode*>vec;
    bool end;
    TrieNode() {
        vec.resize(26); end = false;
        std::fill(vec.begin() , vec.end(), NULL); // did not worked
    }
    bool exist(char x) {
        return vec[x - 'a'] != NULL;
    }
};

class Trie {
public:
    TrieNode* head;

    Trie() {
        head = new TrieNode();
    }
    void insert(std::string st) {
        TrieNode* curr = head;
        for (size_t i = 0; i < st.length(); i++) {
            if (curr->exist(st[i])) {
                curr = curr->vec[st[i] - 'a'];
            }
            else {
                curr->vec[st[i] - 'a'] = new TrieNode();
                curr = curr->vec[st[i] - 'a'];
            }
        }

        curr->end = 1;
    }

    bool exist(std::string st) {
        TrieNode* curr = head;
        for (size_t i = 0; i < st.length(); i++) {
            if (curr->exist(st[i])) {
                curr = curr->vec[st[i] - 'a'];
            }
            else {
                return false;
            }
        }
        return curr->end;
    }
};

int main() {
    
    Trie trie;

    trie.insert("boys");
    trie.insert("boysx");
    std::cout << trie.exist("man");
    std::cout << trie.exist("boys") << ' ' << trie.exist("boysd");
};

Then, we compile it and get the following messages:

enter image description here

The problem is mentioned there.

You want to fill a std::vector of TrieNode* with NULL.

So, again, std::fill expects in your case a TrieNode*. So, give it one. You can cast your 0 to such a type. A static_cast will work: std::fill(vec.begin() , vec.end(), static_cast<TrieNode*>(NULL));, but to be compliant to the followers of the UB religion, you must use a reinterpret_cast:

std::fill(vec.begin() , vec.end(), reinterpret_cast<TrieNode*>(NULL));

But C++ offers you the redommended solution. The nullptr. By definition the nullptr is compatible to other pointer, also the TrieNode*.

So, please do not use NULL for pointers in C++. Use nullptr instead:

std::fill(vec.begin() , vec.end(), nullptr);
Armin Montigny0
Related