I'm getting a compiler error, here is a snippet

for(unsigned i = 0; i < words.size(); ++i){
const std::string& word = words[0];
char firstVal = word[0];
std::pair<std::set<TrieNode>::iterator,bool> ret = trie.insert(TrieNode(firstVal));
TrieNode& n = *ret.first; //line A
//ret.first->insert(word.substr(1)); //line b
}


The error is this:

error: invalid initialization of reference of type 'TrieNode&' from expression of type 'const TrieNode'


So I need to declare TrieNode& n , to be a reference to a constant is what the error message is telling me. But why? My iterator is not constant_iterator. I should be able to use the iterator returned to call a non-const-corrected member function, such as a defined insert. Anyone shed some light?

Oh I see, so this seems awkward. How could I achieve something like this?

struct Node{
char data;
Node(char d) : data(d){}
std::set<Node> childrens;
void insert(const std::string& word) {
//for i = 0 to words.size
//...
//childrens.insert( word )
//...
}
bool operator ==(const Node& n){ return n.data == data; }
//operator <(...){...}
};
struct Tree{
std::set<Node> heads;
void insert( std::vector<string>& words){
for(int i = 0; i < words.size(); ++i){
const std::string& word = words[0];
std::pair<std::set<Node>::iterator, bool> ret = words.insert( Node(word[0]) );
ret.first->insert( words.substr(1) ); //line b
}
}
}


I do not particularly change the ordering, but I want to call a non-const member function in line b, which would populate its child.

Objects in a set are mean't to be immutable. As was said, if you could change them, it could ruin the sort order of the set.

However, there's a "could" in that sentence right...? The deal is that your set ordering is determined by your less-than operator for the TrieNode class. Typically this operator would consider all the variables of the class. One option however is to have additional variables that are not considered within the less-than operator, and these are declared as mutable and can thus be changed from a const member functions. Then since they don't take part in the less-than operator, the set ordering in unaffected.
There are certain circumstances where this makes sense. However, it often means that you would be better off splitting the data type up into two types and using a map instead.

Can you perhaps show the definition of the TrieNode class, in particular the member variables, operator less-than, and the non-const function you are wanting to call, please?

This is just for practice, and its incomplete data structure for a Trie, but here it is.

#include <iostream>
#include <vector>
#include <string>
#include <set>
using namespace std;

struct TrieNode{
public:
typedef char T;
typedef std::set<TrieNode> TrieNodeSet;
private:
T data;
TrieNodeSet childrens;
public:
TrieNode(const T& data = T()): data(data){}
void insert(const std::string& letters)const{
for(unsigned i = 0; i < letters.size(); ++i){
char firstVal = letters[0];
std::pair<std::set<TrieNode>::iterator,bool> ret = childrens.insert(TrieNode(firstVal));
ret.first->insert(letters.substr(1));
}
}
bool operator<(const TrieNode& n)const{ return data < n.data; }
bool operator==(const TrieNode& n)const{ return data == n.data;}
};

class TrieTree{
private:
std::set<TrieNode> trie;
public:
TrieTree(){}
TrieTree(const std::vector<std::string>& words){
_init(words);
}
private:
void _init(const std::vector<std::string>& words){
for(unsigned i = 0; i < words.size(); ++i){
const std::string& word = words[0];
char firstVal = word[0];
std::pair<std::set<TrieNode>::iterator,bool> ret = trie.insert(TrieNode(firstVal));
//ret.first->insert(word.substr(1));
}
}
};

int main() {

return 0;
}



EDIT: I guess I can make childrens mutable or change the data structure to sorted vector, or use map...
of course it doesn't compile because of the previous error. I learned something new today!

Right now I have just declared childrens as mutable, but do you guys think its a valid excuse to do so? I mean, the ordering isn't being changed, but I need the set functionalities and ordering. Its working pretty well, but I don't know if its a good idea. Any thoughts? Right now here is what I have:
[source lang="C++"]
template<typename T>
struct TrieNode{
public:
typedef typename std::set<TrieNode<T> > TrieNodeSet;
typedef typename TrieNodeSet::iterator Iterator;
typedef typename TrieNodeSet::const_iterator ConstIterator;
typedef std::pair<Iterator,bool> ReturnIterator;
private:
T data;
mutable TrieNodeSet childrens;
public:
TrieNode(const T& data = T()): data(data){}
void print()const{
cout << "(" << data << " ";
for(Iterator itr = childrens.begin(); itr != childrens.end(); ++itr){
itr->print();
}
cout << ") ";
}
const T& value()const{ return data; }
template<typename InputType>
std::vector<InputType> match(const InputType& letters){
ConstIterator next = childrens.find(letters[0]);
std::vector<InputType> matches;
/* yet to be finished implemented */
return matches;
}
bool hasChildrens()const{ return !childrens.empty();}
void insert(const std::string& letters)const{
for(unsigned i = 0; i < letters.size(); ++i){
const char firstVal = letters[0];
ReturnIterator ret = childrens.insert(TrieNode(firstVal));
ret.first->insert(letters.substr(1));
}
}
bool operator<(const TrieNode& n)const{ return data < n.data; }
bool operator==(const TrieNode& n)const{ return data == n.data;}
};
template<typename T>
class TrieTree{
private:
typedef typename TrieNode<T>::TrieNodeSet TrieSet;
typedef typename TrieNode<T>::Iterator Iterator;
typedef typename TrieNode<T>::ConstIterator ConstIterator;
typedef typename TrieNode<T>::ReturnIterator ReturnIterator;
private:
TrieSet trie;
public:
TrieTree(){}
template<typename Iterator>
TrieTree(Iterator begin, Iterator end){
_init(begin,end);
}
template<typename InputType>
std::vector< InputType > match(const InputType& letters){
ConstIterator itr = trie.find(letters[0]);
std::vector<InputType> matches;
if(itr != trie.end()){
matches = trie.match(letters.substr(1));
}
return matches;
}
void print()const{
for(ConstIterator itr = trie.begin(); itr != trie.end(); ++itr){
itr->print();
}
}
private:
template<typename Iterator>
void _init(Iterator begin, Iterator end){
while(begin != end){
const std::string& word = *begin;
ReturnIterator ret = trie.insert(TrieNode<T>(word[0]));
ret.first->insert(word.substr(1));
++begin;
}
}
};

int main() {
string words[4] = { "apple", "ape", "basket", "ball" };
TrieTree<char> tree(words, words + 2);

tree.print();

return 0;
}
[/source]

[font="arial, verdana, tahoma, sans-serif"]A level of a trie maps characters to sub-tries. Encoding that as a `std::map<char, TrieNode<T> >' makes a lot more sense than encoding it as a set. The awkwardness that you have to go through to get your std::set to do what you want is proof of this. `mutable' is just a hack here and you shouldn't use it.[/font]
[font="arial, verdana, tahoma, sans-serif"] [/font]
[font="arial, verdana, tahoma, sans-serif"]Let me try to say it in a different way: You have a std::set of objects that have two parts, where the first part is the only one that matters for the order, and this is the part that we'll use to search for the objects. The second part of the objects actually changes value. std::map is your friend.[/font]
[font="arial, verdana, tahoma, sans-serif"] [/font]
[font="arial, verdana, tahoma, sans-serif"]One more thing: I have only ever needed to use a trie when the obvious alternative (`std::map<std::string, T>') wasn't fast enough. In those cases, the mapping from character to sub-trie had to be really fast, so I either used an array of T indexed by the character (child[first_character], or at most I used an intermediate array that described the character set that I expect to find and effectively compacted the alphabet in use (child[alphabet_map[first_character]]). Using a set or map would have been way too slow.[/font]
[font="arial, verdana, tahoma, sans-serif"] [/font]
[font="arial, verdana, tahoma, sans-serif"] [/font]

Ok I'll refractor it. And as to your second point, I agree. Originally thats what I was thinking but I really don't need this for anything. In fact if I did needed to I would have probably did as you said. But this is all just for practice since I've been off C++ lately. Thanks.