CODEWITHSUNDEEP
c++stlsingly-linked-list
upsidedown
upsidedown

Reputation: 221

Implementing stable_partition for forward_list

I want to implement something similar to std::stable_partition but for forward_list of c++11. The stl version requires bidirectional iterators, however by utilizing container specific methods I believe I can get the same outcome effeciently.

Example declaration :

template <typename T, typename UnaryPredicate>
void stable_partition(std::forward_list<T>& list, UnaryPredicate p);

(while possible to add begin and end iterators, I omitted them for brevity. The same for returning the partition point )

I already worked out the algorithm to accomplish this on my own list type, but I have troubles implementing it in stl.

The key method appears to be splice_after. Other methods require memory allocations and copying elements.

Algorithm sketch :

With proper coding this should be linear time (all operations inside the loop can be done in constant time) and without extra memory allocation or copying.

I am trying to implement the second step using splice_after, but I end up either concating the wrong element or invalidating my iterators.

The question:

What is the correct use of splice_after, so that I avoid mixing iterators between lists and insert the correct elements?

First Attempt (how I hoped it works):

template <typename T, typename UnaryPredicate>
void stable_partition(std::forward_list<T>& list, UnaryPredicate p)
{
    std::forward_list<T> positives;
    auto positives_iter = positives.before_begin();

    for (auto iter = list.begin(); iter != list.end(); ++iter)
    {
        if (p(*iter))
            positives.splice_after(positives_iter, list, iter);
    }

    list.splice_after(list.before_begin(), positives);
}

Unfortunately this has at least one major flaw: splice_after inserts after iter, and the wrong element is inserted.

Also, when the element is moved to the other list, incrementing iter now traverses the wrong list.

Upvotes: 0

Views: 165

Answers (1)

Maxim Egorushkin
Maxim Egorushkin

Reputation: 136425

Having to maintain the preceding iterators for std::forward_list::splice_after makes it a bit trickier, but still pretty short:

template<class T, class UnaryPredicate>
std::array<std::forward_list<T>, 2>
stable_partition(std::forward_list<T>& list, UnaryPredicate p) {
    std::array<std::forward_list<T>, 2>  r;
    decltype(r[0].before_begin()) pos[2] = {r[0].before_begin(), r[1].before_begin()};
    for(auto i = list.before_begin(), ni = i, e = list.end(); ++ni != e; ni = i) {
        bool idx = p(*ni);
        auto& p = pos[idx];
        r[idx].splice_after(p, list, i);
        ++p;
    }
    return r;
}

Usage example:

template<class T>
void print(std::forward_list<T> const& list) {
    for(auto const& e : list)
        std::cout << e << ' ';
    std::cout << '\n';
}

int main() {
    std::forward_list<int> l{0,1,2,3,4,5,6};
    print(l);
    // Partition into even and odd elements.
    auto p = stable_partition(l, [](auto e) { return e % 2; });
    print(p[0]); // Even elements.
    print(p[1]); // Odd elements.
}

Upvotes: 1

Related Questions