Obtain container type from (its) iterator type in C++ (STL)

Question

It is easy given a container to get the associated iterators, example:

std::vector<double>::iterator i; //An iterator to a std::vector<double>

I was wondering if it is possible, given an iterator type, to deduce the type of the "corresponding container" (here I am assuming that for each container there is one and only one (non-const) iterator).

More precisely, I would like a template metafunction that works with all STL containers (without having to specialize it manually for each single container) such that, for example:

ContainerOf< std::vector<double>::iterator >::type 

evaluates to

std::vector<double>

Is it possible? If not, why?

Thank you in advance for any help!

Answer 1

The exact runtime types of C++ STL iterators are intentionally undefined and therefore implementation-specific. You can search through your compiler vendor's header files to find out what type is actually used and deduce the container from that, but it's vendor- and version-specific, therefore prone to breaking.

Answer 2

The point of iterators is that you use them to do work without having to know the underlying container type, for example passing a begin/end pair and doing work on that range.

However, if all you care about is the iterator type, I believe you can use iterator traits to determine for example if an iterator is random access. Take std::advance, the general case is that it calls operator++ on the iterator n times, but is specialized for random access iterators to use += instead.

Other than that I'm not aware of any way to get the container type from the iterator.

Answer 3

I don't think this would be possible. On some STL libraries you actually have a vector iterator as a pointer type, i.e. std::vector<T>::iterator is a T* so I can't think of any way you could get back to the container type from that.

Answer 4

Just for fun, here's something I quickly hacked with Boost.MPL (warning: This was veeeery superficially tested, so handle with care):

#include <boost/mpl/list.hpp>
#include <boost/mpl/find_if.hpp>
#include <boost/type_traits.hpp>
#include <vector>
#include <string>
#include <list>
#include <set>

// List of candidate container types
template<typename T>
struct ContainersOf : boost::mpl::list<
    std::vector<T>,
    std::basic_string<T>,
    std::list<T>,
    std::set<T>
>{};

// Metafunction to evaluate if IteratorT == ContainerT::iterator
template<class IteratorT, class ContainerT>
struct IsIteratorOf
{
    typedef typename 
    boost::is_same<
        IteratorT, 
        typename ContainerT::iterator
    >::type type;
};

// Metafunction to compute a container type from an iterator type
template<class IteratorT>
struct ContainerOf
{
    typedef typename 
    boost::mpl::deref<typename 
        boost::mpl::find_if<
            ContainersOf<typename std::iterator_traits<IteratorT>::value_type>,
            IsIteratorOf<IteratorT, boost::mpl::_1>
        >::type
    >::type type;
};

// Test
int main()
{
    ContainerOf<std::list<int>::iterator>::type l;
    std::list<int> l2 = l;  // OK
    std::vector<int> v = l; // Fails to compile

    return 0;
}