array_view alternative for maps, sets, etc

Question

Let's assume I have some class hierarchy that has a couple of virtual functions returning a container reference:

#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>

class Interface {
public:
    virtual const std::vector<int>& getArray() const = 0;
    virtual const std::set<int>& getSet() const = 0;
    virtual const std::map<int, int>& getMap() const = 0;
};

class SubclassA : public Interface {
public:
    const std::vector<int>& getArray() const override { return _vector; }
    const std::set<int>& getSet() const override { return _set; }
    const std::map<int, int>& getMap() const override { return _map; }

private:
    std::vector<int> _vector;
    std::set<int> _set;
    std::map<int, int> _map;
};

At the moment, it is only possible to actually return a vector, set, or map in any subclass of the Interface class. However, for the vector part, I could use, e.g., a gsl::array_view to soften this restriction:

class Interface {
public:
    virtual gsl::array_view<const int> getArray() const = 0;
    virtual const std::set<int>& getSet() const = 0;
    virtual const std::map<int, int>& getMap() const = 0;
};

class SubclassA : public Interface {
public:
    gsl::array_view<const int> getArray() const override { return _vector; }
    const std::set<int>& getSet() const override { return _set; }
    const std::map<int, int>& getMap() const override { return _map; }

private:
    std::vector<int> _vector;
    std::set<int> _set;
    std::map<int, int> _map;
};

class SubclassB : public Interface {
public:
   gsl::array_view<const int> getArray() const override { return _array; }
//    const std::set<int>& getSet() const override { return _set; }
//    const std::map<int, int>& getMap() const { return _map; }

private:
    std::array<int, 3> _array;
    std::unordered_set<int> _set;
    std::unordered_map<int, int> _map;
};

So the question is, is there an alternative for an array_view for use with other container types? Basically all I would like to have is a lightweight object that I could return from a function that would act as an immutable view to some container without specifying a specific container type. It would even make sense to me to shove a std::set to something like an array_view, but with fewer supported operations (e.g., no random access). map is clearly a different beast and would require a different view supporting associative lookup, but even for a map I think it would be useful to have the ability to say array_view<const std::pair<const int, int>>. Am I asking for too much? Or perhaps there are reasonable ways to implement this? Or maybe there are even existing implementations of such 'views'?

PS: inheritance is not a prerequisite - I just thought that it's the easiest way to present the problem.

Topminnow

Answer 1

If you're just looking for a type-erased range, you could check out boost::any_range:

using IntRange = boost::any_range<
                     int,
                     boost::forward_traversal_tag,
                     int,
                     std::ptrdiff_t>;

int sum(IntRange const& range) {
    return std::accumulate(range.begin(), range.end(), 0);
}

int main()
{
    std::cout << sum(std::vector<int>{1, 2, 3}) << std::endl;  // OK, 6
    std::cout << sum(std::set<int>{4, 5, 6}) << std::endl;     // OK, 15
}

Even when you try to misuse it:

sum(std::map<int, int>{})

the error message isn't terrible:

/usr/local/include/boost/range/detail/any_iterator_wrapper.hpp:40:60: error: invalid static_cast from type 'std::pair<const int, int>' to type 'int&'
             return static_cast<Reference>(const_cast<T&>(x));
                                                            ^

You could create an alias for your use case:

template <typename T>
using FwdImmutableRangeT = boost::any_range<T,
                               boost::forward_traversal_tag,
                               const T&, std::ptrdiff_t>;

And return those:

class Interface {
public:
    virtual FwdImmutableRange<int> getArray() const = 0;
    virtual FwdImmutableRange<const int> getSet() const = 0;
    virtual FwdImmutableRange<std::pair<const int, int>> getMap() const = 0;
};

Typical

any_range is a view type, right? (sort of implied by the word range) I glanced at its docs, and that claim didn't stick out in the few pages I read. – Ladysmith

@Yakk Not sure what the specific term "view type" means, but I'm pretty sure you can't insert/remove elements. You can modify the elements via any_range tho. – Typical

I was wondering if it makes a copy, basically. Probably not. – Ladysmith

Answer 2

I am not aware of one, but a general view for a given set of interfaces is not that hard to write. You'd use type erasure with a manual vtable to keep things allocation-free.

Store a pvoid and a pointer to a table of functions. Each function erases the type dependency of one operation.

If the operation has signature R(Args...) then the erasing function pointer in the table has signature R(void*, Args...). I use stateless lambdas to write them in a vtable factory that constructs a static local vtable and returns a pointer to a const vtable.

The user-facing class exposes the operations, forwarding them to the vtable. It has a template ctor that stores the pvoid to the passed value, and gets the type-specific vtable from the factory.

You have to be a touch careful with your copy/move ctors of your view class: the template ctor should SFINAE guard against accepting view class instances.

The annoying part is that you either have to define new semantics for how associative containers work, or you also need to type erase their iterators. And in just views, as iterators are presumed to be value-like. That is a big advantage of vector, because T* can be used instead!

Now that I think of it, boost has type erased iterators, and probably views of associative containers.

If we just want "is it there" functionality (and "what is it" for map), and you don't need iteration, it is pretty easy:

namespace details {
  template<class K>
  using exists = bool(*)(void*, K const&);
  template<class K, class V>
  using get = V(*)(void*, K const&);

  template<class T>
  struct setlike_vtable {
    exists<T> pexists = 0;
    template<class S>
    static void ctor( setlike_vtable* table ) {
      table->pexists = [](void* p, T const& k)->bool {
        S*ps = static_cast<S*>(p);
        return ps->find(k) != ps->end();
      };
    }
    template<class S>
    static setlike_vtable const* make() {
      static const setlike_vtable retval = []{
        setlike_vtable retval;
        ctor<S>(&retval);
        return retval;
      }();
      return &retval;
    }
  };
  template<class K, class V>
  struct maplike_vtable : setlike_vtable<K> {
    get<K,V> pget = 0;
    template<class S>
    static void ctor( maplike_vtable* table ) {
      setlike_vtable<K>::template ctor<S>(table);
      table->pget = [](void* p, K const& k)->V {
        S*ps = static_cast<S*>(p);
        return ps->find(k)->second;
      };
    }
    template<class S>
    static maplike_vtable const* make() {
      static const maplike_vtable retval = []{
        maplike_vtable retval;
        ctor<S>(&retval);
        return retval;
      }();
      return &retval;
    }
  };
}

template<class T>
struct set_view {
  details::setlike_vtable<T> const* vtable = 0;
  void* pvoid = 0;
  template<class U,
    std::enable_if_t<!std::is_same<std::decay_t<U>, set_view>{}, int> =0
  >
  set_view(U&& u):
    vtable( details::setlike_vtable<T>::template make<std::decay_t<U>>() ),
    pvoid( const_cast<void*>( static_cast<void const*>( std::addressof(u) ) ) )
  {}
  set_view(set_view const&)=default;
  set_view() = default;
  ~set_view() = default;
  set_view& operator=(set_view const&)=delete;
  explicit operator bool() const { return vtable; }

  bool exists( T const&t ) const {
    return vtable->pexists( pvoid, t );
  }
};
template<class K, class V>
struct map_view {
  details::maplike_vtable<K, V> const* vtable = 0;
  void* pvoid = 0;
  template<class U,
    std::enable_if_t<!std::is_same<std::decay_t<U>, map_view>{}, int> =0
  >
  map_view(U&& u):
    vtable( details::maplike_vtable<K,V>::template make<std::decay_t<U>>() ),
    pvoid( const_cast<void*>( static_cast<void const*>( std::addressof(u) ) ) )
  {}
  map_view(map_view const&)=default;
  map_view() = default;
  ~map_view() = default;
  map_view& operator=(map_view const&)=delete;
  explicit operator bool() const { return vtable; }

  bool exists( K const&k ) const {
    return vtable->pexists( pvoid, k );
  }
  V get( K const& k ) const {
    return vtable->pget( pvoid, k );
  }
};

note that you want map_view< Key, Value const& > usually if you don't want get to return by-value.

live example.

Iteration via visiting is easy, but requires the passed in visitor to be type erased (down to say std::function). Iteration via iterators requires type erased iterators, and type erased iterators have to have value semantics. At that point, you are best stealing boost's implementation.

Coroutines being proposed right now gives an alternative way to solve the problem; have the type-erased views use coroutines to implement enumeration instead of visiting.

I'd bet the above view is slightly faster than boost::any_range, as it has less work to do due to design. You can speed it up by moving the vtable to be inline in the body of the view, removing a cache miss; for larger type erasure, this can cause runtime memory bloating, but the above type erasure views store 1-2 pointers in the vtable. Having a pointer to 1-2 pointers seems silly.

Ladysmith