Sign in to follow this  
coordz

[C++] function to take both iterator and reverse_iterator

Recommended Posts

I've written a function to operate on a range like this
template <typename T> vector<T> myFunc(
    const typename vector< vector<T> >::const_iterator &beginIter,
    const typename vector< vector<T> >::const_iterator &endIter );
which works fine when passing normal forward iterators. When I try to pass reverse iterators I get an (expected) compile error. How do I define my function to take either forward or reverse iterators? Is there a base class that both forward and reverse iterators are derived from? Or do I need to further template my function to accept the two types of iterators? TIA

Share this post


Link to post
Share on other sites
You shouldn't care what kind of iterator you get, from a vector or not:

template <typename Iterator>
vector<typename Iterator::value_type> myFunc(Iterator begin, Iterator end)
{
// ...
}



This makes your function more general (the whole point of templates), because it can take user defined iterators. You could even template the return type, allowing greater flexibility.

Share this post


Link to post
Share on other sites
Quote:
Original post by coordz
I've written a function to operate on a range like this
template <typename T> vector<T> myFunc(
const typename vector< vector<T> >::const_iterator &beginIter,
const typename vector< vector<T> >::const_iterator &endIter );

rip-off has a good solution for you already, so I am going to go out on a limb and ask why you want to be returning a std::vector? Unless this is a factory function to initialise vectors, it might be better to operate in place, ala std::copy.

Share this post


Link to post
Share on other sites
I don't want to make the function any more generic than it is as it does not make sense for it to operate on anything other than a vector< vector<> >. To be brief, the function selects a path through a 2D grid of T and returns this path as a vector. I just want to be able to do a forward path and reverse path easily.

Share this post


Link to post
Share on other sites
You already have your answer:


template <typename T, typename Iter>
vector<T> myFunc(Iter beginIter, Iter endIter);

Share this post


Link to post
Share on other sites
Quote:
Original post by rip-off
You shouldn't care what kind of iterator you get, from a vector or not:
*** Source Snippet Removed ***

This makes your function more general (the whole point of templates), because it can take user defined iterators. You could even template the return type, allowing greater flexibility.


Not all iterators provide the same level of functionality. What if myFunc uses some functionality of a random access iterator for instance which is not supported by a forward iterator? This contradicts your initial goal of making this function general.

Share this post


Link to post
Share on other sites
Quote:
Original post by Ashkan
Not all iterators provide the same level of functionality. What if myFunc uses some functionality of a random access iterator for instance which is not supported by a forward iterator?

If you pass a forward iterator and your function expects a random access iterator, then you will get a compile time error immediately. Because it is a templated function, the compiler will discover immediately that the passed iterator has no random access functionality.

Share this post


Link to post
Share on other sites
Quote:
Original post by swiftcoder
Quote:
Original post by Ashkan
Not all iterators provide the same level of functionality. What if myFunc uses some functionality of a random access iterator for instance which is not supported by a forward iterator?

If you pass a forward iterator and your function expects a random access iterator, then you will get a compile time error immediately. Because it is a templated function, the compiler will discover immediately that the passed iterator has no random access functionality.


Exactly my point. Then what's the point of making this function general? Why not pass a random access iterator in the first place?

Share this post


Link to post
Share on other sites
A lot of functions in the STL only support certain types of iterators, so while this function could be made more generic, it is not necessarily the right approach in all situations.

Reverse iterators have a base() method, which returns the corresponding iterator for the given range. That may be what you need to look into if you want to use the function as-is (though you may have to change the const_iterators to iterators).

Excellent article on this right here (specifically point 3 in your case)
Dr. Dobb's - Three Guidelines for Effective Iterator Usage

Share this post


Link to post
Share on other sites
Quote:
Original post by Ashkan
Not all iterators provide the same level of functionality. What if myFunc uses some functionality of a random access iterator for instance which is not supported by a forward iterator? This contradicts your initial goal of making this function general.


Since the OP didn't specify what the function was to do initially, I went for the most general one. People often over-specify template functions when there is a more general alternative available.

Besides, had the OP used a random access iterator specific construct (such as begin + 5) the compiler would reject an instantiation of the template for non random access iterator types, which is fine.

Share this post


Link to post
Share on other sites
Quote:
Exactly my point. Then what's the point of making this function general? Why not pass a random access iterator in the first place?


The point is that writing the function to work with any random access iterator is easier and simpler than writing the function just for vector::iterator and vector::const_iterator.

Share this post


Link to post
Share on other sites
Quote:
Original post by Ashkan
Exactly my point. Then what's the point of making this function general? Why not pass a random access iterator in the first place?

There is no single template argument you can use that specifies only random access iterators. You can add conditions in the function body to cause a compiler error if the type parameter is not a random access iterator, but that has the exact same effect as using random access iterator functionality that isn't in other iterator classes.

Share this post


Link to post
Share on other sites
Quote:
Original post by Nitage
You already have your answer:


template <typename T, typename Iter>
vector<T> myFunc(Iter beginIter, Iter endIter);

As I understand things this makes the function so general that I could pass in anything, even int's and float's. I assume from the discussion so far there is no way to limit what Iter can be? And that iterator and reverse_iterator do not have a common parent? Some sort of common parent would be ideal for my purpose.

Share this post


Link to post
Share on other sites
Quote:
Original post by SiCrane
Quote:
Original post by Ashkan
Exactly my point. Then what's the point of making this function general? Why not pass a random access iterator in the first place?

There is no single template argument you can use that specifies only random access iterators. You can add conditions in the function body to cause a compiler error if the type parameter is not a random access iterator, but that has the exact same effect as using random access iterator functionality that isn't in other iterator classes.


Yes, you're right. It was a mistake on my part.

Share this post


Link to post
Share on other sites
Quote:
Original post by coordz
Quote:
Original post by Nitage
You already have your answer:


template <typename T, typename Iter>
vector<T> myFunc(Iter beginIter, Iter endIter);

As I understand things this makes the function so general that I could pass in anything, even int's and float's. I assume from the discussion so far there is no way to limit what Iter can be? And that iterator and reverse_iterator do not have a common parent? Some sort of common parent would be ideal for my purpose.


Techinically yes, but you will likely write the function so that things like floats and ints will fail to compile. For instance, if you use the dereference operator then you will get a compile time error on ints and floats. In fact, the only data types that really support that operator are pointers and iterators. You've narrowed down the number of datatypes that can be used in your function successfully a great deal. As long as the container supports the functionality you desire you'll be fine.

Share this post


Link to post
Share on other sites
And one final question...... I understand this bit of code as it's just adding Iter to represent some iterator.
template <typename T, typename Iter>
vector<T> myFunc(Iter beginIter, Iter endIter);

I don't understand how this code
template <typename Iterator>
vector<typename Iterator::value_type> myFunc(Iterator begin, Iterator end)

is equivalent. Specifically, what is Iterator::value_type?

Share this post


Link to post
Share on other sites
Quote:
Original post by coordz
And one final question...... I understand this bit of code as it's just adding Iter to represent some iterator.
template <typename T, typename Iter>
vector<T> myFunc(Iter beginIter, Iter endIter);

I don't understand how this code
template <typename Iterator>
vector<typename Iterator::value_type> myFunc(Iterator begin, Iterator end)

is equivalent. Specifically, what is Iterator::value_type?


Iterator::value_type is the type of the value that dereferencing the iterator would give you, although using iterator_traits<Iterator>::value_type would be better.

You can also use Boost.Concepts to define what type of iterators you require.


template <typename ForwardIterator>
vector<typename iterator_traits<ForwardIterator>::value_type> foo(ForwardIterator start, ForwardIterator end)
{
boost::function_requires<boost::ForwardIteratorConcept<ForwardIterator> >();
// ...
}


Share this post


Link to post
Share on other sites
Quote:
Original post by mfawcett
Quote:
Original post by coordz
template <typename Iterator>
vector<typename Iterator::value_type> myFunc(Iterator begin, Iterator end)

is equivalent. Specifically, what is Iterator::value_type?


Iterator::value_type is the type of the value that dereferencing the iterator would give you, although using iterator_traits<Iterator>::value_type would be better.


This is also a handy way of disallowing regular pointers to be passed as iterators, as they of course do not have a value_type defined.

Share this post


Link to post
Share on other sites
Depends on your definition of "handy". It will disable the use of a pointer; however, a maintainer will probably assume that you just didn't use iterator_traits as a mistake and change it if they want a pointer. If you want to disable the use of a pointer it'd be better to do something like BOOST_STATIC_ASSERT(!boost::is_pointer<Iterator>::value) in the function body.

Share this post


Link to post
Share on other sites
Actually I was providing that as a handy way *to* allow use of a pointer type. Part of the reason iterator_traits exists is to allow pointer types to have extra information associated with them, since you obviously can't insert a typedef into a pointer type to make Iterator::value_type work.

iterator_traits<int *>::value_type
is int.
int *::value_type
doesn't compile.

Share this post


Link to post
Share on other sites
Quote:
Original post by coordz
I don't want to make the function any more generic than it is as it does not make sense for it to operate on anything other than a vector< vector<> >. To be brief, the function selects a path through a 2D grid of T and returns this path as a vector. I just want to be able to do a forward path and reverse path easily.


1) A vector of vectors is not a 2D grid. It is, well, a vector of vectors. Each vector represents a "row" of what you intend to interpret as a "grid", but each of them has a separate length count and can be resized separately.

2) Consequently, an iterator over a vector of vectors doesn't iterate over elements of a 2D grid; it iterates over the rows. Because "vector of T" is the element type of the outer vector ("vector of vector of T") that you're iterating over.

3) Consequently, if you want to iterate over rows, you'll have to construct the iterators yourself.

4) The whole point of this polymorphism stuff is that you're not supposed to care if you got passed a forward iterator or a reverse iterator. If you just ask for an iterator, you're not going to have a good way of finding out the direction. So you can't implement the logic that says "iterate within the row backwards if and only if we were asked to iterate over the rows backwards".

5) Assuming that's even what you want. How are you "finding a path" through the "grid", anyway?

6) That's making things too complicated, regardless. To find the reverse path, all you need to do is call the function that finds a forward path, and iterate over the returned path in reverse.

Share this post


Link to post
Share on other sites
Quote:
Original post by mfawcett
Actually I was providing that as a handy way *to* allow use of a pointer type. Part of the reason iterator_traits exists is to allow pointer types to have extra information associated with them, since you obviously can't insert a typedef into a pointer type to make Iterator::value_type work.

Ja, yours works for that - rip-off's original code didn't support pointers however.

Share this post


Link to post
Share on other sites
Quote:
Original post by swiftcoder
Quote:
Original post by mfawcett
Actually I was providing that as a handy way *to* allow use of a pointer type. Part of the reason iterator_traits exists is to allow pointer types to have extra information associated with them, since you obviously can't insert a typedef into a pointer type to make Iterator::value_type work.

Ja, yours works for that - rip-off's original code didn't support pointers however.


I know that now. This is why I visit gamedev, I still learn stuff every week. Today: iterator_traits. [grin]

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this