Курорт на std :: vector vs std :: insert

Question

У меня есть отсортированный std::vector относительно небольшого размера (от 5 до 20 элементов). Я использовал std::vector, так как данные непрерывны, поэтому у меня скорость из-за кеша. В определенный момент мне нужно удалить элемент из этого vector.

У меня теперь есть сомнение: какой самый быстрый способ удалить это значение между двумя вариантами ниже?

1. установки этого элемента в 0 и вызовите sort реорганизовать: это имеет сложности, но элементы находятся на одной и той же строке кэша.
2. звоните erase, который скопирует (или memcpy, кто знает?) Все элементы после него из 1-го места (мне нужно исследовать скрытое удаление стирания).

Знаете ли вы, что быстрее?

Я думаю, что такой же подход можно было бы подумать о вставке нового элемента без попадания максимальной емкости вектора.

С уважением

AFG

Answer 1

Если вы не заботитесь о порядке элементов, вы можете быть в состоянии поменять элемент с последним.

void Remove(std::vector<Object> &vec, iterator i) { 
    iterator last = vec.end()-1; 
    if (i != last) 
     std::swap(*i, *last); 
    vec.erase(last); 
} 

Вы упоминаете настройки элемента 0. Если это означает, что у вас есть указатели, то вам не нужен своп:

void Remove(std::vector<Object *> &vec, iterator i) { 
    vec[i] = vec.back(); 
    vec.erase(vec.end()-1); 
} 

Если вы заботитесь о порядке, то ваш второй вариант использование с помощью стирания() сохранит его и выполнит минимальный объем работы. Это почти наверняка будет быстрее, чем прибегать.