Добрый день, подскажите , пожалуйста, как оптимальным образом удалить список элементов (заданный динамически) из контейнера:

Дан контейнер из 10 элементов

vector<int> vec;

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

int pos_elem[3] = {2, 9, 4};

Как оптимально сделать данное действие?

Здравствуйте, emergen, Вы писали:

E>Добрый день, подскажите , пожалуйста, как оптимальным образом удалить список элементов (заданный динамически) из контейнера:

E>Дан контейнер из 10 элементов

E>

E>vector<int> vec;
E>

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

E>

E>int pos_elem[3] = {2, 9, 4};
E>

E>Как оптимально сделать данное действие?
std::remove_if + собственный предикат?

Здравствуйте, emergen, Вы писали:

E>...
E>Как оптимально сделать данное действие?

С точки зрения скорости — тут оптимальностью и не пахнет. Поиск и удаление в векторе имеют сложность O(N). Возможно нужна другая структура данных вместо вектора. Какая вообще поставлена задача?

Здравствуйте, emergen, Вы писали:

E>Как оптимально сделать данное действие?
Почитать Седжвика?

Здравствуйте, ArtDenis, Вы писали:

AD>С точки зрения скорости — тут оптимальностью и не пахнет.

перечитай условие. "дан вектор из 10 элементов"

Здравствуйте, emergen, Вы писали:

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

E>

E>int pos_elem[3] = {2, 9, 4};
E>

E>Как оптимально сделать данное действие?

pos_elem содержит индексы удаляемых элементов или значения?

Допустим, индексы.
Если решать в лоб, то при удалении элемента все последующие за ним поменяют индекс.

Вариант1.
После удаления i-го элемента пройти по pos_elem и декрементировать индексы, которые > i. (придется бегать по всему массиву pos_elem)

Вариант2.
Последний элемент массива ставится на место удаляемого, а хвост массива отрезается. Попутно проверяется, что если индекс перемещаемого элемента находится в pos_elem, то его индекс нужно подправить(*) (не эффективно, но об этом ниже). Тоже придется бегать по всему массиву pos_elem.
Вариант пригоден, если порядок элементов в массиве не важен.

Вариант 3.
Упорядочить pos_elem по убыванию индексов.
Тогда удаление очередного элемента не будет влиять на индексы стоящих в очереди на удаление.

Вариант 4.
Совместить варианты 2 и 3. Тогда удаляемый элемент гарантированно не будет перемещаться (см. обозначенное "*"), плюс не надо передвигать все элементы в массиве для схлопывания "пустот".


Если в pos_elem хранятся значения, то:

Вариант1.
Воспользоваться советом Carc'а (remove_if), либо вызов remove для каждого элемента из pos_elem.

Вариант2.
Упорядочить содержимое vec и использовать бинарный поиск для нахождения удаляемых элементов.

Вариант3.
Выбрать более другой контейнер, подходящий под задачу.

Здравствуйте, emergen, Вы писали:

E>Дан контейнер из 10 элементов
E>необходимо удалить массив с элементами, элементы для удаления задаются динамически и могут меняться при выполнении программы
E>Как оптимально сделать данное действие?

Оптимально по какому критерию? По количеству строк? По скорости?
Что значит "массив с элементами", и какого он размера? Судя по названию и содержимому, int pos_elem[3] = {2, 9, 4};, это массив индексов. Так индексов или значений?
Может ли там быть стопятьсот (повторяющихся) элементов? Или стопятьсот разных?
Если это индексы, почему бы — для такого небольшого размера контейнера — не заменить массив индексов на битовый вектор, то есть, на двоичное 10-разрядное число?

Что произойдёт с контейнером после удаления элементов: его размер уменьшится, или останется тем же (а оставшиеся элементы сдвинутся к началу, или удалённые просто обнулятся)?
Почему спрашиваю: исходное условие звучит "дан контейнер из 10 элементов". Не "из не более чем 10...", т.е. размер может быть прибит гвоздями — например, это какие-то опыты в 10-мерном векторном пространстве.

Короче говоря: учиться, учиться и учиться — как языку С++, так и искусству задавать вопросы.

Здравствуйте, emergen, Вы писали:

E>Дан контейнер из 10 элементов

E>

E>vector<int> vec;
E>

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

E>

E>int pos_elem[3] = {2, 9, 4};
E>

E>Как оптимально сделать данное действие?


Как вариант — создать новый вектор (с установкой capacity) и скопировать туда только нужные элементы, а старый вектор удалить.
Сложность O(N).

Здравствуйте, andy1618, Вы писали:

A>Как вариант — создать новый вектор (с установкой capacity) и скопировать туда только нужные элементы, а старый вектор удалить.
A>Сложность O(N).

... где N — это размер... хм, размер которого вектора: исходного, откуда надо повыбрасывать, или справочного, что надо повыбрасывать?

Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, andy1618, Вы писали:

A>>Как вариант — создать новый вектор (с установкой capacity) и скопировать туда только нужные элементы, а старый вектор удалить.
A>>Сложность O(N).

К>... где N — это размер... хм, размер которого вектора: исходного, откуда надо повыбрасывать, или справочного, что надо повыбрасывать?

Имелся ввиду исходный вектор.
Правда, поскольку справочный вектор несортированный, то для эффективной реализации понадобится ещё дополнительная операция,
но она тоже уложится в O(N) — например, сортировка подсчётом или, если полезные данные в исходном векторе ограничены неким диапазоном,
то можно прямо в нём промаркировать удаляемые элементы каким-то волшебным значением.

UPD: кстати, тогда можно ещё проще сделать — если будет отсортированный справочный вектор, то можно сделать
перепаковку исходного вектора прямо in-place, сдвигая к началу только нужные элементы, а потом отсечь хвост с помощью resize.

Здравствуйте, emergen, Вы писали:
E>Добрый день, подскажите , пожалуйста, как оптимальным образом удалить список элементов (заданный динамически) из контейнера:
E>Дан контейнер из 10 элементов
для 10 элементов без разницы как это делать. проще всего remove_if

если же реально элементов много и вам нужно быстро удалять из этого множества другое множество, то тут напрашивается другой контейнер — set.