Nestable Vector Class

Question

I'm working on a project where I need to be able to have a particular kind of data structure. Essentially, I need to be able to have a vector, which could store either ints as it's elements, or another vector. And then the same idea needs to apply to that second vector. I know this kind of amounts to having a container contain itself, but I was wondering if there was some way to do this.

Maybe an example will clarify. I want to be able to have a collection like this:

[[1,2], [[3,4], 5], [6, 7]]

with the idea that I could ints and vectors at "series" and at "parallel" indefinitely deep. I know this is a tough ask but is there any way this could be possible. One idea I had was that we could have a vector where Elem is a class we define that contains an int representing it's nesting depth, and a void* pointer to a heap allocated element.

I feel like there is some polymorphic magic that can be done here, but not quite sure.

See http://stackoverflow.com/questions/39454347/using-stdvariant-with-recursion-without-using-boostrecursive-wrapper — Barmar, Apr 29 '17 at 22:24
The best way to do this is with a recursive `boost::variant`, but it's not quite trivial. — Nir Friedman, Apr 29 '17 at 22:46

zett42 · Accepted Answer · 2017-04-30T00:03:54.370

How about some boost magic?

#include <vector>
#include <boost/variant.hpp>
#include <boost/variant/recursive_wrapper.hpp>

// A recursive tree structure made of std::vector.
template< typename T, class Allocator = std::allocator<T> >
struct vector_tree :
    std::vector< 
        boost::variant< T, boost::recursive_wrapper< vector_tree< T, Allocator > > >,
        Allocator >
{
    using base = std::vector< 
        boost::variant< T, boost::recursive_wrapper< vector_tree< T, Allocator > > >,
        Allocator >;

    // Forward all constructors of the base class.
    using base::base;
};

This type allows for unlimited nesting and has a very clean initialization syntax.

Usage examples

using mytree = vector_tree<int>;

// Construct a nested vector_tree with initializer list.
mytree tree{
    1,
    2,
    mytree{ 
        mytree{ 3, 4, 5 },
        6, 
    }
};
// Add more stuff.
tree.push_back( 42 );
tree.push_back( mytree{ 43, 44 } );

// Add something to a child vector_tree. 
// NOTE: boost::get() will throw a boost::bad_get exception if requested type is invalid
boost::get<mytree>( tree[ 2 ] ).push_back( 99 );

// To avoid the boost::bad_get exception, we can check if the child actually is a vector_tree:
if( mytree* pchild = boost::get<mytree>( &tree[ 2 ] ) )
{
    (*pchild)[ 1 ] = 88;
}

Live Demo on Coliru.

Explanations

The boost::recursive_wrapper is required because boost::variant normally requires a complete type, but at the point of declaration vector_tree is still incomplete.

boost::recursive_wrapper actually is nothing magic. It's just a wrapper around a pointer! As we know, a pointer can be declared for an incomplete type without issues. This wrapper class just hides the fact that a pointer is used by taking care of allocation, deallocation and providing value semantics. It has special support by boost::variant that makes the wrapper completely transparent, so the variant can be used as if there is no wrapper class at all.

NOTE: Since C++17 there is std::variant but AFAIK there isn't a boost::recursive_wrapper equivalent for it that can handle nesting transparently.

score 1 · Answer 2 · answered Apr 29 '17 at 22:27

If you want to use polymorphism, you can define a base struct, and from it derive a struct containing a std::vector<*base>, and derive another containing an int. Your main function would contain an instance of the first derived class, which could contain pointers to itself, or the second derived class. This would allow for vectors within vectors containing int's.

To store information such as the depth, you could have an int depth in your base struct, where the constructor would pass the current depth and add one.

score 1 · Answer 3 · answered Apr 29 '17 at 22:33

Here is what you're looking for:

template <typename T>
class NestableVector {
private:
    struct element {
        virtual element* copy() const = 0;
    };
    struct vector_element : public element {
        NestableVector value;
        element* copy() const;
    };
    struct normal_element : public element {
        T value;
        element* copy() const;
    };
    class copy_ptr { // specialized smart pointer that copies underlying object when copied
        private:
            element* ptr;
        public:
            copy_ptr(element*);
            copy_ptr(const copy_ptr&); // copies *ptr into new object
            void operator=(const copy_ptr&); // same as above
    };
    std::vector<copy_ptr> v; // underlying vector
public: 
    // interface to v here
};

You define a special element type that has two subclasses, vector_element and normal_element. Both these overload the base class's copy() function, which is used in the new smart pointer class copy_ptr, which copies the element it itself points to when copied. We use the smart pointer so that when stuff is copied around in v, the elements themselves are copied, not the pointers to them.

Nestable Vector Class

3 Answers3

Usage examples

Explanations