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