c++ 容器容器的通用`flatten`

Question

我有兴趣实施一个通用的 flatten 容器容器

为了简化，我会使用自己的容器。主要原因是标准容器接收分配器的附加模板参数，这对我编写操作来说更复杂。因此，将容器 Vector<T>、List<T> 等视为标准容器，只是它们不需要分配器。

现在，我有一个操作flatten操作直到四个级别如下：

template <typename T,
      template <typename> class Container1,
      template <typename> class Container2>
List<T> flatten(const Container1<Container2<T>> & c)
{
  List<T> ret;
  for (auto & l : c)
    for (auto & item : l)
      ret.push_back(item);

  return ret;
}

template <typename T,
      template <typename> class Container1,
      template <typename> class Container2,
      template <typename> class Container3>
List<T>
flatten(const Container1<Container2<Container3<T>>> & c)
{
  List<T> ret;
  for (auto & l : c)
    ret.splice(ret.end(), flatten(l));

  return ret;
}

template <typename T,
          template <typename> class Container1,
          template <typename> class Container2,
          template <typename> class Container3,
          template <typename> class Container4>
    List<T> flatten // and so on for more levels ...

我的问题是：

是否存在一种更简洁、特别是通用的方法，允许任意数量的级别，可能基于更优雅的元编程，或者可能使用宏来编写此操作？
如果前面的问题是肯定的，那么有人可以总结一下怎么可能吗？
有什么方法可以至少将这种技术应用于标准容器？正如我所说，让我在标准容器上的 flatten 版本变得复杂的是这些容器接收分配器作为模板参数。

Answer 1

大概是这样的：

template <typename T>
struct LooksLikeContainer {
  struct Yes{};
  struct No {Yes yes[2];};

  template <typename U>
  static auto test(U* p) ->
    typename std::enable_if<sizeof(std::begin(*p)) != 0, Yes>::type;

  static No test(...);

  static constexpr bool value = sizeof(test(static_cast<T*>(nullptr))) == sizeof(Yes);
};

template <typename In, typename Out>
auto flatten(const In& in, Out* out) ->
  typename std::enable_if<!LooksLikeContainer<In>::value>::type;

template <typename In, typename Out>
auto flatten(const In& in, Out* out) ->
  typename std::enable_if<LooksLikeContainer<In>::value>::type {
  for (auto& el : in) {
      flatten(el, out);
  }
}

template <typename In, typename Out>
auto flatten(const In& in, Out* out) ->
  typename std::enable_if<!LooksLikeContainer<In>::value>::type {
  out->push_back(in);
}

Live demo

Answer 2

最简单的方法是递归地展平容器：

template<typename Container, typename T>
void flatten_impl(Container const& c, List<T>& out)
{
   for(auto const& elem : c) flatten(elem, out);
}

显然，与任何递归一样，您也需要终止此递归：

template<typename Elem, typename T>
void flatten_impl(Elem e, List<T>& out)
{
    out.push_back(e);
}

由于这些现在有歧义，您需要解决歧义：

template<typename Elem, typename T>
void flatten_impl(Elem e, List<T>& out, ...)
{
    out.push_back(e);
}
template<typename Container, typename T>
std::void_t<typename Container::value_type> flatten_impl(Container const& c, List<T>& out)
{
   for(auto const& elem : c) flatten(elem, out);
}

Answer 3

使用 range-v3，您可以使用 ranges::view::join，例如：

namespace detail
{
    struct overload_priority_low {};
    struct overload_priority_high : overload_priority_low {};

    template <typename R>
    R flatten(R&& r, overload_priority_low)
    {
        return std::forward<R>(r);
    }

    template <typename R>
    auto flatten(R&& r, overload_priority_high)
    -> decltype(flatten(std::forward<R>(r) | ranges::view::join, overload_priority_high{}))
    {
        return flatten(std::forward<R>(r) | ranges::view::join, overload_priority_high{});
    }

}

template <typename R>
auto flatten(R&& r)
{
    return detail::flatten(std::forward<R>(r), detail::overload_priority_high{});
}

Demo

c++ 容器容器的通用`flatten`

c++ general `flatten` of container of containers

c++

metaprogramming