CODEWITHSUNDEEP
c++c++11forward-list
ja.abell
ja.abell

Reputation: 133

Transfer elements from one forward_list to another based on condition

I have two forward_lists: list1 and list2. I'd like to iterate over the first and transfer elements to the second based on a condition. Here is an example using forward_list<int> that does not work but I think expresses what I want.

#include <iostream>
#include <forward_list>

using namespace std;

int main(void)
{
    forward_list<int> list1 = {1, 2, 3, 4, 5, 6};
    forward_list<int> list2;

    //Transfer elements between 2 and 5 from list1 to list2.    
    forward_list<int>::const_iterator iter_before = list1.before_begin();
    forward_list<int>::const_iterator iter = list1.begin();
    while ( iter != list1.end())
    {
        int item = *iter;
        cout << item ;
        if (2 <= item && item <= 5 )
        {
            list2.splice_after(list2.before_begin(),list1,iter_before);
            iter_before = iter;
            iter++;
            cout << "! "; // Indicates if current item is transferred.
        }
        else
        {
            iter++;
            iter_before++;
            cout << " ";
        }
    }

    cout << "\nList 1: ";
    for (auto item : list1)
    {
        cout << item << " ";
    }
    cout << "\nList 2: ";
    for (auto item : list2)
    {
        cout << item << " ";
    }
    cout << endl;

    return 0;
}

I've tried resetting the iter and iter_before iterators to the beginning of list1, which works but transverses some list1 elements more than once (restarts). I've also tried copying elements into list2 first and then erasing the element on list1, which also works. I deem both these solutions inefficient.

Can anyone propose a more efficient one which involves just swapping the pointers at the list?

Upvotes: 0

Views: 938

Answers (2)

T.C.
T.C.

Reputation: 137310

The trick is realizing that:

  1. You need to obtain an iterator to the element following the one you will splice into the other list - and this must take place before the splicing. After the splice, this iterator will point to the next element to be processed.
  2. After splicing, iter_before is still pointing right before the next element to be processed - there's no need to change it.

So, in your if, do instead:

auto iter_next = std::next(iter);
list2.splice_after(list2.before_begin(),list1,iter_before);
iter = iter_next;

Demo.

Upvotes: 2

DaRich
DaRich

Reputation: 1027

Your answer exactly describes the use case of STL copy_if (http://www.cplusplus.com/reference/algorithm/copy_if/).

Upvotes: 0

Related Questions