STL iterator/reverse_iterator

[jason]

My question is regaring STL iterator/reverse_iterator.

I would like to write a function which does the following

int CFoo::calculate(std::vector<int>::iterator itBegin,
std::vector<int>::iterator itEnd)
{
int nWSum = 0;
std::vector<int>::iterator it = itBegin;
for (int i = 1; it != itEnd; ++it, ++i)
{
nWSum += i*(*it);
}

return nWSum;
}

Ideally, I would like to pass in the forward iterator or the reverse
iterator for the vector (the weighted sum will be different for each).

int nSum1 = oCFoo.calculate(vecA.begin(), vecA.end());
int nSum2 = oCFoo.calculate(vecA.rbegin(), vecA.rend());

How should I setup the interface for calculate so that I can do that?

Thanks.

 

[Thomas J. Gritzan]

My question is regaring STL iterator/reverse_iterator.

I would like to write a function which does the following

int CFoo::calculate(std::vector<int>::iterator itBegin,
std::vector<int>::iterator itEnd)
{
int nWSum = 0;
std::vector<int>::iterator it = itBegin;
for (int i = 1; it != itEnd; ++it, ++i)
{
nWSum += i*(*it);
}

return nWSum;
}

template <class InputIterator>
int CFoo::for_each(InputIterator first, InputIterator last)
{
int nWSum = 0;
InputIterator it = first;
for (int i = 1; it != last; ++it, ++i)
{
nWSum += i*(*it);
}

return nWSum;
}

 

[Greg Buchholz]

My question is regaring STL iterator/reverse_iterator.
How should I setup the interface for calculate so that I can do that?

// "reverse_iterator" is a different type than "iterator". Use a
// template parameter, and as a bonus, it'll now work for
// more than just vectors. ("int" might not be the best to
// use for a return type though...)

template<class T>
int calculate(T itBegin,T itEnd)
{
int nWSum = 0;
T it = itBegin;
for (typename iterator_traits<T>::difference_type i = 1;
it != itEnd; ++it, ++i)
{
nWSum += i*(*it);
}

return nWSum;
}

 

[Ian Collins]

// "reverse_iterator" is a different type than "iterator". Use a
// template parameter, and as a bonus, it'll now work for
// more than just vectors. ("int" might not be the best to
// use for a return type though...)

template<class T>
int calculate(T itBegin,T itEnd)
{
int nWSum = 0;
T it = itBegin;
for (typename iterator_traits<T>::difference_type i = 1;
it != itEnd; ++it, ++i)
{
nWSum += i*(*it);
}

return nWSum;
}

I guess it should be:

template <typename T>
int calculate( const T& itBegin, const T& itEnd)

for non-trivial iterator types.

 

[red floyd]

I guess it should be:

template <typename T>
int calculate( const T& itBegin, const T& itEnd)

for non-trivial iterator types.

How do you increment the iterator? it++ will fail!

Consider

void f(const int& i)
{
++i; // bad: i references a *CONST* int.
}

Similarly,

void f(const std::vector<int>::iterator & it)
{
++it; // bad: it references a const iterator (not a const_iterator).
}

 

[Ian Collins]

How do you increment the iterator? it++ will fail!

Consider

void f(const int& i)
{
++i; // bad: i references a *CONST* int.
}

Similarly,

void f(const std::vector<int>::iterator & it)
{
++it; // bad: it references a const iterator (not a const_iterator).
}

No, it is a local:

T it = itBegin;

 

[red floyd]

Ian Collins wrote: [redacted]

I guess it should be:

template <typename T>
int calculate( const T& itBegin, const T& itEnd)

for non-trivial iterator types.

How do you increment the iterator? it++ will fail!

Consider

void f(const int& i)
{
++i; // bad: i references a *CONST* int.
}

Similarly,

void f(const std::vector<int>::iterator & it)
{
++it; // bad: it references a const iterator (not a const_iterator).
}

No, it is a local:

T it = itBegin;

At which point you have the same overhead as if you had passed it by
value. What's the point?

 

[Ian Collins]

At which point you have the same overhead as if you had passed it by
value. What's the point?

Well, the parameters should be const, any advantage of passing by
reference depends on how complicated the iterator object is. At least
passing be reference only results in one copy, the end iterator is
neither copied or modified.

 

[Pete Becker]

Well, the parameters should be const, any advantage of passing by
reference depends on how complicated the iterator object is.

Iterators should be small enough that passing by value is appropriate.
All of the algorithms in the standard library do it that way.

 

[Kai-Uwe Bux]

Iterators should be small enough that passing by value is appropriate.
All of the algorithms in the standard library do it that way.

For tree like data structures, you face an alternative: small iterators
would usually be pointers to nodes. To move in the tree, you need a
parentpointer at each node. Alternatively, you could abandon parent
pointers; but then, iterators would encode a path from the root to the
node. In this case, it is a little more tricky to come up with an
implementation for the iterators that supports fast copy construction and
assignment.

Sometimes you cannot have parent pointers in your tree because different
trees might share nodes: consider for instance that interesting rope thing
that HP/SGI had in their STL implementation.


Best

Kai-Uwe Bux

 

[Pete Becker]

Pete Becker wrote:




For tree like data structures, you face an alternative: small iterators
would usually be pointers to nodes. To move in the tree, you need a
parentpointer at each node. Alternatively, you could abandon parent
pointers; but then, iterators would encode a path from the root to the
node. In this case, it is a little more tricky to come up with an
implementation for the iterators that supports fast copy construction and
assignment.

Sometimes you cannot have parent pointers in your tree because different
trees might share nodes: consider for instance that interesting rope thing
that HP/SGI had in their STL implementation.

Nevertheless, STL passes iterators by value. If you have specialized
iterators that can't be passed efficiently by value you cannot use them
with standard algorithms.

 

[Daniel T.]

My question is regaring STL iterator/reverse_iterator.

I would like to write a function which does the following

int CFoo::calculate(std::vector<int>::iterator itBegin,
std::vector<int>::iterator itEnd)
{
int nWSum = 0;
std::vector<int>::iterator it = itBegin;
for (int i = 1; it != itEnd; ++it, ++i)
{
nWSum += i*(*it);
}

return nWSum;
}

Ideally, I would like to pass in the forward iterator or the reverse
iterator for the vector (the weighted sum will be different for each).

int nSum1 = oCFoo.calculate(vecA.begin(), vecA.end());
int nSum2 = oCFoo.calculate(vecA.rbegin(), vecA.rend());

How should I setup the interface for calculate so that I can do that?

Do it like the standard library does it.

template < typename T >
typename T::value_type calc2( T begin, T end ) {
typename T::value_type result = 0;
int i = 1;
while ( begin != end )
result += i++ * (*begin++);
return result;
}

The above has the added bonus of being usable with any container type
(const or non-const) and any value type (that can handle '+=' and '*').

Now let's have some fun! Why re-invent the loop?

template < typename T >
class weighted_sum {
T _result;
int _count;
public:
weighted_sum():_result( 0 ), _count( 1 ) { }
T operator()( T i ) {
_result += _count++ * i;
return _result;
}
T result() const { return _result; }
};


The above can be used thusly:

vector<int> test;
// ...
int forward_result =
for_each( test.begin(), test.end(), weighted_sum<int>() ).result() );

Or we can be *really* clever!

vector< int > results;
transform( test.begin(), test.end(), back_inserter(results),
weighted_sum<int>() );

 

[Ian Collins]

Iterators should be small enough that passing by value is appropriate.
All of the algorithms in the standard library do it that way.

Which make the use of const irrelevant. I'll go away now....

 

[Daniel T.]

Which make the use of const irrelevant. I'll go away now....

Since you have to copy the first iterator, passing it in by const ref
doesn't help you at all, better would be to pass by value and not bother
making a copy. I could see accepting the end iterator by const ref
though... Call this a compromise between the two of you.