Как правильно (и в то же время эффективно )реализовать что-то вроде «вставки вектора ::»? (Псевдоним указателя)
Рассмотрим эту гипотетическую реализацию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)
{
...
}
...
}
Задача
Здесь мы сталкиваемся с тонкой проблемой :
. Существует вероятность того, что beginи endотносятся к элементам одного и того же вектора, послеwhere.
Например, если пользователь говорит:
vector<int> items;
for (int i = 0; i < 1000; i++)
items.push_back(i);
items.insert(items.begin(), items.end() - 2, items.end() - 1);
Если Itне является типом указателя, то все в порядке.
Но мы не знаем, поэтому мы должны проверить, что [begin, end)не относится к диапазону, уже находящемуся внутри вектора.
Но как мы это делаем? Согласно C++, если они не ссылаются на один и тот же массив, то сравнение указателей будет неопределенным!
Таким образом, компилятор может ложно сказать нам, что элементы не являются псевдонимами, хотя на самом деле это так, вызывая ненужное O (n )замедление.
Возможное решение и предостережение
Одно из решений состоит в том, чтобы копировать весь вектор каждый раз, чтобы включить новые элементы, а затем выбросить старую копию.
Но это очень медленно в таких сценариях, как в приведенном выше примере, где мы копируем 1000 элементов только для того, чтобы вставить 1 элемент, даже если у нас уже может быть достаточно места.