STL iterator/reverse_iterator

[jason]

My question is regaring STL iterator/reverse_iterato r.

I would like to write a function which does the following

int CFoo::calculate (std::vector<in t>::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]

Re: STL iterator/reverse_iterato r

jason schrieb:[color=blue]
> My question is regaring STL iterator/reverse_iterato r.
>
> I would like to write a function which does the following
>
> int CFoo::calculate (std::vector<in t>::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;
> }[/color]

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]

Re: STL iterator/reverse_iterato r

jason wrote:[color=blue]
> My question is regaring STL iterator/reverse_iterato r.
> How should I setup the interface for calculate so that I can do that?[/color]

// "reverse_iterat or" 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]

Re: STL iterator/reverse_iterato r

Greg Buchholz wrote:[color=blue]
> jason wrote:
>[color=green]
>>My question is regaring STL iterator/reverse_iterato r.
>>How should I setup the interface for calculate so that I can do that?[/color]
>
>
> // "reverse_iterat or" 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;
> }
>[/color]
I guess it should be:

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

for non-trivial iterator types.

--
Ian Collins.

[red floyd]

Re: STL iterator/reverse_iterato r

Ian Collins wrote:[color=blue]
> Greg Buchholz wrote:[color=green]
>> jason wrote:
>>[color=darkred]
>>> My question is regaring STL iterator/reverse_iterato r.
>>> How should I setup the interface for calculate so that I can do that?[/color]
>>
>>
>> // "reverse_iterat or" 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;
>> }
>>[/color]
> I guess it should be:
>
> template <typename T>
> int calculate( const T& itBegin, const T& itEnd)
>
> for non-trivial iterator types.
>[/color]

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]

Re: STL iterator/reverse_iterato r

red floyd wrote:[color=blue]
> Ian Collins wrote:
>[color=green]
>> Greg Buchholz wrote:
>>[color=darkred]
>>> jason wrote:
>>>
>>>> My question is regaring STL iterator/reverse_iterato r.
>>>> How should I setup the interface for calculate so that I can do that?
>>>
>>>
>>>
>>> // "reverse_iterat or" 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;
>>> }
>>>[/color]
>> I guess it should be:
>>
>> template <typename T>
>> int calculate( const T& itBegin, const T& itEnd)
>>
>> for non-trivial iterator types.
>>[/color]
>
> 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) .
> }[/color]
No, it is a local:

T it = itBegin;

--
Ian Collins.

[red floyd]

Re: STL iterator/reverse_iterato r

Ian Collins wrote:[color=blue]
> red floyd wrote:[color=green]
>> Ian Collins wrote:[/color][/color]
[redacted][color=blue][color=green][color=darkred]
>>>>
>>> I guess it should be:
>>>
>>> template <typename T>
>>> int calculate( const T& itBegin, const T& itEnd)
>>>
>>> for non-trivial iterator types.
>>>[/color]
>>
>> 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) .
>> }[/color]
> No, it is a local:
>
> T it = itBegin;
>[/color]

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

[Ian Collins]

Re: STL iterator/reverse_iterato r

red floyd wrote:[color=blue][color=green][color=darkred]
>>>>>
>>>> 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) .
>>> }[/color]
>>
>> No, it is a local:
>>
>> T it = itBegin;
>>[/color]
>
> At which point you have the same overhead as if you had passed it by
> value. What's the point?[/color]

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.

--
Ian Collins.

[Pete Becker]

Re: STL iterator/reverse_iterato r

Ian Collins wrote:[color=blue]
>
> Well, the parameters should be const, any advantage of passing by
> reference depends on how complicated the iterator object is.
>[/color]

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

--

Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)

[Kai-Uwe Bux]

Re: STL iterator/reverse_iterato r

Pete Becker wrote:
[color=blue]
> Ian Collins wrote:[color=green]
>>
>> Well, the parameters should be const, any advantage of passing by
>> reference depends on how complicated the iterator object is.
>>[/color]
>
> Iterators should be small enough that passing by value is appropriate.
> All of the algorithms in the standard library do it that way.[/color]

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]

Re: STL iterator/reverse_iterato r

Kai-Uwe Bux wrote:[color=blue]
> Pete Becker wrote:
>
>[color=green]
>>Ian Collins wrote:
>>[color=darkred]
>>>Well, the parameters should be const, any advantage of passing by
>>>reference depends on how complicated the iterator object is.
>>>[/color]
>>
>>Iterators should be small enough that passing by value is appropriate.
>>All of the algorithms in the standard library do it that way.[/color]
>
>
> 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.
>
>[/color]

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.

--

Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)

[Daniel T.]

Re: STL iterator/reverse_iterato r

In article <D2UBf.332$RC1. 101@fe05.lga>,
"jason" <jasonsmith008@ charter.net> wrote:
[color=blue]
> My question is regaring STL iterator/reverse_iterato r.
>
> I would like to write a function which does the following
>
> int CFoo::calculate (std::vector<in t>::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?[/color]

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<in t>() ).result() );

Or we can be *really* clever!

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


--
Magic depends on tradition and belief. It does not welcome observation,
nor does it profit by experiment. On the other hand, science is based
on experience; it is open to correction by observation and experiment.

[Ian Collins]

Re: STL iterator/reverse_iterato r

Pete Becker wrote:[color=blue]
> Ian Collins wrote:
>[color=green]
>>
>> Well, the parameters should be const, any advantage of passing by
>> reference depends on how complicated the iterator object is.
>>[/color]
>
> Iterators should be small enough that passing by value is appropriate.
> All of the algorithms in the standard library do it that way.
>[/color]
Which make the use of const irrelevant. I'll go away now....

--
Ian Collins.

[Daniel T.]

Re: STL iterator/reverse_iterato r

In article <1138323387.827 127@drone2-svc-skyt.qsi.net.nz >,
Ian Collins <ian-news@hotmail.co m> wrote:
[color=blue]
> Pete Becker wrote:[color=green]
> > Ian Collins wrote:
> >[color=darkred]
> >>
> >> Well, the parameters should be const, any advantage of passing by
> >> reference depends on how complicated the iterator object is.
> >>[/color]
> >
> > Iterators should be small enough that passing by value is appropriate.
> > All of the algorithms in the standard library do it that way.
> >[/color]
> Which make the use of const irrelevant. I'll go away now....[/color]

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. :-)