mercredi 4 novembre 2015

pointer member typedef for iterator categories of containers

Given a set universe of distinct elements of some type Point (it can be any STL container (say, std::forward_list or std::vector) or POD array, or simply many different objects of the same type). An iterator to elements of this set have a type Iterator (it can be std::container<>::iterator or std::container<>::const_iterator, or (const) pointer to Point).

Given a short subsets polyhedra of the set, represented as STL containers (facet) of elements of iterator type. I want to make a hash for facets elements and for facet type itself.

I do the following:

    using value_type = double;
    using Point = std::valarray< value_type >;
    //using Point = value_type [3];
#if 1
    std::forward_list< Point > universe;
    // init universe
    // following point_iterator is Iterator
    using point_iterator = typename std::forward_list< point >::const_iterator;
#elif 0
    Point universe[100] = /* init */;
    using point_iterator = Point const *;
#else
    Point p0 = /* init */
    Point p1 = /* init */;
    // ...
    struct
    {
       Point p;
       int i;
    } s = {/* init */};
    using point_iterator = Point const *;
#endif
    using facet = std::vector< point_iterator >;
    std::deque< facet > polyhedra;
    // fill polyhedra

I.e. Iterator (point_iterator) is template parameter of some algorithm for polyhedra construction. During operation of the algorithm I need a hashes for facet objects.

std::hash< typename std::iterator_traits< point_iterator >::pointer > point_hash;
struct facet_hash
{
    std::size_t
    operator () (facet const & f) const noexcept
    {
        std::size_t hash = 0;
        for (point_iterator const & p : f) {
            hash ^= point_hash(&*p); // hash combiner
        }
    }
};

Due to multipass guarantee for ForwardIterator expression *p should give a reference to the same object repeatedly.

All the consequent iterator categories (for STL containers) are defined as a descendants of ForwardIterator. Requirements of each next iterator category in chain ForwardIterator -> BidirectionalIterator -> RandomAccessIterator is supersets of the requirement for a previous one. But:

  • It is not clear whether the requirement to reference member typedef of ForwardIterator is redefined or not further in the chain. I.e. does the expression *r for RandomAccess iterator should results in exactly the typename std::iterator_category< std::remove_reference_t< decltype(r) > >::value_type /* const */ & or it can be a custom type? The case of std::vector< bool > suggests that the latter is true (and requirement to reference member typedef is redefined too).
  • It is not clear how must be defined the pointer member typedef for each iterator category. For std::iterator_traits< Iterator > it is mandatory for (non-pointer) Iterator to have all five the member typedefs simultaneously to be able to provide its own corresponding member typedefs. But there is no any wordings about the pointer member typedef for iterator categories.

Point can have user-provided overloading of operator &. In such a case above definitions of hashes might be invalid. The expression &*p must be refactored as std::addressof(*p). But how to properly change the point_hash definition?

Can I leave it unchanged? Or should I change it to:

std::hash< typename std::iterator_traits< point_iterator >::value_type const * > point_hash;

?

Aucun commentaire:

Enregistrer un commentaire