removing elements from vector<int> using <algorithm>

[arnuld]

WANTED:

/* C++ Primer - 4/e
*
* Exercise: 9.26
* STATEMENT
* Using the following definition of ia, copy ia into a vector and
into a list. Use the single iterator form of erase to remove the
elements with odd values from your list * and the even values from your
vector.

int ia[] = { 0, 1, 1, 2, 3, 5, 8, 13, 21, 55, 89 };
*
*/


WHAT I GET:

/home/arnuld/programming/c++ $ g++ -ansi -pedantic -Wall -Wextra
ex_09.26.cpp ex_09.26.cpp:

In function 'int main()': ex_09.26.cpp:43:
error: '_1' was not declared in this scope /home/arnuld/programming/c++ $



CODE:

#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
#include <iterator>


int main()
{
int ia[] = { 0, 1, 1, 2, 3, 5, 8, 13, 21, 55, 89 };
const size_t ia_size = sizeof( ia ) / sizeof( *ia );

/* I made this array behave like a container:
"ia_begin" is the pointer to 1st element of ia
"ia_end" is the pointer to one past the last element of ia
*/
int *ia_begin = ia;
int *ia_end = ia + ia_size;

std::vector<int> ivec;
std::list<int> ilist;

/* copy elements from array to vector & list */
std::copy( ia_begin, ia_end, std::back_inserter( ivec ) );
std::copy( ia_begin, ia_end, std::back_inserter( ilist ) );


std::remove_if( ivec.begin(),
ivec.end(),
_1 % 2 == 0 );

/* print out the values */
std::copy( ivec.begin(), ivec.end(),
std:stream_iterator<int> (std::cout, "\n" ) );

return 0;
}



I am just trying to use Lambda from Std. Lib. Why it is the problem ?



-- arnuld
http://lispmachine.wordpress.com

 

[Jim Langston]

WANTED:

/* C++ Primer - 4/e
*
* Exercise: 9.26
* STATEMENT
* Using the following definition of ia, copy ia into a vector and
into a list. Use the single iterator form of erase to remove the
elements with odd values from your list * and the even values from your
vector.

int ia[] = { 0, 1, 1, 2, 3, 5, 8, 13, 21, 55, 89 };
*
*/


WHAT I GET:

/home/arnuld/programming/c++ $ g++ -ansi -pedantic -Wall -Wextra
ex_09.26.cpp ex_09.26.cpp:

In function 'int main()': ex_09.26.cpp:43:
error: '_1' was not declared in this scope /home/arnuld/programming/c++ $



CODE:

#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
#include <iterator>


int main()
{
int ia[] = { 0, 1, 1, 2, 3, 5, 8, 13, 21, 55, 89 };
const size_t ia_size = sizeof( ia ) / sizeof( *ia );

/* I made this array behave like a container:
"ia_begin" is the pointer to 1st element of ia
"ia_end" is the pointer to one past the last element of ia
*/
int *ia_begin = ia;
int *ia_end = ia + ia_size;

std::vector<int> ivec;
std::list<int> ilist;

/* copy elements from array to vector & list */
std::copy( ia_begin, ia_end, std::back_inserter( ivec ) );
std::copy( ia_begin, ia_end, std::back_inserter( ilist ) );


std::remove_if( ivec.begin(),
ivec.end(),
_1 % 2 == 0 );

/* print out the values */
std::copy( ivec.begin(), ivec.end(),
std:stream_iterator<int> (std::cout, "\n" ) );

return 0;
}

I am just trying to use Lambda from Std. Lib. Why it is the problem ?

You might want to re-read your homework assignment again. "... Use the
single iterator form of erase to remove the elements..." I don't believe
std::remove_if qualifies as erase. I believe the instructor may be looking
for ivec.erase( iterator ); but this is just how I read it.

 

[Guest]

WANTED:

/* C++ Primer - 4/e
*
* Exercise: 9.26
* STATEMENT
* Using the following definition of ia, copy ia into a vector and
into a list. Use the single iterator form of erase to remove the
elements with odd values from your list * and the even values from your
vector.

int ia[] = { 0, 1, 1, 2, 3, 5, 8, 13, 21, 55, 89 };
*
*/


WHAT I GET:

/home/arnuld/programming/c++ $ g++ -ansi -pedantic -Wall -Wextra
ex_09.26.cpp ex_09.26.cpp:

In function 'int main()': ex_09.26.cpp:43:
error: '_1' was not declared in this scope /home/arnuld/programming/c++ $



CODE:

#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
#include <iterator>


int main()
{
int ia[] = { 0, 1, 1, 2, 3, 5, 8, 13, 21, 55, 89 };
const size_t ia_size = sizeof( ia ) / sizeof( *ia );

/* I made this array behave like a container:
"ia_begin" is the pointer to 1st element of ia
"ia_end" is the pointer to one past the last element of ia
*/
int *ia_begin = ia;
int *ia_end = ia + ia_size;

std::vector<int> ivec;
std::list<int> ilist;

/* copy elements from array to vector & list */
std::copy( ia_begin, ia_end, std::back_inserter( ivec ) );
std::copy( ia_begin, ia_end, std::back_inserter( ilist ) );


std::remove_if( ivec.begin(),
ivec.end(),
_1 % 2 == 0 );

/* print out the values */
std::copy( ivec.begin(), ivec.end(),
std:stream_iterator<int> (std::cout, "\n" ) );

return 0;
}



I am just trying to use Lambda from Std. Lib. Why it is the problem ?

First, there is not lambda in the standard library (at least not yet,
they might add it in the next version) and second, you are trying to use
the boos lambda, but have not included any boost headers.

By the way, the assignment wants you to use erase() (not sure if they
meant std::erase or std::vector<T>::erase(), I suspect the latter).

 

[Michael DOUBEZ]

arnuld a écrit :

WANTED:

/* C++ Primer - 4/e
*
* Exercise: 9.26
* STATEMENT
* Using the following definition of ia, copy ia into a vector and
into a list. Use the single iterator form of erase to remove the
elements with odd values from your list * and the even values from your
vector.

int ia[] = { 0, 1, 1, 2, 3, 5, 8, 13, 21, 55, 89 };
*
*/


WHAT I GET:

/home/arnuld/programming/c++ $ g++ -ansi -pedantic -Wall -Wextra
ex_09.26.cpp ex_09.26.cpp:

In function 'int main()': ex_09.26.cpp:43:
error: '_1' was not declared in this scope /home/arnuld/programming/c++ $
[snip]
std::remove_if( ivec.begin(),
ivec.end(),
_1 % 2 == 0 );

[snip]

I am just trying to use Lambda from Std. Lib. Why it is the problem ?

There is no lambda in STL (for now).
Instead, you can use the std::modulus<> functor together with
std::bind2nd().

Michael

 

[arnuld]

First, there is not lambda in the standard library (at least not yet,
they might add it in the next version) and second, you are trying to use
the boos lambda, but have not included any boost headers.

OK, I will not use BOOST for now.

By the way, the assignment wants you to use erase() (not sure if they
meant std::erase or std::vector<T>::erase(), I suspect the latter).

I tried it with vector's erase member function but that falls into the
infinite loop:


void rem_evens( std::vector<int>& ivec)
{
std::vector<int>::iterator begin = ivec.begin();
std::vector<int>::iterator end = ivec.end();

while( begin != end )
{
if( (*begin % 2) == 0 )
{
begin++ = ivec.erase( begin );
}
end = ivec.end();
}

}



int main()
{
int ia[] = { 0, 1, 1, 2, 3, 5, 8, 13, 21, 55, 89 };
const size_t ia_size = sizeof( ia ) / sizeof( *ia );

int *ia_begin = ia;
int *ia_end = ia + ia_size;

std::vector<int> ivec;
std::list<int> ilist;

/* copy elements from array to vector & list */
std::copy( ia_begin, ia_end, std::back_inserter( ivec ) );
std::copy( ia_begin, ia_end, std::back_inserter( ilist ) );

/* vector before values are removed */
std::copy( ivec.begin(), ivec.end(),
std:stream_iterator<int>( std::cout, "\n" ) );
rem_evens( ivec );

/* vector after even values are removed */
std::copy( ivec.begin(), ivec.end(),
std:stream_iterator<int>( std::cout, "\n" ) );

return 0;
}




-- arnuld
http://lispmachine.wordpress.com

 

[James Kanze]

[...]

I tried it with vector's erase member function but that falls into the
infinite loop:

void rem_evens( std::vector<int>& ivec)
{
std::vector<int>::iterator begin = ivec.begin();
std::vector<int>::iterator end = ivec.end();

while( begin != end )
{
if( (*begin % 2) == 0 )
{
begin++ = ivec.erase( begin );

I'm not sure what this statement is supposed to do, but it
looks very, very wrong (and may not compile with some
implementations).

Note that the statement has a very different meaning
depending on whether vector<>::iterator is a typedef for a
pointer, or is a class type. Since the code shouldn't
compile if it is a typedef for a pointer, I will assume that
it is a class type, which means that you have the equivalent
of:

begin.operator++( 0 ).operator=( ivec.erase( begin ) ) ;

(I'm supposing member functions for the operator++ here, as
I think that's the most frequent implementation. If it's a
non-member, the call sequence will be different, but what
follows still holds.)

Note that begin.operator++( 0 ) returns a temporary object,
whose assignment operator is called to capture the results
of ivec.erase. Furthermore, ivec.erase invalidates begin
(since it removes the object begin points to); the order of
evaluation of the subexpressions above is not specified, so
you may be calling operator++ on an invalid iterator.

And of course, if begin happens to point to the last element
of the vector, after erase, it will point to end() (if it
were valid), and incrementing an iterator pointing to end()
is not a good idea at all.

Note that erase returns an iterator which points to the
element which was immediately behind the element you
removed. For something like this, the "classical" idiom is:

while ( begin != end ) {
if ( condition ) {
begin = vec.erase( begin ) ;
} else {
++ begin ;
}
}

You either increment, or you use the iterator returned by
erase.

Of course, the classical idiom would use remove here:

vec.erase(
remove_if( vec.begin(), vec.end(), condition ),
vec.end() ) ;

 

[arnuld]

I'm not sure what this statement is supposed to do, but it
looks very, very wrong (and may not compile with some
implementations).

Note that the statement has a very different meaning
depending on whether vector<>::iterator is a typedef for a
pointer, or is a class type. Since the code shouldn't
compile if it is a typedef for a pointer, I will assume that
it is a class type,

yes, it is a class because VECTOR is a class and erase is its memebr
function.

which means that you have the equivalent of:

begin.operator++( 0 ).operator=( ivec.erase( begin ) ) ;

I dont' know and don't understand what that

begin.operator++( 0 ).operator

means :-(

while ( begin != end ) {
if ( condition ) {
begin = vec.erase( begin ) ;
} else {
++ begin ;
}
}
}
You either increment, or you use the iterator returned by erase.

OK ,i got it but since we have removed the element, so the ivec.end()
iterator defined previously (before erasing) must invalidate but it does
not whereas insert() invalidates such things . I don't understand the
phenomenon.

Of course, the classical idiom would use remove here:

vec.erase(
remove_if( vec.begin(), vec.end(), condition ), vec.end() ) ;

Aha... that's good but that's new to me. so this member function takes
2 arguments:

ivec.erase( algorithm, end_iterator )

it is mysterious, why it takes end_iterator here. I need to look up the
that ERASE member function in Stroustrup .




-- arnuld
http://lispmachine.wordpress.com

 

[Barry]

arnuld a écrit :

WANTED:
/* C++ Primer - 4/e
*
* Exercise: 9.26
* STATEMENT
* Using the following definition of ia, copy ia into a vector and
into a list. Use the single iterator form of erase to remove the
elements with odd values from your list * and the even values from your
vector.
int ia[] = { 0, 1, 1, 2, 3, 5, 8, 13, 21, 55, 89 };
*
*/


WHAT I GET:

/home/arnuld/programming/c++ $ g++ -ansi -pedantic -Wall -Wextra
ex_09.26.cpp ex_09.26.cpp:
In function 'int main()': ex_09.26.cpp:43:
error: '_1' was not declared in this scope
/home/arnuld/programming/c++ $ [snip]
std::remove_if( ivec.begin(), ivec.end(),
_1 % 2 == 0 );
[snip]

I am just trying to use Lambda from Std. Lib. Why it is the problem ?

There is no lambda in STL (for now).
Instead, you can use the std::modulus<> functor together with
std::bind2nd().

std::not2 is also needed, the Predicate looks like:
bind2nd(not2(modulus<int>()), 2))

 

[Barry]

yes, it is a class because VECTOR is a class and erase is its memebr
function.




I dont' know and don't understand what that

begin.operator++( 0 ).operator

means :-(




OK ,i got it but since we have removed the element, so the ivec.end()
iterator defined previously (before erasing) must invalidate but it does
not whereas insert() invalidates such things . I don't understand the
phenomenon.





Aha... that's good but that's new to me. so this member function takes
2 arguments:

ivec.erase( algorithm, end_iterator )

it is mysterious, why it takes end_iterator here. I need to look up the
that ERASE member function in Stroustrup .

template < class ForwardIterator, class Predicate >
ForwardIterator remove_if ( ForwardIterator first,
ForwardIterator last,
Predicate pred )
{
ForwardIterator result = first;
for ( ; first != last; ++first)
if (!pred(*first)) *result++ = *first;
return result;
}

actually remove_if does NOT remove any thing, it just move the matched
items forward to overwrite those are not.


std::vector<int>::iterator pos
= remove_if(ivec..begin(), ivec.end(),
std::bind2nd(std::not2(std::modulus<int>()), 2));

now, pos points to the first item that's not matched

iterator vector::erase (iterator first, iterator last);

ivec.erase(pos, ivec.end());

now it's clear that, vector::erase erases a iterator range

 

[Barry]

yes, it is a class because VECTOR is a class and erase is its memebr
function.




I dont' know and don't understand what that

begin.operator++( 0 ).operator

means :-(

means that you can't increment rvalue return by a function.

int f() { return 10; }
++f(); //modifying an rvalue is illformed

But VC has an extension to compile the code. you can turn it off by /Za

 

[werasm]

Aha... that's good but that's new to me. so this member function takes
2 arguments:

ivec.erase( algorithm, end_iterator )

it is mysterious, why it takes end_iterator here. I need to look up the
that ERASE member function in Stroustrup .

No, <erase> is not the surprise, <remove_if (or remove)> is. It
changes
the order of the elements as if they have been removed and returns the
logical (not physical) end (where the physical end would have been
should they have been removed). Using the logical end one can erase
the
remainder (from the logical to the physical end). Perhaps have a
closer
look at remove. It's subtle.

Getting hold of the book "The Standard C++ Library" by Nicolai M.
Josuttis
would be very helpful.

Regards,

Werner

 

[James Kanze]

yes, it is a class because VECTOR is a class and erase is its memebr
function.

vector<>::iterator can be a class type, but it can also be a
typedef to a pointer. In most of the early implementations, it
was just a typedef to a pointer.

I dont' know and don't understand what that

begin.operator++( 0 ).operator

means :-(

It's the function which overloads of the ++ operator. For
overloaded operators, the name of the function which overloads
the operator is "operator <op>", where <op> is the operator
being overloaded.

++ and -- are a bit special, as well, since there are two
versions, one for prefix, and one for postfix. For whatever
reasons, the postfix version takes an additional int argument;
the compiler passes it 0 when it is being called using the
normal operator syntax.

OK ,i got it but since we have removed the element, so the ivec.end()
iterator defined previously (before erasing) must invalidate but it does
not whereas insert() invalidates such things. I don't understand the
phenomenon.

Erase on a vector invalidates all iterators which designate the
element, or follow it. But you're right that that includes the
end iterator, so the loop should read:

while ( begin != vec.end() ) ...

If you're erasing in the loop, you can't cache the end()
iterator.

Aha... that's good but that's new to me. so this member function takes
2 arguments:

ivec.erase( algorithm, end_iterator )

vector::erase() has two overloads: one takes a single iterator,
and removes just that element; the other takes two iterators,
which define a sequence of elements to be removed.

The algorithm remove_if returns an iterator. You should read
the specifications of the function.

it is mysterious, why it takes end_iterator here. I need to
look up the that ERASE member function in Stroustrup .

You need to look up all of the overloads to erase, and you need
to look up the algorithm remove/remove_if: because of the fact
that (like all of the algorithms), they take iterators, and not
containers, they can't actually remove anything. So all they do
is regroup the elements which aren't removed at the front of the
sequence, and return an iterator to the first element which
follows. This is used, with the end iterator, as an argument to
the erase function, which does the actual removal.

 

[James Kanze]

means that you can't increment rvalue return by a function.

Not at all. First, of course, from a formal point of view, you
can't "increment" a class type at all; all you can do is call a
function on it (or use it as an argument to a function). When
the compiler sees a ++ applied to a class type; the compiler
tries to find a function named operator++ which can be called.

And of course, if the return value of a function is a class
type for which operator++ is defined, you can call operator++ on
it. But that's not what's happening here.