Splitting an STL list?

Question

I have a circular linked list that looks something like this:

4 -> 3 -> 2 -> 5 -> 0 -> 1 -> beginning

I want to split this list into two segments, reverse one of the segments, and then rejoin the list. Something like this:

Split, an O(1) operation 4 ** 3 -> 2 -> 5 ** 0 -> 1 -> beginning

Reverse, an O(n) operation 0 ** 3 -> 2 -> 5 ** 4 -> 1 -> beginning

Rejoin, an O(1) operation 0 -> 3 -> 2 -> 5 -> 4 -> 1 -> beginning

The STL does not appear to have a circular linked list, but I'm hoping I can get away with representing the list as a (forward) list. This, requires: * A way to split the lists into sublists * A way to merge the lists together

Merging the sublists together should be easy using std::list::splice, and it should be an O(1) operation. Yay!

However, I can't find a good O(1) way to split the lists into sublists. One approach is to use iterators, but I don't think that works in my case because the sublist goes off the end of the list and resumes at the beginning of the list.

Is there an efficient way to implement this algorithm using the STL? Or should I just give up and write my own circular linked list library?

Thanks!

Answer 1

I am not sure how helpful this is, but here it is:

template<typename I>
void inner(I b, I e)
{
    std::reverse(b, e);  // l = {4 5 2 3 0 1}
}

template<typename L, typename I>
void outer(L& l, I b, I e)
{
    l.splice(l.begin(), l, e, l.end());  // l = {0 1 4 3 2 5}
    std::reverse(l.begin(), b);          // l = {4 1 0 3 2 5}
}

int main ()
{
    std::list<int> t, l{4, 3, 2, 5, 0, 1};
    std::cout << l << std::endl;

    auto b = l.begin(), e = l.begin();
    std::advance(b, 1);
    std::advance(e, 4);
    bool in = true;

    in ? inner(b, e) : outer(l, b, e);
    std::cout << l << std::endl;
}

There are two options:

• reverse the inner part of the list (3 2 5)
• reverse the outer part (0 1 -> 4)

and you might want to reverse the shorter one, but you'll have to count for this, which is linear-time. I have written two separate functions inner,outer for these two tasks.

inner is very simple (nothing but a wrapper) and working as expected. However, outer is leaving the list in a state that is equivalent to the expected modulo some rotation (circular shift). If you are modelling a circular list, this should be fine. But if you want the output exactly as in your example, you'll have to count again, to find the right point where to rotate. I would avoid this, as it is linear-time.

Note that no splitting is actually needed, because reversal is in-place. Also, operation

l.splice(l.begin(), l, e, l.end());

is constant-time.

Check live example.