Re: Values vs. references for deep, nested structures.

[gratuitous quote below so this post doesn't get rejected]

On Aug 6, 10:47 am, Edward Rosten <Edward.Ros...@gmail.com> wrote:


I tested the below on an experimental implementation with move
semantics. It allowed the incomplete vector type. It experiments
with a node containing a MoveOnly type which has private copy
constructor and copy assignment. This guarantees at compile time that
the payload, and thus the node and its children are not being copied,
not even once, even though it is being generated from a recursive
factory function.

#include <vector>
#include <iostream>

template <class T>
class node
{
public:
    typedef T value_type;
    typedef std::vector<node> C;
    typedef typename C::const_iterator iterator;
private:
    value_type data_;
    C children_;
public:
    node()
        : data_()
    {}
    explicit node(const value_type& v)
        : data_(v)
    {}
    explicit node(value_type&& v)
        : data_(std::move(v))
    {}

    node(node&& n)
        : data_(std::move(n.data_)),
          children_(std::move(n.children_))
    {}

    node& operator=(node&& n)
    {
        data_ = std::move(n.data_);
        children_ = std::move(n.children_);
        return *this;
    }

    void push_back(const node& n) {children_.push_back(n);}
    void push_back(node&& n) {children_.push_back(std::move(n));}

    const value_type& get_value() const {return data_;}
    const C& get_children() const {return children_;}
};

template <class T>
std::ostream&
operator<<(std::ostream& os, const node<T>& n)
{
    typedef typename node<T>::C C;
    typedef typename node<T>::iterator I;
    os << '[' << n.get_value() << ']';
    const C& c = n.get_children();
    switch (c.size())
    {
    case 0:
        return os << "{}";
    case 1:
        return os << '{' << c.front() << '}';
    }
    os << '{' << c.front();
    for (I i = c.begin() + 1; i != c.end(); ++i)
        os << ", " << *i;
    return os << '}';
}

class MoveOnly
{
    int data_;

    MoveOnly(const MoveOnly&);
    MoveOnly& operator=(const MoveOnly&);
public:
    explicit MoveOnly(int data = 0)
        : data_(data)
    {
        assert(data >= 0);
    }
    ~MoveOnly()
    {
        assert(data_ >= 0);
        data_ = -1;
    }

    MoveOnly(MoveOnly&& m)
        : data_(m.data_)
    {
        m.data_ = 0;
    }

    MoveOnly& operator=(MoveOnly&& m)
    {
        data_ = m.data_;
        m.data_ = 0;
    }

    int get() const {return data_;}
};

std::ostream&
operator<<(std::ostream& os, const MoveOnly& m)
{
    return os << m.get();
}

node<MoveOnly>
get(unsigned depth)
{
    switch (depth)
    {
    case 0:
        return node<MoveOnly>();
    case 1:
        return node<MoveOnly>(MoveOnly(1));
    }
    node<MoveOnly> c((MoveOnly(depth)));
    c.push_back(get(depth-1));
    c.push_back(get(depth-1));
    return c;
}

int main()
{
    node<MoveOnly> c = get(4);
    std::cout << c << '\n';
}

[4]{[3]{[2]{[1]{}, [1]{}}, [2]{[1]{}, [1]{}}}, [3]{[2]{[1]{}, [1]{}},
[2]{[1]{}, [1]{}}}}

hth.

-Howard

--
      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated. First time posters: Do this! ]