How to correctly (but efficiently) implement something like "vector :: insert"? (Smoothing the pointer)

Question

Consider this hypothetical implementation of vector :

 template<class T> // ignore the allocator struct vector { typedef T* iterator; typedef const T* const_iterator; template<class It> void insert(iterator where, It begin, It end) { ... } ... } 

Problem

There is a subtle problem we are facing here:
It is likely that begin and end refer to elements in the same vector after where .

For example, if the user says:

 vector<int> items; for (int i = 0; i < 1000; i++) items.push_back(i); items.insert(items.begin(), items.end() - 2, items.end() - 1); 

If It not a pointer type, then we are fine.
But we don’t know, therefore we have to check that [begin, end) does not belong to the range already inside the vector.

But how do we do this? According to C ++, if they do not belong to the same array, then the pointer comparison will be undefined!
Thus, the compiler may erroneously tell us that the elements are not aliases when in fact they do this, which leads to an unnecessary slowdown of O (n).

Potential solution and disclaimer

One solution is to copy the entire vector each time, include new elements, and then delete the old copy.

But it is very slow in scenarios such as the example above, where we will copy 1000 elements to insert one element, although we might already have sufficient capacity.

Is there a general way (correctly) to solve this problem effectively, i.e. not suffer from a slowdown of O (n) in cases where nothing overlaps?

Answer 1

You can use the predicates std::less , etc., which are guaranteed to give a complete order, even if the comparison with the original pointers fails.

From the standard [comparisons]/8 :

For templates with a larger, smaller, larger, equal, and lower level of specialization for any type of pointer, they are given the full order, even if the built-in operators <,>, <=,> = do not.

Answer 2

But how do we do this? According to C ++, if they do not belong to the same array, then the pointer comparison will be undefined!

Wrong. Comparison of pointers is not specified, not undefined. From C ++ 03 §5.9 / 2 [expr.rel]:

[...] Pointers to objects or functions of the same type (after pointer conversions) can be compared with the result, defined as follows:

[...]
-Other pointer comparisons not indicated.

Thus, it is safe to check if there is overlap before making an expensive but correct copy.

Interestingly, C99 differs from C ++ in that there is undefined behavior in this comparison of pointers between unrelated objects. From C99 §6.5.8 / 5:

When comparing two pointers, the result depends on the relative locations in the address space of the objects that it points to. [...] In all other cases, the behavior is undefined.

Answer 3

Actually, that would be true, even if they were ordinary iterators. Nothing prevents anyone from doing

 std::vector<int> v; // fill v v.insert(v.end() - 3, v.begin(), v.end()); 

Determining if these aliases are a problem for any iterator implementation.

However, what you are missing is an implementation; you do not need to use portable code. As an implementation, you can do whatever you want. You could say: "Well, in my implementation, I follow x86, and < and > great for any pointers." And it will be good.