Solved

Lambda expressions in STL algorithms C++11

Posted on 2014-09-11
19
543 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
  • 8
  • 8
  • 3
19 Comments
 
LVL 28

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 28

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
 

Author Comment

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

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 28

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 28

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
What Is Threat Intelligence?

Threat intelligence is often discussed, but rarely understood. Starting with a precise definition, along with clear business goals, is essential.

 
LVL 32

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 28

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 28

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 32

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 32

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 28

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

Enabling OSINT in Activity Based Intelligence

Activity based intelligence (ABI) requires access to all available sources of data. Recorded Future allows analysts to observe structured data on the open, deep, and dark web.

Join & Write a Comment

Unlike C#, C++ doesn't have native support for sealing classes (so they cannot be sub-classed). At the cost of a virtual base class pointer it is possible to implement a pseudo sealing mechanism The trick is to virtually inherit from a base class…
What is C++ STL?: STL stands for Standard Template Library and is a part of standard C++ libraries. It contains many useful data structures (containers) and algorithms, which can spare you a lot of the time. Today we will look at the STL Vector. …
The goal of the tutorial is to teach the user how to use functions in C++. The video will cover how to define functions, how to call functions and how to create functions prototypes. Microsoft Visual C++ 2010 Express will be used as a text editor an…
The viewer will be introduced to the technique of using vectors in C++. The video will cover how to define a vector, store values in the vector and retrieve data from the values stored in the vector.

705 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

Need Help in Real-Time?

Connect with top rated Experts

18 Experts available now in Live!

Get 1:1 Help Now