How to write previous element in STL list

[cornelis van der bent]

In my code I want to go through all combinations of two items in a
list. Here is my code:

list<Instance*>::iterator i;
for (i = instances.begin(); i != --instances.end(); i++)
{
list<Instance*>::iterator j;
for (j = i + 1; j < instances.end(); j++)
{
// Do something!
}
}

I get a big error message at i + 1. I got a similar message when I
wrote
i != instances.end() -1, but fixed this by writing --instances.end().

My question what must I write instead of i + 1?

Thanks for listening!

Kees

 

[Victor Bazarov]

In my code I want to go through all combinations of two items in a
list. Here is my code:

list<Instance*>::iterator i;
for (i = instances.begin(); i != --instances.end(); i++)
{
list<Instance*>::iterator j;
for (j = i + 1; j < instances.end(); j++)
{
// Do something!
}
}

I get a big error message at i + 1.

Such an operation is only defined for random-access iterators, and the
list iterator isn't one.

> I got a similar message when I
wrote
i != instances.end() -1, but fixed this by writing --instances.end().

My question what must I write instead of i + 1?

Duplicate it and increment. Something like

// presume the list does not change
list<Instance*>::iterator i = instances.begin(),
last = --instances.end(),
e = instances.end();
for (; i != last; ++i)
{
list<Instance*>::iterator j = i;
while (++j != e)
{
// Do something
}
}

V

 

[Pascal J. Bourguignon]

In my code I want to go through all combinations of two items in a
list. Here is my code:

list<Instance*>::iterator i;
for (i = instances.begin(); i != --instances.end(); i++)
{
list<Instance*>::iterator j;
for (j = i + 1; j < instances.end(); j++)
{
// Do something!
}
}

I get a big error message at i + 1. I got a similar message when I
wrote
i != instances.end() -1, but fixed this by writing --instances.end().

My question what must I write instead of i + 1?

j=i; j++; seems to work.

Thanks for listening!

------------------------------------------------------------------------

#include <list>
#include <iostream>

typedef int Instance;

void process(Instance a,Instance b){
std::cout<<a<<" "<<b<<std::endl;
}

int main(){
Instance init[5]={1,2,3,4,5};
std::list<Instance> instances(5);
std::copy(init,init+5,instances.begin());

std::list<Instance>::iterator i=instances.begin();
while(i!=instances.end()){
std::list<Instance>::iterator j=i;
j++;
while(j!=instances.end()){
process(*i,*j);
j++;
}
i++;
}
return(0);
}

/*
-*- mode: compilation; default-directory: "/tmp/" -*-
Compilation started at Mon Jul 27 17:46:40

SRC="/tmp/l.c++" ; EXE="l" ; g++ -g3 -ggdb3 -o ${EXE} ${SRC} && ./${EXE} && echo status = $?
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5
status = 0

Compilation finished at Mon Jul 27 17:46:40
*/

 

[Victor Bazarov]

j=i; j++; seems to work. .. ^^^

Advice: prefer pre-increment over post-increment *for iterators*.

V

 

[cornelis van der bent]

Such an operation is only defined for random-access iterators, and the
list iterator isn't one.

Do you know reason(s) why this has nog been implemented for a list?
The list is doubly-linked, so giving back an iterator one postion
earlier/further does not seem to be a big deal.

Thanks for the insight! I used a vector instead.

 

[Victor Bazarov]

Do you know reason(s) why this has nog been implemented for a list?

My guess would be because addition is slow and implementing it would
just tempt folks to use it with unfortunate performance impacts.

The list is doubly-linked, so giving back an iterator one postion
earlier/further does not seem to be a big deal.

Yes, but the compiler does not need to recognize that the value you're
adding or subtracting from the iterator is '1'. It sees the addition or
the subtraction and needs to resolve it. It can't. No compiler I know
would convert (a+1) into anything except operator+(a,1) for user-defined
types.

Thanks for the insight! I used a vector instead.

It's probably easier to use indices with the vector instead of iterators.

[..]

V

 

[Rolf Magnus]

Do you know reason(s) why this has nog been implemented for a list?
The list is doubly-linked, so giving back an iterator one postion
earlier/further does not seem to be a big deal.

One position not, that's why there are increment/decrement operators, but
you cannot define addition/subtraction operators that only work with the
value 1. They would have to be usable with any value, and adding e.g. a
million to such an iterator (provied that the list has that many elements
elements) would be possible, but very slow.

 

[cornelis van der bent]

cornelis van der bent wrote:







One position not, that's why there are increment/decrement operators, but
you cannot define addition/subtraction operators that only work with the
value 1. They would have to be usable with any value, and adding e.g. a
million to such an iterator (provied that the list has that many elements
elements) would be possible, but very slow.- Tekst uit oorspronkelijk bericht niet weergeven -

- Tekst uit oorspronkelijk bericht weergeven -

I agree that in language design you could leave out useless (e.g. due
to low performance) constructions. On the other hand having uniform
interfaces as much as possible has its virtues too. If it would be
possible to implement list<T>::iterator + N, I think I would choose to
do so and leave the performance issues to the user.

 

[James Kanze]

Do you know reason(s) why this has nog been implemented for a
list? The list is doubly-linked, so giving back an iterator
one postion earlier/further does not seem to be a big deal.

But operator+ isn't limited to adding one. Operator+ is defined
when it can be done in constant time; with list, it requires
linear time (with regards to what is being added).

One simple solution would be to define functions succ and prec:

template< typename ForwardIterator >
ForwardIterator
succ( ForwardIterator i )
{
++ i ;
return i ;
}

template< typename BidirectionalIterator >
BidirectionalIterator
prec( BidirectionalIterator i )
{
-- i ;
return i ;
}

More generally, one does wonder why std::advance takes a
reference to the iterator and updates it, rather than taking an
iterator, and returning the modified iterator.

 

[Richard Herring]

In message

I agree that in language design you could leave out useless (e.g. due
to low performance) constructions. On the other hand having uniform
interfaces as much as possible has its virtues too. If it would be
possible to implement list<T>::iterator + N, I think I would choose to
do so and leave the performance issues to the user.

Which is no doubt why the uniform interface provided by std::advance is
available. It can be applied to input, forward, bidirectional and
random-access iterators, N can be negative for bidirectional and
random-access, and performance depends on the iterator type.

 

[Pascal J. Bourguignon]

I agree that in language design you could leave out useless (e.g. due
to low performance) constructions. On the other hand having uniform
interfaces as much as possible has its virtues too. If it would be
possible to implement list<T>::iterator + N, I think I would choose to
do so and leave the performance issues to the user.

It's one aspect of the stl library, that it specifies time (and
sometimes space) complexity limits that must be fulfilled for most
methods by any implementation of the library.

So in a way, performance issues are not left to the user, they're
taken in charge by the stl which gives some guarantees in this
respect.


I don't know if the C++ standard does the same about operators such as
+, but indeed it might be expect that + is a O(1) operation.

However, would this mean that operator+ cannot be overriden for string
concatenation or bignum sum (much less matrix sum)? I don't think so,
therefore in this case, I'd tend to agree that it would be nice to use
this operator for advance. If course, if C++ language lawyers tell us
that operator+ must stay O(1) and forbid it for bignums and matrix,
etc, then I'd gladly concede that operator+ shall not be used for
advance.

 

[Pascal J. Bourguignon]

Advice: prefer pre-increment over post-increment *for iterators*.

Right. Old habits...

 

[Juha Nieminen]

I don't know if the C++ standard does the same about operators such as
+, but indeed it might be expect that + is a O(1) operation.

You can write your own operator+ for your list iterators if you want.
There's nothing stopping you. (Except that I think you can't template
operator overloads, which is a bit of a bummer, but you can overload the
operator for specific list types.)

 

[James Kanze]

You can write your own operator+ for your list iterators if
you want. There's nothing stopping you. (Except that I think
you can't template operator overloads, which is a bit of a
bummer, but you can overload the operator for specific list
types.)

Operator overloads can be template functions; there's no problem
there. The problem for operator+ on an std::list::iterator is
that if you try to write:

template< typename T >
typename std::list< T >::iterator
operator+(
typename std::list< T >::iterator
lhs,
int rhs )
{
std::advance( lhs, rhs ) ;
return lhs ;
}

, T is in a non-deduced context, which means that template
argument deduction fails, and no instantiation of the template
is added to the overload set. (You can, of course, still call
it with ":perator+<int>( i, 3 )", but that sort of defeats the
purpose of operator overloading.) And if you just write:

template< typename T >
T
operator+(
T lhs,
int rhs )
{
std::advance( lhs, rhs ) ;
return lhs ;
}

, you're going to match a lot of things you don't want it to
match, and probably cause problems elsewhere (ambiguous
overloads, or it might even be a better match than the intended
operator).

 

[Juha Nieminen]

Operator overloads can be template functions; there's no problem
there. The problem for operator+ on an std::list::iterator is
that if you try to write:

template< typename T >
typename std::list< T >::iterator
operator+(
typename std::list< T >::iterator
lhs,
int rhs )
{
std::advance( lhs, rhs ) ;
return lhs ;
}

, T is in a non-deduced context, which means that template
argument deduction fails, and no instantiation of the template
is added to the overload set. (You can, of course, still call
it with ":perator+<int>( i, 3 )", but that sort of defeats the
purpose of operator overloading.) And if you just write:

template< typename T >
T
operator+(
T lhs,
int rhs )
{
std::advance( lhs, rhs ) ;
return lhs ;
}

, you're going to match a lot of things you don't want it to
match, and probably cause problems elsewhere (ambiguous
overloads, or it might even be a better match than the intended
operator).

I suppose there is no way of implementing this in a templated way?

(I wonder if concepts would have helped doing this, if they had been
included in the next standard. Or were concepts usable purely for
compile-time diagnostics?)