Флейм
GameDev.ru / Флейм / Форум / C++03 - удалить из вектора целых элементы меньше 10 (11 стр)

C++03 - удалить из вектора целых элементы меньше 10 (11 стр)

Поделиться
Страницы: 110 11 12 1317 Следующая »
1 frag / 2 deathsУчастникwww6 дек. 201723:47#150
CasDev
> Тип коллекции выбирается. vector / deque (не помню название - в обе стороны
> растет), ordered / unordered set или что-то такое.
В таких рамках можно менять. Только у них интерфейс одинаковый, поэтому проблем нет, и v.erase(1,2) одинаково будет рабочий.
А вот вектор/лист менять на ходу - это бред.
CasDevПостоялецwww7 дек. 201718:16#151
1 frag / 2 deaths
> А вот вектор/лист менять на ходу - это бред.

У вектора плохо с вставкой, у листа - хорошо. Если у тебя 100-1000 элементов, и предполагается помимо перебора и энергичная вставка/удаление (что само по себе - обычное дело), то как раз имеет смысл смотреть, что быстрее будет работать.

1 frag / 2 deathsУчастникwww7 дек. 201719:39#152
CasDev
> Если у тебя 100-1000 элементов, и предполагается помимо перебора и энергичная
> вставка/удаление (что само по себе - обычное дело),
Вставка куда? В конец у вектора отличная вставка. А если важен порядок, то поиск места для вставки в листе печальный.
ArochПостоялецwww7 дек. 201720:33#153
1 frag / 2 deaths
> то поиск места для вставки в листе печальный.
тебе про вставку ты про поиск /_-
Вставка/удаление зачастую нужна при обходе и у нас уже есть нужный итератор.
1 frag / 2 deathsУчастникwww7 дек. 201720:41#154
Aroch
Дык а куда в середину вставлять-то?

Aroch
> Вставка/удаление зачастую нужна при обходе и у нас уже есть нужный итератор.
Например?

ArochПостоялецwww7 дек. 201720:49#155
1 frag / 2 deaths
> Например?
пройтись по всем элементам, найти те что удовлетворяют определенному критерию удалить их и вставить вместо них два новых.
ArochПостоялецwww7 дек. 201720:59#156
Или более простой пример там где у меня используется список (не stl):
+ Показать

Заодно подумай почему вариант в закомментированной строке будет не верным.
1 frag / 2 deathsУчастникwww7 дек. 201721:07#157
Aroch
> Или более простой пример там где у меня используется список (не stl):
Дык тут O(N) что вектор что лист, разве что у тебя искомый ключ в самом начале где-то.
А при равной сложности вектор по любому на практике быстрее.

Aroch
> пройтись по всем элементам, найти те что удовлетворяют определенному критерию
> удалить их и вставить вместо них два новых.
O(N) что вектор, что лист.

ArochПостоялецwww7 дек. 201721:31#158
1 frag / 2 deaths
> O(N) что вектор, что лист.
ну-ну а вставка/удаление уже куда то делись?
1 frag / 2 deathsУчастникwww7 дек. 201722:04#159
Aroch
> ну-ну а вставка/удаление уже куда то делись?
Думаешь, я не смогу для вектора без квадрата сделать?
Подсказка: на инплейс иногда можно и забить.
ArochПостоялецwww7 дек. 201722:20#160
1 frag / 2 deaths
> Думаешь, я не смогу для вектора без квадрата сделать?
> Подсказка: на инплейс иногда можно и забить.
Можно и без квадрата, только толку, возьми коллекцию с приличным размером и твой вектор накроется медным тазом.
1 frag / 2 deathsУчастникwww7 дек. 201722:31#161
Aroch
> Можно и без квадрата, только толку, возьми коллекцию с приличным размером и
> твой вектор накроется медным тазом.
Боишься, что в память не влезет промежуточный результат рядом с оригиналом? Лист-то раньше раком встанет.
ArochПостоялецwww7 дек. 201722:38#162
1 frag / 2 deaths
/_-
desssПостоялецwww7 дек. 201722:39#163
Aroch
> Можно и без квадрата, только толку, возьми коллекцию с приличным размером и твой вектор накроется медным тазом.
На коллекции такого размера, деаллокация твоего листа накроет медным тазом вообще всё.

Использование списка оправдано довольно в редком количестве случаев:
1. Если в коллекции важен порядок элементов и они в него добавляются и удаляются, это в подавляющем количестве случаев стек или очередь.
2. Если нужно часто удалять элементы в случайном порядке, то часто тебе не важен порядок элементов и удалять их можно за константу свапая с последним.
3. Если же нужно удалять элементы в случайном порядке и и тебе важен порядок элементов, то можно удалять элементы банчами:
    это как раз задача из названия темы, и кучу элементов можно удалить за один N.
    Если архитектурно не можешь удалить всё, что нужно за один вызов функции, то есть несколько способов амортизации:
    * удалять элементы свапом с последним, а при доступе сортировать почти отсортированный массив.
    * еще эффективнее удалять элементы свапом с последним попутно считая сколько удалено, а при доступе восстановить отсортированность за один N
    * если, у элементов нет отношения, а только порядок добавления, то кешировать индексы удаляемых элементов, а при доступе удалять их все за один N
4. Производительность списка и так не высока и на порядок ниже вектора, но после большого количества вставок и удалений деградирует в ноль.
5. Может нужен не список а словарь?

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

Правка: 7 дек. 2017 22:59

1 frag / 2 deathsУчастникwww7 дек. 201722:48#164
desss
> Кажется один неопровержимый случай, это когда элементы коллекции не должны
> реаллоцироваться в памяти.
Массив указателей на блоки из 1024 элементов.
Также я зачем-то мутил буфер из 32 векторов, первый на 64 элемента, второй тоже на 64, третий на 128, четвёртый на 256 итд

Aroch
Ы?

Правка: 7 дек. 2017 22:49

Страницы: 110 11 12 1317 Следующая »

/ Форум / Флейм / Программирование

2001—2017 © GameDev.ru — Разработка игр