Why std::lists can not be split/merged in constant time? Aren't they just linked lists?
I m sure I am missing something. Can you please give an insight on the reasons behind that?
That is a side-effect (some say a rather unfortunate one) of requiring size() to be constant-time. It is impossible to have both a constant-time size() and a constant-time splice() of sublists. Since all standard containers are required to have constant-time size(), this necessarily requires the sublist splice() to be linear.