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

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

Поделиться
Страницы: 1 2 3 4 515 Следующая »
=A=L=X=Постоялецwww4 дек. 201716:16#30
Восстановил историческую справедливость, вот так этот код из первопоста должен был быть написан на C++03:
arr.erase( std::remove_if( arr.begin(), arr.end(), std::bind2nd( std::less<int>(), 10 ) ), arr.end() );

beejahПостоялецwww4 дек. 201716:22#31
Зачем вообще что-то удалять, если можно просто игнорировать.
Panzerschrek[CN]Участникwww4 дек. 201716:58#32
Sbtrn. Devil
Переголова на перекладывание из одного вектора в другой.
MrShoorУчастникwww4 дек. 201721:33#33
Suslik
> size_t new_size = 0;
> for(size_t i = 0; i < vec.size(); i++)
> {
> if(vec[i] >= 10)
> vec[new_size++] = vec[i];
> }
> vec.resize(new_size);
Плюс тебе за олдскульность. А то я уже хотел расстроиться, что никто не написал нормальной реализации, и написать такую сам.
Добавлю от себя небольшую оптимизацию:
size_t removed = 0;
for(size_t i = vec.size()-1; i>=0; i--){
  if (vec[i] < 10){
    removed++;
    vec[i] = vec[vec.size()-removed];
  }
}
vec.resize(vec.size()-removed);
Если порядок не важен, то при проходе от конца к началу мы можем копировать последний элемент в дырку, а потом ресайзнуть контейнер. Это позволит избежать лишнего копирования, что может дать нехилый буст если удаляемых элементов мало.
ud1Постоялецwww4 дек. 201721:39#34
MrShoor
> for(size_t i = vec.size()-1; i>=0; i--){
И тут же допустил баг, тип size_t безнаковый, выражение i >= 0 всегда истина. Надо использовать оператор стремления к нулю:
for (size_t i = vec.size(); i --> 0; )
MrShoorУчастникwww4 дек. 201721:40#35
ud1
> И тут же допустил баг, тип size_t безнаковый, выражение i >= 0 всегда истина.
Ок, я не С++ программист, поэтому тонкости типов С++ могу не знать (я бы вообще int зафигачил бы вместо size_t, но я решил быть "модным" и заюзать правильный тип, что собственно меня и подставило). В остальном же код верный. Но спасибо за замечание

Правка: 4 дек. 2017 21:43

OgraПостоялецwww4 дек. 201721:49#36
MrShoor
> В остальном же код верный.

Ты уверен? Я что-то сомневаюсь. Очень сильно сомневаюсь.

MrShoorУчастникwww4 дек. 201722:00#37
Ogra
> Ты уверен? Я что-то сомневаюсь. Очень сильно сомневаюсь.
Это хорошо. Вот я тебе написал кодец:
http://rextester.com/TKRMY22465
Жду от тебя данных, на которых код будет неверно работать. Очень сильно жду.

upd. А вообще код суслика, и вот этот мой код - это почти классика. Стыдно такое не знать (или забывать про такое).

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

OgraПостоялецwww4 дек. 201722:17#38
MrShoor
Ага, теперь я разобрался. Хитрый алгоритм, но работает. И да, если удаляемых элементов мало и порядок не важен - будет еще и быстро работать.
Код суслика мне самому в голову пришел - видимо все же помню такие алгоритмы, хоть и не все вариации. Эх, надо заново пару книжек по алгоритмам посмотреть, а то все либы, либы...

ud1Постоялецwww4 дек. 201722:20#39
MrShoor
> это почти классика
В чем смысл бежать справа налево и перекладывать один и тот же элемент по нескольку раз?
eMan.LivedПостоялецwww4 дек. 201722:21#40
ud1
for (size_t i = vec.size(); i --> 0; )
Что случится, если скормить пустой вектор?

MrShoor
> Жду от тебя данных, на которых код будет неверно работать. Очень сильно жду.
10 строка:

for(int i = vec.size()-1; i>=0; i--){
Что будет, если кол-во элементов в векторе будет больше, чем может вместить int (size() — беззнаковый, int — знаковый)?
OgraПостоялецwww4 дек. 201722:28#41
ud1
> В чем смысл бежать справа налево и перекладывать один и тот же элемент по
> нескольку раз?

Представь себе массив

[10, 2, 45, 100, 40, 40, 50, 120, 354, 1009]

Удалить надо только один элемент.
При проходе слева направо произойдет 8 перекладываний и сохранится порядок:

[10, 45, 100, 40, 40, 50, 120, 354, 1009]

При проходе справа налево произойдет одно перекладывание, но порядок не сохранится:

[10, 1009, 45, 100, 40, 40, 50, 120, 354]

Соответственно, если элементов мало, а порядок не важен (мы их отсортируем потом, например), то алгоритм на таких данных отработает быстро.

На массиве вроде [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] лучше проходить слева направо.

MrShoorУчастникwww4 дек. 201722:34#42
ud1
> В чем смысл бежать справа налево и перекладывать один и тот же элемент по
> нескольку раз?
Если в большом массиве очень мало удаляемых элементов, то не выполняется лишнее копирование (что в С++ приводит к вызову конструктора копирования например). Тут количество копирований = количеству удаленных элементов.

eMan.Lived
> Что будет, если кол-во элементов в векторе будет больше, чем может вместить int
> (size() — беззнаковый, int — знаковый)?
Грустно будет. Я знал, что к этому придерутся. Реальность такова, что если у тебя в коде массивы на 2 лярда элементов, то все плохо станет гораздо раньше. Но для особо упоротых случаев конечно можно заменить на int64_t. А вот int64_t хватит на ближайшие лет 30-50 точно.

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

ZefickПостоялецwww4 дек. 201722:53#43
MrShoor
> Добавлю от себя небольшую оптимизацию:
    int last = vec.size()-1;
    for(int i = 0; i<=last; i++) {
      if (vec[i] < 10) {
        vec[i--] = vec[last--];
      }
    }
    vec.resize(last+1);
  Почувствуйте разницу, как говорится.
MrShoorУчастникwww4 дек. 201722:54#44
Zefick
> Почувствуйте разницу, как говорится.
Почувствовал. Мало того, что работает неправильно, так еще и стало хуже читаться.
Сразу видно кто умеет в классику, а кто нет. xD

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

Страницы: 1 2 3 4 515 Следующая »

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

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