Specializes in iterator_traits

Question

I would like to specialize std::iterator_traits<> for iterators of a container class template that does not have the usual nested typedefs (e.g. value_type , difference_type , etc.) and whose source I should not change. Basically, I would like to do something like this:

 template <typename T> struct iterator_traits<typename Container<T>::iterator> { typedef T value_type; // etc. }; 

except that this does not work as the compiler cannot infer T from Container<T>::iterator .

Is there any working way to achieve the same?

---

For example:

 template <typename T> class SomeContainerFromAThirdPartyLib { typedef T ValueType; // not value_type! // no difference_type class iterator { typedef T ValueType; // not value_type! // no difference_type ... }; iterator begin() { ... } iterator end() { ... } ... }; 

Now suppose I call std::count() with an instance of this class. As far as I know, in most implementations of STL count() returns iterator_traits<Iterator>::difference_type . The main iterator_traits<I> template simply executes typedef typename I::difference_type difference_type . Same thing with other nested types.

Now, in our example, this obviously will not work, since there is no Container::iterator::difference_type . I thought I could get around this without changing the iterator class, specializing in iterator_traits for iterators of any Container<T> .

In the end, I just want to be able to use std algorithms like count, find, sort, etc., preferably without modifying the existing code. I thought the whole point of iterator_traits is that: the ability to specify types (e.g. value_type , diff_type , etc.) For types of iterators that don't support them. Unfortunately, I cannot figure out how to specialize the feature class for all instances of Container<T> .

Answer 1

Yes. The compiler cannot derive T from Container<T>::iterator , because it is not an inferred context, which, in other words, means that given Container<T>::iterator , the value of T cannot be unambiguously and reliably inferred (see for a detailed explanation ).

The only solution to this problem is that you should fully specialize iterator_traits for every possible iterator value that you intend to use in your program. There is no general solution, since you are not allowed to edit the template of the class Container<T> .

Answer 2

Nawaz's answer is most likely the right solution for most cases. However, if you are trying to do this for many instances of SomeContainerFromAThirdPartyLib<T> and only a few functions (or an unknown number of instances, but a fixed number of functions, which can happen if you write your own library), in a different way.

Suppose we are provided with the following (immutable) code:

 namespace ThirdPartyLib { template <typename T> class SomeContainerFromAThirdPartyLib { public: typedef T ValueType; // not value_type! // no difference_type class iterator { public: typedef T ValueType; // not value_type! // no difference_type // obviously this is not how these would actually be implemented int operator != (const iterator& rhs) { return 0; } iterator& operator ++ () { return *this; } T operator * () { return T(); } }; // obviously this is not how these would actually be implemented iterator begin() { return iterator(); } iterator end() { return iterator(); } }; } 

We define an adapter class template containing the necessary typedef for iterator_traits , and specialize it to avoid pointer problems:

 namespace MyLib { template <typename T> class iterator_adapter : public T { public: // replace the following with the appropriate types for the third party iterator typedef typename T::ValueType value_type; typedef std::ptrdiff_t difference_type; typedef typename T::ValueType* pointer; typedef typename T::ValueType& reference; typedef std::input_iterator_tag iterator_category; explicit iterator_adapter(T t) : T(t) {} }; template <typename T> class iterator_adapter<T*> { }; } 

Then, for each function that we want to call using SomeContainerFromAThirdPartyLib::iterator , we define the overload and use SFINAE:

 template <typename iter> typename MyLib::iterator_adapter<iter>::difference_type count(iter begin, iter end, const typename iter::ValueType& val) { cout << "[in adapter version of count]"; return std::count(MyLib::iterator_adapter<iter>(begin), MyLib::iterator_adapter<iter>(end), val); } 

Then we can use it as follows:

 int main() { char a[] = "Hello, world"; cout << "a=" << a << endl; cout << "count(a, a + sizeof(a), 'l')=" << count(a, a + sizeof(a), 'l') << endl; ThirdPartyLib::SomeContainerFromAThirdPartyLib<int> container; cout << "count(container.begin(), container.end(), 0)="; cout << count(container.begin(), container.end(), 0) << std; return 0; } 

You can find an executable example with the required include and using at http://ideone.com/gJyGxU . Exit:

  a = Hello, world
 count (a, a + sizeof (a), 'l') = 3
 count (container.begin (), container.end (), 0) = [in adapter version of count] 0

Unfortunately, there are reservations:

• As I said, for every function that you plan to support, an overload must be defined ( find , sort , etc.). This will obviously not work for functions from algorithm that are not yet defined.
• If this is not optimized, there may be small penalties for performance at runtime.
• There are potential problems with defining the scope.

As for the latter, the question is in what namespace the overload is placed (and how to call the std version). Ideally, this would be in ThirdPartyLib so that it can be found using an argument-dependent search, but I suggested that we cannot change it. The next best option is in MyLib , but then the call should be qualified or should be preceded by using . In either case, the end user must either use using std::count; , or be careful about which calls qualify with std:: , because if std::count mistakenly used with SomeContainerFromAThirdPartyLib::iterator , this obviously will fail (the whole reason for this exercise).

An alternative, not to suggest , but to be here for completeness, would be right in the std . This will lead to undefined behavior; while this may work for you, in the standard it does not guarantee anything. If we specialized in count instead of overloading, that would be legal.

Answer 3

In this specialization, T is in an inexplicable context, but there is no third-party container container code or any specialization in the std .

If the third-party library does not provide any free begin and end functions in the corresponding namespace, you can write your own functions (in this namespace, if necessary to enable ADL), and wrap the iterator in your own wrapper class, which in turn provides necessary typedefs and operators.

First you need an Iterator shell.

 #include <cstddef> namespace ThirdPartyStdAdaptor { template<class Iterator> struct iterator_wrapper { Iterator m_it; iterator_wrapper(Iterator it = Iterator()) : m_it(it) { } // Typedefs, Operators etc. // ie using value_type = typename Iterator::ValueType; using difference_type = std::ptrdiff_t; difference_type operator- (iterator_wrapper const &rhs) const { return m_it - rhs.m_it; } }; } 

Note. You can also make iterator_wrapper inherit from Iterator or make it more general and have another helper to enable and carry other iterators.

Now begin() and end() :

 namespace ThirdPartyLib { template<class T> ThirdPartyStdAdaptor::iterator_wrapper<typename SomeContainer<T>::iterator> begin(SomeContainer<T> &c) { return ThirdPartyStdAdaptor::iterator_wrapper<typename SomeContainer<T>::iterator>(c.begin()); } template<class T> ThirdPartyStdAdaptor::iterator_wrapper < typename SomeContainer<T>::iterator > end(SomeContainer<T> &c) { return ThirdPartyStdAdaptor::iterator_wrapper < typename SomeContainer<T>::iterator > (c.end()); } } 

(It is also possible to have them in a different namespace than SomeContainer , but lose ADL. IF there are begin and end functions present in the namespace for this container, I would like to rename the adapters to something like wbegin and wend .)

Now standard algorithms can be called using these functions:

 ThirdPartyLib::SomeContainer<SomeType> test; std::ptrdiff_t d = std::distance(begin(test), end(test)); 

If begin() and end() are included in the library namespace, the container can be used even in more general contexts.

 template<class T> std::ptrdiff_t generic_range_size(T const &x) { using std::begin; using std::end; return std::distance(begin(x), end(x)); } 

Such code can be used with std::vector , as well as ThirdPartyLib::SomeContainer , if ADL finds begin() and end() , returning a wrapper iterator.

Answer 4

You can use the Container parameter as a template for your iterator_traits . As for the rest of the STL, these are typedefs inside your attribute class, such as value_type . They must be installed correctly:

 template <class Container> struct iterator_traits { public: typedef typename Container::value_type value_type; // etc. }; 

Then you would use value_type , where you would use T earlier.

Regarding the use of the feature class, you, of course, parameterize it with the type of the external container:

 iterator_traits<TheContainer> traits; 

Naturally, this assumes that TheContainer conforms to standard STL container contracts and has value_type defined correctly.