C++11 中的通用 STL 兼容直方图

Question

这是我第一次尝试 C++ 中的通用直方图模板函数，并使用 GCC 4.6 进行测试。但是，我想将 dense_histogram() 和 sparse_histogram() 合并到一个通用的通用函数模板中。问题是特定于密集的构造函数H h(n, 0)在稀疏版本H中既没有定义也没有相关性h.有没有办法以某种巧妙的 C++ 常规方式或静态地通过 Boost Type.Traits (#include) 使用条件编译来解决此问题？

#include <algorithm>
#include <limits>
#include <algorithm>
#include <vector>
#include <unordered_map>

namespace std
{

/*!
 * \em Dense Histogram of \p a.
 *
 * \tparam V is Value Type.
 * \tparam C is Count (Bin) Type.
 * \tparam H is Histogram Storage Type, typically a vector.
 *
 * \param[in] x is a set of the input data set
 */
template <class V, class C = size_t, class H = vector<C> >
inline
H dense_histogram(const V & x)
{
    typedef typename V::value_type E; // element type
    size_t n = (static_cast<C>(1)) << (8*sizeof(E)); // maximum number of possible elements for dense variant
    H h(n, 0);                       // histogram
    C bmax = 0;                      // bin max
    for_each(begin(x), end(x),  // C++11
             [&h, &bmax] (const E & e) { // value element
                 h[e]++;
                 bmax = std::max(bmax, h[e]);
             });
    return h;
}
template <class V, class H = vector<size_t> > H make_dense_histogram(const V & x) { return dense_histogram<V, size_t, H>(x); }

/*!
 * \em Sparse Histogram of \p a.
 *
 * \tparam V is Value Type.
 * \tparam C is Count (Bin) Type.
 * \tparam H is Histogram Structure Type, typically a unordered_map.
 *
 * \param[in] x is a set of the input data set
 */
template <class V, class C = size_t, class H = unordered_map<typename V::value_type, C> >
inline
H sparse_histogram(const V & x)
{
    typedef typename V::value_type E; // element type
    H h;                        // histogram
    C bmax = 0;                 // bin max
    for_each(begin(x), end(x), // C++11
             [&h,&bmax] (const E & e) { // value element
                 h[e]++;
                 bmax = std::max(bmax, h[e]);
             });
    return h;
}
template <class V, class H = unordered_map<typename V::value_type, size_t> > H make_sparse_histogram(const V & x) { return sparse_histogram<V, size_t, H>(x); }

}

运行使用

Answer 1

我认为您应该简单地将公共部分放在第三个函数中，留下 dense_histogram 和 sparse_histogram 来创建 h 并调用该实现函数：

template <class V, class C = size_t, class H>
inline void histogram_impl(const V & x, H& h) {
    typedef typename V::value_type E; // element type
    C bmax = 0;                      // bin max
    for_each(begin(x), end(x),  // C++11
             [&h, &bmax] (const E & e) { // value element
                 h[e]++;
                 bmax = std::max(bmax, h[e]);
             });
    return h;
}
template <class V, class C = size_t, class H = vector<C> >
inline H dense_histogram(const V & x) {
    typedef typename V::value_type E; // element type
    size_t n = (static_cast<C>(1)) << (8*sizeof(E)); // maximum number of possible elements for dense variant
    H h(n, 0);                       // histogram
    histogram_impl(x, h);
    return h;
}
template <class V, class C = size_t, class H = unordered_map<typename V::value_type, C> >
inline H sparse_histogram(const V & x) {
    H h;                        // histogram
    histogram_impl(x, h);
    return h;
}

但是，因为你要求它：当你在容器上工作时，我会假设它们有一个便宜的移动，所以你可以定义一个创建特征来生成你的容器并将其移动到你的本地变量中。然后，您可以编写自己的适当构造函数检测，如下所示：

template<typename T> struct has_explicit_length_constructor{
private:
   template<typename U>
   decltype(U(0, 0), void(), std::true_type()) test(int x);
   template<typename>
   std::false_type test(...);
  typedef decltype(test<T>(0)) constant_type;
public:
   constexpr bool value = constant_type::value;
};

template<class H, bool B = has_explicit_length_constructor<H>::value> struct histogram_creation_trait;
template<class H> struct histogram_creation_trait<H, true> {
  static H create()  {
    size_t n = (static_cast<C>(1)) << (8*sizeof(typename V::value_type));
    return H(n, 0);  
  }
};
template<class H> struct histogram_creation_trait<H, false>
{ static H create()  { return H(); } };

template <class V, class C = size_t, class Ht>
inline void histogram_impl(const V & x, H& h, Trait) {
    typedef typename V::value_type E; // element type
    C bmax = 0;                      // bin max
    H h = histogram_creation_trait<H>::create();
    for_each(begin(x), end(x),  // C++11
             [&h, &bmax] (const E & e) { // value element
                 h[e]++;
                 bmax = std::max(bmax, h[e]);
             });
    return h;
}
template <class V, class H = vector<size_t> > H make_dense_histogram(const V & x) { return histogram_impl<V, size_t, H>(x); }
template <class V, class H = unordered_map<typename V::value_type, size_t> > H make_sparse_histogram(const V & x) { return histogram_impl<V, size_t, H>(x); }

作为一个方面，不要：将您自己的方法添加到 std 是标准的 UB ([namespace.std] $17.6.4.2. 1 p1）：

如果 C++ 程序向命名空间 std 或命名空间 std 内的命名空间添加声明或定义，则该程序的行为是未定义的，除非另有指定。仅当声明依赖于用户定义的类型并且专门化满足原始模板的标准库要求且未明确禁止时，程序才可以将任何标准库模板的模板专门化添加到命名空间 std。