c++ - Splitting an STL list? -

i have circular linked list looks this:

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

i want split list 2 segments, reverse 1 of segments, , rejoin list. this:

split, o(1) operation 4 ** 3 -> 2 -> 5 ** 0 -> 1 -> beginning

reverse, o(n) operation 0 ** 3 -> 2 -> 5 ** 4 -> 1 -> beginning

rejoin, o(1) operation 0 -> 3 -> 2 -> 5 -> 4 -> 1 -> beginning

the stl not appear have circular linked list, i'm hoping can away representing list (forward) list. this, requires: * way split lists sublists * way merge lists together

merging sublists should easy using std::list::splice, , should o(1) operation. yay!

however, can't find o(1) way split lists sublists. one approach use iterators, don't think works in case because sublist goes off end of list , resumes @ beginning of list.

is there efficient way implement algorithm using stl? or should give , write own circular linked list library?

thanks!

i not sure how helpful is, here is:

template<typename i> void inner(i b, e) {     std::reverse(b, e);  // l = {4 5 2 3 0 1} }  template<typename l, typename i> void outer(l& l, b, 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 2 options:

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

and might want reverse shorter one, you'll have count this, linear-time. have written 2 separate functions inner,outer these 2 tasks.

inner simple (nothing wrapper) , working expected. however, outer leaving list in state equivalent expected modulo rotation (circular shift). if modelling circular list, should fine. if want output in example, you'll have count again, find right point rotate. avoid this, linear-time.

note no splitting needed, because reversal in-place. also, operation

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

is constant-time.

check live example.