array_view 地图、集合等的替代方案

Question

假设我有一些 class 层次结构，其中有几个 virtual 函数 return 容器引用：

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

目前，实际上只能 return vector、set 或 map 在 [的任何子 class 中=17=] class。但是，对于 vector 部分，我可以使用 gsl::array_view 来放宽此限制：

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

所以问题是，是否有 array_view 的替代方案用于其他容器类型？基本上我想要的只是一个轻量级对象，我可以 return 从一个函数中 return 充当某个容器的不可变视图，而无需指定特定的容器类型。将 std::set 推到 array_view 之类的东西对我来说甚至是有意义的，但支持的操作更少（例如，没有随机访问）。 map 显然是一个不同的野兽，需要不同的 view 支持关联查找，但即使对于 map 我认为能够说 array_view<const std::pair<const int, int>> 也会很有用.我要求太多了吗？或者也许有合理的方法来实现这个？或者甚至可能存在这种 'views'?

的现有实现

PS：继承不是先决条件 - 我只是认为这是呈现问题的最简单方法。

Answer 1

如果您只是在寻找类型擦除的范围，您可以查看 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
}

即使您试图滥用它：

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

错误信息并不可怕：

/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));
                                                            ^

您可以为您的用例创建一个别名：

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

和return那些：

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

我不知道一个，但是给定接口集的一般视图并不难写。您将使用带有手动 vtable 的类型擦除来保持无分配。

存储一个 pvoid 和一个指向 table 函数的指针。每个函数擦除一个操作的类型依赖。

如果操作具有签名 R(Args...)，则 table 中的擦除函数指针具有签名 R(void*, Args...)。我使用无状态 lambda 将它们写入一个 vtable 工厂，该工厂构造一个静态本地 vtable 和 returns 一个指向 const vtable.

的指针

面向用户的 class 公开操作，将它们转发给 vtable。它有一个模板构造器，将 pvoid 存储到传递的值，并从工厂获取特定类型的 vtable。

您必须小心处理您的 copy/move 视图构造器 class：模板构造器应该 SFINAE 防止接受视图 class 实例。

烦人的部分是您必须为关联容器的工作方式定义新的语义，或者您还需要键入擦除它们的迭代器。在公正的观点中，迭代器被认为是类似价值的。这是vector的一大优势，因为可以用T*代替！

现在我想起来了，boost 有类型擦除的迭代器，可能还有关联容器的视图。

如果我们只需要 "is it there" 功能（和 "what is it" 地图），并且不需要迭代，那很简单：

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

请注意，如果您不希望按值 get 到 return，则通常需要 map_view< Key, Value const& >。

live example.

通过访问进行迭代很容易，但需要对传入的访问者进行类型擦除（向下说 std::function）。通过迭代器进行迭代需要类型擦除迭代器，类型擦除迭代器必须具有值语义。到那时，您最好窃取 boost 的实现。

现在提出的协程提供了解决问题的另一种方法；让类型擦除的视图使用协程来实现枚举而不是访问。

我敢打赌上面的视图比 boost::any_range 稍微快一点，因为它在设计上需要做的工作更少。您可以通过将 vtable 移动到视图主体中内联来加快速度，从而消除缓存未命中；对于较大的类型擦除，这会导致运行时内存膨胀，但上述类型擦除视图在 vtable 中存储了 1-2 个指针。拥有指向 1-2 个指针的指针似乎很愚蠢。

array_view 地图、集合等的替代方案

array_view alternative for maps, sets, etc

c++

c++11

c++14

array-view

cpp-core-guidelines