how to implement a for_each like function in c++?

Question

I need to implement a for_each function, like below. I know std::for_each could apply fn to each element, but we cannot erase elements in std::for_each. I need to extend this template function, so that in fn, the caller can both visit elements and erase elements one at a time. Is there a proper way to do this?

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class A
{
public:
    explicit A(){
        mVec.clear();
    }
    ~A(){}
    template<class T> void for_each(T fn)
    {
        for(size_t i = 0; i < mVec.size(); ++i)
        {
            //fn can erase element or just visit element
            fn(mVec[i]);
        }
    }
    vector<int> mVec;
};
int main()
{
    A test;
    for(int i = 0; i < 8; ++i)
    {
        test.mVec.push_back(i);
    }
    test.for_each([&test](int i){
        if (i % 2 == 0)
        {
            cout << i << " deleted" << endl;
            test.mVec.erase(find(test.mVec.begin(), test.mVec.end(), i));
        } 
        else
        {
            cout << i << " parse" << endl;
        }
    });

    system("pause");
    return 0;
}

Edit: In for_each template function, we do not know whether the caller will erase elements or not. Erasing elements is done in fn

try `vec.erase(std::remove_if(vec.begin(), vec.end(), [](int i){ return i%2==0;}), vec.end());` ? — Chen OT, Dec 01 '15 at 10:36
Read [this](http://stackoverflow.com/questions/16013545/how-do-i-erase-elements-from-stl-containers) on how to properly remove items from a vector. — RedX, Dec 01 '15 at 10:40
This thread is interesting and related, on why the elements are immutable in foreach. Don't be fooled by the c-sharp in the topic - it's actually about the design of foreach and is interesting regardless of implementation language. http://stackoverflow.com/questions/776430/why-is-the-iteration-variable-in-a-c-sharp-foreach-statement-read-only — Kif, Dec 01 '15 at 10:42

Paolo Bonzini · Answer 1 · 2015-12-01T10:48:59.867

4

Could you return a bool value from the function, where true means "erase the element"? Then your for_each function becomes something like.

    size_t i = 0;
    for(size_t j = 0; j < mVec.size(); ++j) {
        if (!fn(mVec[j])) {
            // The element must be kept
            if (i != j)
                mVec[i] = std::move(mVec[j]);
            i++;
        }
    }
    mVec.resize(i);

The advantage is also that this is always O(n), no matter how many elements are erased.

EDIT: The loop above is really just std::remove_if(), so @ChenOT's suggestion is the best. Alternatively

    n = std::remove_if(mVec.begin(), mVec.end(), fn) - mVec.begin();
    mVec.resize(n);

edited Dec 01 '15 at 10:48

answered Dec 01 '15 at 10:43

Paolo Bonzini

1,900
15
25

1

You buried the lede here, which is that this method is O(n) instead of O(n^2) as when you erase single elements from a vector. +1. – John Zwinck Dec 01 '15 at 10:47
@JohnZwinck, the same will hold for remove_if too though. – Paolo Bonzini Dec 01 '15 at 10:49
@PaoloBonzini, thanks. But this will not help. When we use remove_if function, We control the delete operation. if someone erase a element in fn, running crashes. I want to implement a public template function, the caller can erase elements or visit elements in fn one at a time. – John Zhu Dec 02 '15 at 02:44
@IceYounger, it's impossible to solve what you want in a generic way, or it would be solved. Try rephrasing your problem in terms of remove_if. – Paolo Bonzini Dec 02 '15 at 17:50
@PaoloBonzini, thanks. Maybe we can let fn return a bool value. If fn erase an element, return true, then iterator stop auto-incrementing. If return false, auto-increment. – John Zhu Dec 03 '15 at 01:40
@IceYounger Then what you have is exactly something that can be passed to remove_if. :) – Paolo Bonzini Dec 04 '15 at 14:43

how to implement a for_each like function in c++?

1 Answers1