C++ STL-like doubly linked list with constant time splicing

[nejuberuh]

Hey,

I'm looking for a C++ implementation of a doubly linked list with constant time splicing. To be more specific:

http://en.cppreference.com/w/cpp/container/list/splice

I need the third overload to be done in constant time, too.

I understand this means that .size() will be linear which I'm ok with as I really need cutting to be constant at all times and don't particularly need fast .size() queries.

Is there such an implementation? I tried to search for it but haven't found anything. The more STL-like the implementation is, the better.

Thanks.

[dhayden]

I'm not aware of such an implementation but it probably wouldn't be too hard to create your own. splice() would splice in the items without adjusting the size of the two lists. size() would count the number of items in the list when called.

There might be a better way. If you describe the problem you're trying to solve (not the solution), then maybe someone will suggest a faster solution. For example, does absolutely have to be a doubly linked list? If not then maybe forward_list<> will do. Since it doesn't have a size() method, I imagine that its splice () method might run in constant time, although I see that the standard lets it run in up-to linear time.