What is the efficient way to split a vector

Question

Is there any other constant time way to split a vector other than using the following.

 std::vector<int> v_SplitVector(start , end);

This would take a complexity of O(N). In this case O(end - start). Is there a constant time operation to do this.

OR am I using the wrong container for the task?..

Answer 1

The act of "splitting" a container, for container like vectors, where elements sits on contiguous memory, require necessarily a copy / move of everything needs to go on the other side.

Container like list, that have elements each on its own memory block can be easily rearranged (see std::list::splice)

But having elements in non contiguous memory may result in lower memory access performance due to more frequent cache missing.

In other words, the complexity of the algorithm may be not the only factor influencing performance: an infrequent linear copy may damage you less than a frequent linear walk on dispersed elements.

The trade-off mostly depends on how the hardware manage caches and how the std implementation you are using takes care of that (and how the compiler can eventually optimize)

Answer 2

This is a copy rather than a split, hence the complexity. You can probably write a split for list which might perform better.