I'd like to specialize std::iterator_traits<>
for iterators of a container class template that does not have the usual nested typedefs (like value_type
, difference_type
, etc.) and whose source I shouldn't modify. Basically I'd like to do something like this:
template <typename T> struct iterator_traits<typename Container<T>::iterator>
{
typedef T value_type;
// etc.
};
except that this doesn't work, as the compiler is unable to deduce 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()
using an instance of this class. As far as I know, in most STL implementations, count()
returns iterator_traits<Iterator>::difference_type
. The primary template of iterator_traits<I>
simply does typedef typename I::difference_type difference_type
. Same with the other nested types.
Now in our example this obviously won't work, as there's no Container::iterator::difference_type
. I thought I could work around this without modifying the iterator class, by specializing 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 any existing code. I thought that the whole point of iterator_traits
is exactly that: being able to specify types (like value_type
, diff_type
etc.) for iterator types that do not support them built-in. Unfortunately I can't figure out how to specialize the traits class for all instances of Container<T>
.
std::iterator_traits is the type trait class that provides uniform interface to the properties of LegacyIterator types. This makes it possible to implement algorithms only in terms of iterators.
difference_type - a type that can be used to identify distance between iterators. value_type - the type of the values that can be obtained by dereferencing the iterator. This type is void for output iterators. pointer - defines a pointer to the type iterated over ( value_type )
Yes. The compiler cannot deduce T
from Container<T>::iterator
because it is non-deducible context, which in other words means, given Container<T>::iterator
, the value of T
cannot uniquely and reliably be deduced (see this for detail explanation).
The only solution to this problem is that you've to fully specialize iterator_traits
for each possible value of iterator
which you intend to use in your program. There is no generic solution, as you're not allowed to edit the Container<T>
class template.
Nawaz's answer is likely the right solution for most cases. However, if you're trying to do this for many instantiated SomeContainerFromAThirdPartyLib<T>
classes and only a few functions (or an unknown number of instantiations but a fixed number of functions, as might happen if you're writing your own library), there's another way.
Assume we're given the following (unchangeable) 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
s for iterator_traits
and specialize it to avoid problems with pointers:
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 we want to be able to call with a SomeContainerFromAThirdPartyLib::iterator
, we define an 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);
}
We can then 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 a runnable example with the required include
s and using
s at http://ideone.com/gJyGxU. The output:
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 caveats:
find
, sort
, et cetera). This obviously won't work for functions in algorithm
that haven't been defined yet.In regards to that last one, the question is in which namespace to put the overload (and how to call the std
version). Ideally, it would be in ThirdPartyLib
so that it could be found by argument-dependant lookup, but I've assumed we can't change that. The next best option is in MyLib
, but then the call has to be qualified or preceded by a using
. In either case the end-user should either use using std::count;
or be careful about which calls to qualify with std::
, since if std::count
is mistakenly used with SomeContainerFromAThirdPartyLib::iterator
, it will obviously fail (the whole reason for this exercise).
An alternative that I do not suggest but present here for completeness would be to put it directly in the std
namespace. This would cause undefined behavior; while it might work for you, there's nothing in the standard that guarantees it. If we were specializing count
instead of overloading it, this would be legal.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With