Самый быстрый метод поиска и удаления элементов из отсортированного вектора целых чисел в переполнении стека

Я бы, наверное, сделал что-то вроде:

std::vector<int> temp;

std::set_difference(a.begin(), a.end(),
b.begin(), b.end(),
std::back_inserter(temp));
std::swap(a, temp);

Редактировать на основе отредактированного вопроса:

Учитывая, что ваш a вектор существенно больше вашего b вектор, есть второй вопрос, который я хотел бы рассмотреть: вам нужно a остаться отсортированным после завершения?

Если перестановка элементов в a разрешено, тогда вы можете существенно улучшить скорость: вместо того, чтобы делать удаление / стирание, чтобы удалить элементы из середины a, вы можете поменять элемент, который будет удален, с последнего элемента aзатем удалите его с конца (что имеет постоянную сложность). Это делает постоянные удаления, поэтому общая сложность составляет O (N log M) (где N = b.size () и M = a.size ()).

Если вам нужно поддерживать порядок, вы все равно можете немного улучшить скорость: вместо удаления элементов из a, затем немедленно стереть удаленный элемент, сделать std::remove_if найти все элементы a это необходимо удалить, а затем один раз (когда это будет сделано) сделать одно удаление, чтобы удалить все эти элементы.

В настоящее время вы используете отдельный вызов remove для каждого элемента a что вы удалите. Все элементы a после каждой точки удаления копируются (или перемещаются, если применимо) для каждого remove, Это означает, что если вы удалите 10 элементов из aкопируешь (в среднем) половину a В 10 раз больше Используя один remove_if вместо этого вы копируете каждый элемент a только однажды.

К несчастью, remove_if не дает вам хороший способ воспользоваться заказом в b, Вы можете использовать бинарный поиск, который помогает некоторым, но не так сильно, как хотелось бы.

Если вы не против написания собственного цикла, вы можете в полной мере воспользоваться тем, что оба a а также b отсортированы, примерно так:

#include <vector>
#include <iostream>

// Compute the difference between two "set"s in-place. Each 'set' must be a
// sorted sequence.
//
template <class FwdIt, class InIt>
FwdIt
inplace_set_difference(FwdIt b1, FwdIt e1, InIt b2, InIt e2) {
FwdIt pos = b1;
while (pos != e1 && b2 != e2) {
if (*pos < *b2)
*b1++ = *pos++;
else if (*b2 < *pos)
++b2;
else
++pos;
}
while (pos != e1)
*b1++ = *pos++;
return b1;
}

int main() {
std::vector<int> a{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 };
std::vector<int> b{ 2, 5, 9 };

auto it = inplace_set_difference(a.begin(), a.end(), b.begin(), b.end());
a.erase(it, a.end());

for (auto i : a)
std::cout << i << '\t';
}

Если вы хотите сделать это максимально универсальным, вы, вероятно, захотите изменить его, чтобы использовать только постинкремент на итераторах, позволяя пользователю передавать оператор сравнения вместо использования < непосредственно и т. д. Они оставлены как страшное «упражнение для читателя».

Вероятно, стоит отметить, что это в основном тот же алгоритм, что и set_difference обычно используется, только с незначительной регулировкой для работы на месте. Это вызывает существенные изменения в интерфейсе: поскольку он может (и создает) повторяющиеся элементы в коллекции, он может быть применен к отсортированной последовательности (vector, deque, hash и т. Д.), Но не в ассоциативный контейнер ([unordered_][multi_](set|map)).

Так как это траверсы a а также b ровно по одному O(N + M), но так как мы начинаем с идеи, что M(= b.size ()) мало, это эффективно O(N)

Примечание: в тестовом коде интенсивно используются функции C ++ 11 (например, для инициализации двух векторов), но я считаю, что сама реализация алгоритма должна быть в порядке в C ++ 98/03.