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

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

Поделиться
Страницы: 13 4 5 617 Следующая »
eMan.LivedПостоялецwww4 дек. 201722:57#45
ud1
А, постдекремент же. Тогда да. :-)
MrShoorУчастникwww4 дек. 201722:57#46
Zefick
А не, походу ошибки нет, ибо там у тебя копирование в vec[i--], а не в vec[ i ]. Но читается один фиг хуже. Нужно голову напрягать на всех этих --

Правка: 4 дек. 2017 22:58

ud1Постоялецwww4 дек. 201723:07#47
eMan.Lived
> Что случится, если скормить пустой вектор?
И что случится? По мне все в порядке.

MrShoor
> Тут количество копирований = количеству удаленных элементов.
Неплохо, но можно еще меньше.

Кажись нашел самый эффективный и компактный способ

v.erase(std::partition(v.begin(), v.end(), [](int v){return v >= 10;}), v.end());

http://www.cplusplus.com/reference/algorithm/partition/

Правка: 4 дек. 2017 23:09

kiparПостоялецwww4 дек. 201723:12#48
ud1
разве remove_if из #0 не будет эффективнее, ведь ему не надо делать swap, только копировать те элементы которые сохранятся в начало?
ZefickПостоялецwww4 дек. 201723:14#49
MrShoor
> так еще и стало хуже читаться.
  Может просто дело в том, что чужой код всегда читается хуже? Я об этом уже говорил, но ответили, что любой программист подобную лапшу всегда читает за две секунды. Вот и проверили, кто программист и умеет читать код, а кто нет :)

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

ud1Постоялецwww4 дек. 201723:23#50
kipar
Почитал про remove_if и насколько понял, он сохраняет порядок неудаленных элементов. Поэтому при удалении одного только первого элемента, ему придется двигать все остальные элементы. Так что partition должен быть эффективнее. Остается конечно неэффективность, что удаляемые элементы свапаются.
MrShoorУчастникwww4 дек. 201723:26#51
ud1
> Неплохо, но можно еще меньше.
Чет сомневаюсь. Максимум можно на хвостике сэкономить если завести еще один булевый флаг.

ud1
> Кажись нашел самый эффективный и компактный способ
Жесть какая-то на эльфийском. В реальности же перфоманс судя по коду будет хуже. Это и 2 цикла вместо одного (лишние проверки first==last), это и swap, который делает аж 3 копирования вместо одного. Ну и читабельность опять же имхо чутка пострадала. Классику может читать любой, а вот это v.erase(std::partition только тот, кто хорошо знает std.
Так что старинный квадртаногнездовой алгоритм рулид.

ud1Постоялецwww4 дек. 201723:29#52
MrShoor
> Чет сомневаюсь.
Ну вот же уже приводили пример - удалять все элементы кроме последнего. Для этого надо последний элемент перенести на первое место и все. У тебя же он будет копироваться N раз, пока с правой позиции не приедет в первую.

А std надо по любому знать. Многие вещи можно написать компактнее и крассивее. Ради того оно и придумано, что это стандарт, чтоб люди пользовались, могли бегло читать, понимать, а не приходилось всматриваться в тучи вручную написанных циклов. В общем как цикл в этой задаче не напиши, читаться он будет фигово. А std если не знаешь, всегда можно доку глянуть, там все толково написано и с примерами. В общем стандартое api лучше великов.

Правка: 4 дек. 2017 23:41

MrShoorУчастникwww4 дек. 201723:36#53
Zefick
>   Может просто дело в том, что чужой код всегда читается хуже?
Забавно, почему тогда код суслика мною отлично прочитался. Под "читается хорошо" я имею ввиду насколько просто понять, что здесь сейчас происходит.
Давай я тебе покажу, что в твоем коде плохо:
    int last = vec.size()-1;
    for(int i = 0; i<=last; i++) { //last меняется внутри цикла, т.е. проитерируется не весь массив
      if (vec[i] < 10) {
        vec[i--] = vec[last--]; //тут вообще надо напрячь извилины что куда скопируется
      }
    }
    vec.resize(last+1);
Итого у тебя лишняя зависимость в итерациях по массиву от кода внутри. При этом реальных итераций цикл выполнит больше, чем last за счет i-- (и количество реальных итераций неявно окажется равным начальной длине массива). Так что ну нафиг эту зависимость.
Теперь мой код:
    int removed = 0; 
    for(int i = vec.size()-1; i>=0; i--){ //четко понятно, что итераций будет == исходному размеру массива и что проходим с конца
      if (vec[i] < 10){
        removed++;  //увеличиваем количество удаленных элементов
        vec[i] = vec[vec.size()-removed]; //копируем элемент, "выпавший" за границу массива
      }
    }
    vec.resize(vec.size()-removed);

SuslikМодераторwww5 дек. 20170:28#55
хороший, годный тред где каждый может прийти, выложить на стол, сравнить, по-дружески обменяться парой скрытых оскорблений. всё в лучших традициях :D
MrShoorУчастникwww5 дек. 20170:36#56
Suslik
> хороший, годный тред где каждый может прийти, выложить на стол, сравнить,
> по-дружески обменяться парой скрытых оскорблений. всё в лучших традициях :D
Ты практически саму суть, самую её мякотку сейчас описал. Никто бы не сидел на геймдеве, если тут было по другому. Собственно это одна из ключевых причин почему gamedev.ru и выжил, а тот же mirgames.ru загнулся. Эх блин как же жалко mirgames...
1 frag / 2 deathsУчастникwww5 дек. 20170:45#57
ud1
> И тут же допустил баг, тип size_t безнаковый, выражение i >= 0 всегда истина
петушиный беззнаковый цикл, кстати привет кантонажнику
Sbtrn. DevilПостоялецwww5 дек. 20170:55#58
Panzerschrek[CN]
> Переголова на перекладывание из одного вектора в другой.
Зато O(1). Плюс-минус расходы на реаллокацию, но у вектора они всё равно amortized O(1), плюс можно соптимизировать через reserve.
entrywayПостоялецwww5 дек. 20170:59#59
Из кресто-вариантов голосую за версию desss. Ничего лишнего, код понятный барану. Хотя и придется спрятать в функцию.

Правка: 5 дек. 2017 2:38

Страницы: 13 4 5 617 Следующая »

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

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