Solved

Lambda expressions in STL algorithms C++11

Posted on 2014-09-11
19
659 Views
Last Modified: 2014-09-15
Hi,

I have below code. I am trying use lambda expression as a predicate to remove_if algorithm to delete an element from vector. However I am not able to compile it using mingw gcc 4.8 compiler.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    vector<int> vi;
    vi.push_back(12);
    vi.push_back(24);
    vi.erase(remove_if(vi.begin(), vi.end(), [&vi]()->bool{return (vi[0] == 12);}), vi.end());
    return 0;
}

Open in new window


Can anybody please help with this?? Is it that only local variable are captured and not the parameters passed to parent function?? what is the way to pass calling functions parameters to lambda expression??

Some of the compiler errors below -

c:\program files (x86)\codeblocks\mingw\lib\gcc\x86_64-w64-mingw32\4.8.1\include\c++\bits\stl_algo.h|1174|error: no match for call to '(main()::__lambda0) (int&)'|
C:\CPP\vector_cpp1\main.cpp|13|note: candidate is:|
C:\CPP\vector_cpp1\main.cpp|13|note: main()::__lambda0|
C:\CPP\vector_cpp1\main.cpp|13|note:   candidate expects 0 arguments, 1 provided|
0
Comment
Question by:mumbaikar
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 8
  • 8
  • 3
19 Comments
 
LVL 29

Accepted Solution

by:
pepr earned 300 total points
ID: 40318022
Try the following:
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    vector<int> vi;
    vi.push_back(12);
    vi.push_back(24);
    
    for (auto x : vi)
        cout << x << "\n";

    cout << "-----------------------------\n";

    // Wrong: vi.erase(remove_if(vi.begin(), vi.end(), [&vi]()->bool{return (vi[0] == 12); }), vi.end());

    vi.erase(remove_if(vi.begin(), vi.end(), [](int x){ return x == 12; }));

    for (auto x : vi)
        cout << x << "\n";

    return 0;
}

Open in new window

In the lambda expression [](int x)->bool{ return x == 12; }), the ->bool says what will be the return type and can be left out here (see below). The [] does not need anything inside -- it is used for telling the compiler what variables should be visible inside and how. The (int x) defines the integer argument of the function. And the body just uses the agument for testing and returning the boolean result. The lambda function does not need to know anything about the container. It gets one integer and returns one boolean.

The one-liner can be more understandable when using the iterator variable explicitly.
    auto after_end = remove_if(vi.begin(), vi.end(), [](int x){ return x == 12; });
    vi.erase(after_end);

Open in new window

0
 

Author Comment

by:mumbaikar
ID: 40318050
Ok. But i want to erase the first element in vector always, no matter how many elements are added from back. Is it possible to do it using lambda expression? Or simply using erase on vi.begin() will do? I am looking for efficient  pop_front functionality.
0
 
LVL 29

Expert Comment

by:pepr
ID: 40318188
There is no need for lambda expression in the case. You can use vi.erase(vi.begin(), vi.begin() + 1);

But if the vector is very long, the solution is  not efficient.
0
Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 

Author Comment

by:mumbaikar
ID: 40318251
Is 2nd parameter necessary?
0
 
LVL 29

Expert Comment

by:pepr
ID: 40318666
My fault. I am sorry. You are right, and I have the bug in my above solution.

.erase() can have one or two arguments. If only one is used, then the element is removed. So, for your case, the vi.erase(vi.begin()) should be fine. You need the second iterator only when you want to remove more than one elements.

The remove_if() returns the iterator after the end of what remained. Generally, more than one element can be removed. This way, the two iterator version of .erase() must be used (as you did in the question -- that was not not part of the bug found by the compiler).
0
 

Author Comment

by:mumbaikar
ID: 40318724
Your lambda expression worked. However I used one parameter version of erase and its working fine.

I have another question.

vector<int>::iterator s,e;

s = vi.begin();
e = vi.end();
vi.erase(vi.begin());

Open in new window


What happens to begin and end iterators if above call is made on a vector which has only one element. Shouldn't begin iterator and end iterator be pointing at same location, one past last element?? In other words, s should be equal to e after erase call is made on one last element. But my test gave me runtime error. What exactly erase does to begin iterator when applied to a vector with just one last element?? why do we have to again call "end" method to get correct end on empty vector, which was not empty initially?? Runtime error goes away if I call
e = vi.end()

Open in new window

and then compare with s iterator (which has automatically changed after call to erase). They match!!
0
 
LVL 29

Assisted Solution

by:pepr
pepr earned 300 total points
ID: 40318804
The reference (http://www.cplusplus.com/reference/vector/vector/erase/) says:
Iterators, pointers and references pointing to position (or first) and beyond are invalidated, with all iterators, pointers and references to elements before position (or first) are guaranteed to keep referring to the same elements they were referring to before the call.

    auto s = vi.begin();
    auto e = vi.end();
    vi.erase(vi.begin());
    cout << "s == vi.begin() ... " << (s == vi.begin()) << endl;

Open in new window


I am using Visual Studio C++ 2013. It tests compatibility  of the operators and calls _DEBUG_ERROR("vector iterators incompatible"); that is implemented via (probably) MS specific ::_CrtDbgBreak();. Anyway, it should fail somehow and it fails using the mentioned way (error message displayed in a message box...).
0
 

Author Comment

by:mumbaikar
ID: 40318851
So end iterator gets modified and probably is pointing to where begin iterator is pointing to (in case of erasing last element). It should have been the opposite actually ideally. Begin iterator should get modified and probably point to where end is pointing to. It doesn't matter for container because its empty. But a test condition in for or while loop without calling end() will fail and will end up in runtime crash.
0
 
LVL 29

Expert Comment

by:pepr
ID: 40318954
The .begin() and .end() return new iterator to the positions. The iterators pointing to erased area and behind are invalidated. It is implementation dependent how it is done.

The problem with looping through any container that is modified on-the-fly is general. The behaviour si always dependent on the kind of the container and on the implementation.
0
 
LVL 34

Assisted Solution

by:sarabande
sarabande earned 200 total points
ID: 40319005
It should have been the opposite actually ideally. Begin iterator should get modified and probably point to where end is pointing to.
the begin() and end() iterators are no members of std::vector but member functions (see also comment of pepr). in case of an empty vector both are equal and the condition vi.begin() != vi.end() is false. you may not rely on iterators always have to point to a valid memory address. that is implementation dependent and varies among compilers.

the erase function however returns a valid iterator which points behind the erased sequence. if the vector is empty after erase the erase function returns end() iterator.

because of that the following is possible:

std::vector<int>::iterator it;
while ((it = vi.begin()) != vi.end())
{
      it = vi.erase(vi.begin());
}

Open in new window


though vi.clear(); of course is more efficient.

if you need to selectively erase elements you may do:

std::vector<int>::iterator it;
for (it = vi.begin(); it != vi.end(); )
{
      if (my_erase_condition(*it) == true)
      {
          it = vi.erase(vi.begin());
      }
      else
      {
          it++;
      }
}

Open in new window



Sara
0
 

Author Comment

by:mumbaikar
ID: 40319516
Here is a test code to check before and after value of begin and end iterators -

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    vector<int> vi;

    vi.push_back(189);

    vector<int>::iterator b = vi.begin();      // Will have 189
    vector<int>::iterator e = vi.end();         // Will have 0 which probably means one element beyond 189
    vector<int>::iterator ret;

    cout << "Size before erase = " << vi.size() << endl;    // this is 1
    cout << "end = " << *e << endl;                                   // this is 0
    cout << "begin = " << *b << endl;                               // this is 189

    ret = vi.erase(vi.begin());                                             // ret is 189
    e = vi.end(); //========> If you dont do this then *e will have 0 and will not be equal to begin iterator

    cout << "Size after erase = " << vi.size() << endl;      // This is now 0
    cout << "end = " << *e << endl;                                  // This is now 189 after call to end()
    cout << "begin = " << *b << endl;                               // This is still 189
    cout << "ret = " << *ret << endl;                                 // This is 189 returned by erase()

    if(b == e)                                    //This is true if end() is called
        cout << "b == e" << endl;
    else                                           // This is true if end() is not called
        cout << "b != e" << endl;

    return 0;
}

Open in new window


I haven't tested for other containers. But for vector it still looks like end iterator is moving backwards after the call to erase.
0
 
LVL 29

Expert Comment

by:pepr
ID: 40320015
The line 17 is wrong. It is a bug. The compiler or probably runtime should not allow that. The .end() should return the iterator that should not be allowed to be dereferenced. If you think more about it, why the zero should be the result? This is exactly what Sara wrote about referencing the memory via the end iterator. Actually, it is a kind of tradeoff if the specific compiler allows it. The idea of the Standard is that it is not allowed, and a better compiler should produce a code that reveals that wrong approach.

As I wrote earlier and as Sara also emphasized, the .begin() and .end() are not iterators. They are functions (member functions of the class, also known as methods). Their results are the iterators.

The vector container is always implemented as contiguous block of memory with index zero at the beginning. Knowing that, it is clear that the end of the content moves towards the address with the first element.
0
 

Author Comment

by:mumbaikar
ID: 40320082
I know begin and end are methods. When I said begin and end iterators I was talking about iterators returned by them. Just convenient way of writing. Sorry that it created confusion. Also, I know you cant dereference iterators which are invalid like the one returned by end(). May be my mingw gcc 4.8.1 compiler, a standard one actually, is allowing it for integral types underlying only. I am not sure. I was pressing this matter further because I was very surprised that after calling erase() the iterator returned by end was pointing to a value which iterator returned by begin() was pointing at before calling erase(). May be it is implemented that way internally as any location is invalid after container is empty. I "thought" - erase() when called in a while or for loop on begin method till the container is empty, only begin iterator, returned by erase(), moves to next valid begin element i.e. 1st element. And end iterator remains where it is i.e. one element beyond last element. But the key is to call end() at least one last time to ensure the while condition matches and we come out of the loop appropriately. I was expecting only one iterator to move and end iterator to hold its position. However, it also changes its position. This is the behavior matches with sara's code and explanation given in other posts by you. Thanks for help.
0
 
LVL 29

Expert Comment

by:pepr
ID: 40320114
I also thank YOU. That is because trying to explain in details helps to understand it better by myself. And I believe I am not alone to feel and think this way ;)
0
 
LVL 34

Expert Comment

by:sarabande
ID: 40321118
May be my mingw gcc 4.8.1 compiler, a standard one actually, is allowing it for integral types underlying only.
no. it is correct. generally, the returned iterator of end() is a valid iterator. because of that, the compiler does not complain if you dereference it. however, you would get a runtime error doing so. the case is similar to accessing a vector with an index that is out of boundaries. it compiles but throws an exception at runtime.

Sara
0
 

Author Comment

by:mumbaikar
ID: 40321122
I did not get runtime error.
0
 
LVL 34

Expert Comment

by:sarabande
ID: 40322834
I did not get runtime error.
yes, if the allocated array was not freed when the vector becomes empty by std::vector::erase the end() iterator still would point to a valid memory address which is beyond the valid elements of the vector but not beyond the allocated internal array. this might be different when dereferencing the end() of a newly created empty vector.

Sara
0
 

Author Comment

by:mumbaikar
ID: 40322844
So it is illegal to dereference end iterator on container which is just created and not populated yet. Otherwise its safe.
0
 
LVL 29

Expert Comment

by:pepr
ID: 40323014
To simplify the answer a bit, dereferencing .end() is about as valid as dereferencing a NULL pointer. This is from the principle point of view. This is not the explanation why it works in your specific case.

In other words, an iterator returned by the .end() method is a valid iterator the same way as a pointer variable filled with the NULL (or nullptr in C++11) value is is a valid pointer variable. However, the attempt to dereference both of them is wrong. The values can be used only for testing against another pointer/iterator.
0

Featured Post

Enroll in May's Course of the Month

May’s Course of the Month is now available! Experts Exchange’s Premium Members and Team Accounts have access to a complimentary course each month as part of their membership—an extra way to increase training and boost professional development.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

When writing generic code, using template meta-programming techniques, it is sometimes useful to know if a type is convertible to another type. A good example of when this might be is if you are writing diagnostic instrumentation for code to generat…
Container Orchestration platforms empower organizations to scale their apps at an exceptional rate. This is the reason numerous innovation-driven companies are moving apps to an appropriated datacenter wide platform that empowers them to scale at a …
The viewer will learn how to user default arguments when defining functions. This method of defining functions will be contrasted with the non-default-argument of defining functions.
The viewer will learn how to clear a vector as well as how to detect empty vectors in C++.

738 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question