Deduce type of container from iterator (when possible)

Question

Is it possible to detect the container type from the iterator type?

For example,

#include<traits>
int main(){
   static_assert(std::is_same<
      container_of<std::vector<double>::iterator>::type, std::vector<double>>{});
   static_assert(std::is_same<
      container_of<std::list<int>::iterator>::type, std::list<int>>{});
}

(Of course some iterators type will not give a container (or not give a unique container), for example a raw pointer or a stream iterator, but in those cases it can soft-SFINAE-fail.)

The first attempt is

template<class T, template<class> class Cont> Cont<T> aux(typename Cont<T>::iterator it);

template<class Iterator> struct container_of{
  using type = decltype(aux(Iterator{}));
};

However, it doesn't work because the compiler can't detect the type of T (it is not in a deductible context).

---

Motivation: I want to detect whether the associated container of an iterator has a .data() member.

Answer 1

The is_contiguous_iterator type trait evaluates to true if the type T is a pointer or an iterator of a standard container or view that model ContiguousContainer.

To verify whether the type is a pointer, it is sufficient to exploit a standard type trait, std::is_pointer. For the second condition, it is possible to verify whether it is the same as the iterator or const-iterator of std::array, std:vector, std::basic_string, std::basic_string_view, std::span or std::valarray. The value type can be inferred from T through the std::iterator_traits interface.

Even if the above approach may seem robust, it has an important limit: if one of the containers specializes the iterator depending on template parameters that are not only the value type, a false negative may occur. Indeed, it is not guaranteed that, given a certain container C, the type C<U, Args...>::iterator be the same as C<U>::iterator. The same is valid for const-iterators. An example is the MSVC library, in which iterator types are often specialized for their own container type.

The simplest solution concerns with verifying whether the template class of the type T match with the template class of any iterator or const-iterator.

Example:

namespace detail {
    template <typename, typename...>
    struct is_same_template
     : std::false_type {};
    
    template <typename T, typename U, typename ...Us>
    struct is_same_template<T, U, Us...>
     : is_same_template<T, Us...> {};
    
    template <template <typename...> typename T, typename ...Args, typename ...Vs, typename ...Us>
    struct is_same_template<T<Args...>, T<Vs...>, Us...>
     : std::true_type {};
    
    template <typename T>
    struct is_contiguous_iterator
     : std::bool_constant<
         std::is_pointer<T>::value
          && is_same_template<T, typename std::array<char, 1>::iterator, typename std::array<char, 1>::const_iterator, 
                                 typename std::vector<char>::iterator, typename std::vector<char>::const_iterator, 
                                 typename std::basic_string<char>::iterator, typename std::basic_string<char>::const_iterator, 
                                 typename std::basic_string_view<char>::iterator, typename std::span<char>::iterator, 
                                 decltype(std::begin(std::declval<std::valarray<char>&>())), 
                                 decltype(std::begin(std::declval<const std::valarray<char>&>()))>>::value
       > {};
}

template <typename T>
struct is_contiguous_iterator
 : detail::is_contiguous_iterator<T> {};

template <typename T>
inline constexpr bool is_contiguous_iterator_v = is_contiguous_iterator<T>::value;

Answer 2

What I am doing at the moment is to manually register all (some really) of the iterators that are contiguous.

Since I will always need this in combination with some way to extract the raw pointer, I directly code a single function called data that returns the pointer.

The code is not funny, it considers std::vector<>::iterator, std::basric_string<>::iterator, for illustration (to show that it will always be incomplete) I also added boost::static_vector<>, raw pointer and anything convertible to a pointer. (boost::array<>::iterator and std::array<>::iterator and begin/end(std::valarray) are effectively included because the iterators are pointers). I also had to include the const_iterator cases.

#include<type_traits>
#include<vector> // the code below needs to know about std::vector
#include<boost/container/static_vector.hpp> // ... and all possible contigous containers :(

template<
    class ContiguousIterator, // well ProbablyContiguos
    typename = std::enable_if_t<

        /**/std::is_same<ContiguousIterator, typename std::vector<std::decay_t<decltype(*std::declval<ContiguousIterator>())>>::iterator>{}
        or  std::is_same<ContiguousIterator, typename std::vector<std::decay_t<decltype(*std::declval<ContiguousIterator>())>>::const_iterator>{}

        or  std::is_same<ContiguousIterator, typename std::basic_string<std::decay_t<decltype(*std::declval<ContiguousIterator>())>>::iterator>{}

        or  std::is_same<ContiguousIterator, typename boost::container::static_vector<std::decay_t<decltype(*std::declval<ContiguousIterator>())>, 1>::iterator>{}
        or  std::is_same<ContiguousIterator, typename boost::container::static_vector<std::decay_t<decltype(*std::declval<ContiguousIterator>())>, 1>::const_iterator>{}
        // many many other possible iterators :(

        or  std::is_pointer<ContiguousIterator>{}
        or  std::is_constructible<typename std::iterator_traits<ContiguousIterator>::pointer, ContiguousIterator>{}
    >
>
typename std::iterator_traits<ContiguousIterator>::pointer
data(ContiguousIterator const& it){return std::addressof(*it);}

int main(){
    std::vector<double> v(30);
    v[0] = 10.;
    assert( *data(v.begin()) == 10. );
}

Feedback is welcomed.

Answer 3

Instead of your primitive being an iterator, make your primitive be a range.

template<class It, bool Contiguous, class D=void>
struct range_t {
  using Self = std::conditional< !std::is_same<D, void>, D, range_t >;
  It b, e;
  It begin() const { return b; }
  It end() const { return e; }
  Self without_front( std::size_t i = 1 ) const {
    return {std::next(begin(), i), end()};
  }
  Self without_back( std::size_t i = 1 ) const {
    return {begin(), std::prev(end(), i)};
  }
  bool empty() const { return begin()==end(); }
  std::size_t size() const { return std::distance( begin(), end() ); }
};
template<class It>
struct range_t<It, true, void>:
  range_t<It, false, range_t<It, true>>
{
  using Base = range_t<It, false, range_t<It, true>>;
  range_t( It b, It e ):Base(b,e) {}
  auto* data() const {
    if (empty()) return nullptr;
    return std::addressof(*this->begin()); }
  }
};

Track (manually) what containers are contiguous:

template<class T, class=void>
struct is_contiguous_container : std::false_type{};
template<class T>
struct is_contiguous_container<T const, void> : is_contiguous_container<T> {};
template<class T>
struct is_contiguous_container<T volatile, void> : is_contiguous_container<T> {};
template<class T>
struct is_contiguous_container<T const volatile, void> : is_contiguous_container<T> {};
template<class T>
struct is_contiguous_container<T, std::enable_if_t< has_data_ptr<T>{} >>:
  std::true_type{};
template<class T, std::size_t N>
struct is_contiguous_container<T[N],void> : std::true_type{};

The contiguous containers are array, std::array and std::vector, so not much to track. range_t< ?, true, ? > is also contiguous. Just write has_data_ptr, that is true iff T.data() returns a pointer to non-void.

template<class C>
auto range( C&& c ) {
  using std:begin; using std::end;
  auto b = begin(c), e = end(c);
  using It = decltype(b);
  using R = range_t<It, is_contiguous_container<std::remove_reference_t<C>>{}>;
  return R{ b, e };
}

range now smartly converts a container into a range_t, keeping track of if it is contiguous or not.

range_t supports r.without_front( r.size()/2 ) to divide and conquer.

When a range is contiguous, just call .data() on it. When it isn't, don't.

Answer 4

In your application if you just want to know whether the container has a .data() member, it might be enough for you to check if it is random access (using std::iterator_traits<Iter>::iterator_category()).

Otherwise, I think you might be able to use a combination of the technique in: How to check if two types come from the same templated class and partial specialization for every standard container type.

Or wait for c++17 which has a new contiguous iterator concept: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n4284.html