Fix the specification of insert modifier

[gnzlbg]

From Casey's feedback:

O(# of elements inserted) is not generally implementable for e.g. inline_vector<int, 42> v(40); v.insert(begin(), 42); O(size) elements need to be displaced.

[gnzlbg]

@CaseyCarter the C++14 standard says for vector::insert:

The complexity is linear in the number of elements inserted plus the distance to the end of the vector.

In my head there is an algorithm that I call unstable_insert, that always inserts the elements at the end of the container first, and then swaps them with the elements at the insertion position, which requires N insertions and N swaps where N is the number of elements being inserted, and thus has complexity O(N) which also satisfies O(N + size()).

I cannot find anywhere in the standard that vector::insert must preserve the relative order of the elements after the insertion point, which would make unstable_insert a valid and faster implementation of vector::insert. Is this requirement specified somewhere?

A different algorithm, stable_insert, would maintain the relative order of the vector elements after the insertion point. This algorithms is O(N + size()) as you say, and also a valid implementation of vector::insert, but since IIUC the standard doesn't guarantee that vector::insert is stable, we might just as well be clear about it and make it unstable. We can always add a stable_insert method if desired.

[gnzlbg]

So... after discussing this at large in loungec++... the standard says:

• "strictly linear arrangement", which is hard to interpret but I interpret as a linear memory arrangement without holes
• all iterators after the insertion point are invalidated, which... allows an unstable insert implementation
• "Effects: Inserts x at position p". Which doesn't say anything about any other effects, but could be interpreted as "Insert x at position p in the sequence", where changing the relative order of the elements would be inserting x at position p in a different sequence, which would forbid unstable insert. It doesn't say "stably inserts..." though.

Anyhow the consensus there is that everybody expects vector::insert to be stable, all library implementations do it that way, and this container should do so as well (which I agree with). So I'll change the proposal to do that.

EDIT: Furthermore, if you don't care about the relative order of the elements, why would you try to insert something at some position in the sequence? You can just insert at the end... unstable_insert is kind of useless...

[gnzlbg]

We run into this problem with the specification of erase as well...

Complexity: The destructor of T is called the number of times equal to the number of the elements erased, but the move assignment operator of T is called the number of times equal to the number of elements in the vector after the erased elements

While this hints that we should shift the elements preserving the order, nothing actually says so. We can probably destroy N elements. Swap the elements from the end of the vector into their position (breaking the relative order of the elements within the vector), and then still do M number of swaps between two elements (which would be faster) and still be standard conforming...

[CaseyCarter]

I would advise you not to do anything sneaky with erase, either. LWG is far more likely to clarify the wording in the standard than to allow a container to exist with insert and/or erase operations with different semantics from the pre-existing containers. Users who don't care about the order of elements already know to insert elements at the end of a vector and to swap elements to the end before erasing; they'll do the same with inline_vector.

[gnzlbg]

Yes, I just extra made it clear that insert and erase are stable and preserve the order of the elements after the insertion point. Tried to find the "standard wording" for that in the standard but if it is specified somewhere, i just couldn't find it :/

On Wednesday, 19 October 2016, Casey Carter notifications@github.com wrote:

I would advise you not to do anything sneaky with erase, either. LWG is far more likely to clarify the wording in the standard than to allow a container to exist with insert and/or erase operations with different semantics from the pre-existing containers. Users who don't care about the order of elements already know to insert elements at the end of a vector and to swap elements to the end before erasing; they'll do the same with inline_vector.

— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub https://github.com/gnzlbg/inline_vector/issues/10#issuecomment-254838044, or mute the thread https://github.com/notifications/unsubscribe-auth/AA3NpiXX2XUa65QLGiSxUhP0uDim1xU_ks5q1i9egaJpZM4JEah_ .