How to create a tree using boost multi index container

Question

I'm trying to create a tree. My very first requirement is that the objects within a tree level are ordered by its insertion order.

As a first attempt I used stl vector class:

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

class Node;
typedef std::vector<Node> NodeList;

class Node
{
public:
    Node(const std::string& name, int val=0): name_(name), value_(val), list_() {}
    Node(const Node& nd): name_(nd.name_), value_(nd.value_), list_(nd.list_) {}
    Node& operator=(const Node& nd)
    {
        name_ = nd.name_;
        value_ = nd.value_;
        list_ = nd.list_;
        return *this;
    }
    const std::string& name(void) const {return name_;}
    NodeList& list(void) {return list_;}
    const NodeList& list(void) const {return list_;}
    int value(void) const {return value_;}
    void value(int val) {value_ = val;}
private:
    std::string name_;
    int value_;
    NodeList list_;
};

std::ostream& operator<<(std::ostream& os, const Node& nd)
{
    os << nd.name() << "=\"" << nd.value() << "\"";
    return os;
}

std::ostream& operator<<(std::ostream& os, const NodeList& ndlst)
{
    for(NodeList::const_iterator it = ndlst.begin(); it < ndlst.end(); it++)
    {
        os << ' ' << *it;
    }
    return os;
}

int main()
{
    std::cout << "Creating a little tree..." << std::endl;
    Node a("ROOT", 1);
    a.list().push_back(Node("LEVEL1_1", 21));
    a.list().push_back(Node("LEVEL1_2", 22));
    a.list().push_back(Node("LEVEL1_3", 23));
    a.list().push_back(Node("LEVEL1_4", 24));
    a.list().at(2).list().push_back(Node("LEVEL2_1", 231));
    std::cout << "Done. Now let's see some values." << std::endl;
    std::cout << "root: " << a.value() << ", root->node2: "
              << a.list().at(1).value()
              << ", root->node3->node1: "
              << a.list().at(2).list().at(0).value()
              << std::endl;
    std::cout << "Ok, now let's use our '<<' operators." << std::endl;
    std::cout << a << std::endl;
    std::cout << a.list() << std::endl;
    return 0;
}

This little program compiles OK and executes as expected.

As a step further, I would like to add the capability to access objects in a tree level by its name, so I tryed using boost multi index so I modified the Node class as follows:

class Node;
struct Name{};


typedef boost::multi_index::multi_index_container<
    Node,
    boost::multi_index::indexed_by<
        boost::multi_index::random_access<>,
        boost::multi_index::hashed_non_unique<
            boost::multi_index::tag<Name>,
            boost::multi_index::const_mem_fun<Node, const std::string&, &Node::name>
        >
    >
> NodeList;


class Node
{
public:
    Node(const std::string& name, int val=0): name_(name), value_(val), list_() {}
    Node(const Node& nd): name_(nd.name_), value_(nd.value_), list_(nd.list_) {}
    Node& operator=(const Node& nd)
    {
        name_ = nd.name_;
        value_ = nd.value_;
        list_ = nd.list_;
        return *this;
    }
    const std::string& name(void) const {return name_;}
    int value(void) const {return value_;}
    void value(int val) {value_ = val;}
    NodeList& list(void) {return list_;}
    const NodeList& list(void) const {return list_;}
private:
    std::string name_;
    int value_;
    NodeList list_;
};

But it does not compile at all. Using gnu g++ version 4.6.1 the very first error is

tree.cpp:19:65: error: incomplete type 'Node' used in nested name specifier

Can someone help me solve this mutual dependence?

Thank you very much.

Best regards

Thanks to James Hopkin, I have the program partially working:

#include <boost/multi_index_container.hpp>
#include <boost/multi_index/random_access_index.hpp>
#include <boost/multi_index/hashed_index.hpp>
#include <boost/multi_index/identity.hpp>
#include <boost/multi_index/global_fun.hpp>
#include <iostream>
#include <string>

class Node;
struct Name{};
const std::string& getNodeName(const Node& nd);


typedef boost::multi_index::multi_index_container<
    Node,
    boost::multi_index::indexed_by<
        boost::multi_index::random_access<>,
        boost::multi_index::hashed_non_unique<
            boost::multi_index::tag<Name>,
            boost::multi_index::global_fun<const Node&, const std::string&, &getNodeName>
        >
    >
> NodeList;


class Node
{
public:
    Node(const std::string& name, int val=0): name_(name), value_(val), list_(new NodeList) {}
    Node(const Node& nd): name_(nd.name_), value_(nd.value_), list_(new NodeList(*nd.list_)) {}
    virtual ~Node() {delete list_;}
    Node& operator=(const Node& nd)
    {
        name_ = nd.name_;
        value_ = nd.value_;
        *list_ = *nd.list_;
        return *this;
    }
    const std::string& name(void) const {return name_;}
    int value(void) const {return value_;}
    void value(int val) {value_ = val;}
    NodeList& list(void) {return *list_;}
    const NodeList& list(void) const {return *list_;}
    friend const std::string& getNodeName(const Node& nd);
private:
    std::string name_;
    int value_;
    NodeList* list_;
};



const std::string& getNodeName(const Node& nd)
{
    return nd.name_;
}



std::ostream& operator<<(std::ostream& os, const Node& nd)
{
    os << nd.name() << "=\"" << nd.value() << "\"";
    return os;
}



std::ostream& operator<<(std::ostream& os, const NodeList& ndlst)
{
    for(NodeList::const_iterator it = ndlst.begin(); it < ndlst.end(); it++)
    {
        const Node& nd = *it;
        os << ' ' << nd;
    }
    return os;
}



int main()
{
    std::cout << "Creating a little tree..." << std::endl;
    Node a("ROOT", 1);
    a.list().push_back(Node("LEVEL1_1", 21));
    a.list().push_back(Node("LEVEL1_2", 22));
    a.list().push_back(Node("LEVEL1_3", 23));
    a.list().push_back(Node("LEVEL1_4", 24));
    // a.list().at(2).list().push_back(Node("LEVEL2_1", 231)); // First call to "at()" returns a read-only iterador so I can't append elements to its pointed object.
    std::cout << "Done. Now let's see some values." << std::endl;
    std::cout << "root: " << a.value() << ", root->node2: "
              << a.list().at(1).value() << std::endl;
             /* << ", root->node3->node1: " << a.list().at(2).list().at(0).value()
              << std::endl; */
    std::cout << "Ok, now let's use our '<<' operators." << std::endl;
    std::cout << a << std::endl;
    std::cout << a.list() << std::endl;
    return 0;
}

Now I must work in the replace/modify methods in order to add elements to the objects retrieved by multi-index itrerators.

Thank you very much.

Answer 1

It looks like the use of Node::name in the typedef is causing that error. Maybe you could create a non-member function to access a Node's name and use that instead.

Answer 2

Have you taken a look at Boost.PropertyTree?