Alternative to array_view for maps, sets, etc.

Question

Suppose I have a class hierarchy that has a couple of virtual functions that return a reference to a container:

 #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, you can actually return vector , set or map in any subclass of the Interface class. However, for the vector part, I could use, for example, a gsl::array_view to mitigate this limitation:

 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 to array_view for use with other types of containers? Basically, all I would like to have is a lightweight object that I could return from a function that would act as an immutable representation for any container without specifying a specific type of container. It would even be wise for me to drag std::set into something like array_view , but with fewer supported operations (for example, without random access). map clearly different from another beast and requires a different supportive associative search view , but even for map I think it would be useful to be able to say array_view<const std::pair<const int, int>> . Am I asking too much? Or maybe there are reasonable ways to implement this? Or perhaps there are even existing implementations of such “representations”?

PS: inheritance is not a prerequisite - I just thought it was the easiest way to introduce the problem.

Answer 1

If you're just looking for a range of erasable types, you can check 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 use it incorrectly:

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

the error message is not scary:

 /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 can 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 them:

 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; }; 

Answer 2

I do not know about this, but the general view for this set of interfaces is not so difficult to write. You should use style-wiping with the vtable manual table to maintain access to things.

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

If the operation has the signature R(Args...) , then the pointer to the erase function in the table has the signature R(void*, Args...) . I am using stagnant lambdas to write them to a vtable factory, which creates a static local vtable and returns a pointer to a vtable constant.

The user class provides operations by sending them to the vtable. It has a ctor template that stores pvoid in the passed value and gets the vtable type from the factory type.

You must be careful with your copies / movements of your view class: the ctor template should protect SFINAE from accepting instances of the view class.

The annoying part is that you either need to define new semantics, how associative containers work, or you also need to introduce erasure of your iterators. And only in the view, since iterators are considered valuable. This is a big advantage of the vector because T* can be used instead!

Now that I think about it, boost has a type of erasable iterators and, possibly, kinds of associative containers.

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

 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 return a value.

living example .

The iteration during the visit is simple, but it is required that the past one in the guest dash is erased (up to std::function ). Iterating with iterators requires erasing type iterators, and the type of erased iterators must have semantics of values. At this point, your best bet is to steal the boost implementation.

The Coroutines now offered provide an alternative way to solve the problem; for types with deletion, coroutines are used to implement the enumeration instead of visiting.

I would put that the above view is a little faster than boost::any_range , since it has less design work. You can speed it up by moving the vtable to be embedded in the body of the view, removing the missing cache; to erase a larger size, this can lead to bloating at runtime, but erase scans above the types save 1-2 pointers in the vtable. Having a pointer to 1-2 pointers seems silly.