Общая STL-совместимая гистограмма в C ++ 11 - PullRequest
Новая
       20

Общая STL-совместимая гистограмма в C ++ 11

2 голосов
/ 12 января 2012

Вот моя первая попытка использовать шаблонную функцию гистограммы в C ++, протестированную в GCC 4.6. Однако я хотел бы объединить dense_histogram() и sparse_histogram() в один общий шаблон универсальной функции. Проблема в том, что плотный -специфический конструктор H h(n, 0) не определен и не релевантен в sparse версии H h. Есть ли способ решить эту проблему каким-нибудь умным C ++ обычным способом или статически, обычно используя условную компиляцию через Boost Type.Traits (#include <boost/type_traits.hpp>)? 

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

}

запустить с помощью

1 Ответ

2 голосов
/ 12 января 2012

Я думаю, что вы должны просто поместить только общие части в третью функцию, оставляя 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;
}

Однако, поскольку вы запросилиit: Поскольку вы работаете с контейнерами, я бы предположил, что у них дешевый ход, так что вы можете определить черту создания для генерации вашего контейнера и переместить ее в локальную переменную.Затем вы можете написать собственное обнаружение соответствующего конструктора, например: 

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, только если объявление зависит от типа, определенного пользователем, и специализация соответствует требованиям стандартной библиотеки для исходного шаблона и явно не запрещена.

...