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

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

Страницы: 1 2 3 4 517 Следующая »
#30
16:16, 4 дек. 2017

Восстановил историческую справедливость, вот так этот код из первопоста должен был быть написан на C++03:

arr.erase( std::remove_if( arr.begin(), arr.end(), std::bind2nd( std::less<int>(), 10 ) ), arr.end() );


#31
16:22, 4 дек. 2017

Зачем вообще что-то удалять, если можно просто игнорировать.

#32
16:58, 4 дек. 2017

Sbtrn. Devil
Переголова на перекладывание из одного вектора в другой.

#33
21:33, 4 дек. 2017

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);
Если порядок не важен, то при проходе от конца к началу мы можем копировать последний элемент в дырку, а потом ресайзнуть контейнер. Это позволит избежать лишнего копирования, что может дать нехилый буст если удаляемых элементов мало.
#34
21:39, 4 дек. 2017

MrShoor
> for(size_t i = vec.size()-1; i>=0; i--){
И тут же допустил баг, тип size_t безнаковый, выражение i >= 0 всегда истина. Надо использовать оператор стремления к нулю:

for (size_t i = vec.size(); i --> 0; )
#35
21:40, 4 дек. 2017

ud1
> И тут же допустил баг, тип size_t безнаковый, выражение i >= 0 всегда истина.
Ок, я не С++ программист, поэтому тонкости типов С++ могу не знать (я бы вообще int зафигачил бы вместо size_t, но я решил быть "модным" и заюзать правильный тип, что собственно меня и подставило). В остальном же код верный. Но спасибо за замечание

#36
21:49, 4 дек. 2017

MrShoor
> В остальном же код верный.

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

#37
22:00, 4 дек. 2017

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

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

#38
22:17, 4 дек. 2017

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

#39
22:20, 4 дек. 2017

MrShoor
> это почти классика
В чем смысл бежать справа налево и перекладывать один и тот же элемент по нескольку раз?

#40
22:21, 4 дек. 2017

ud1

for (size_t i = vec.size(); i --> 0; )
Что случится, если скормить пустой вектор?

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

for(int i = vec.size()-1; i>=0; i--){
Что будет, если кол-во элементов в векторе будет больше, чем может вместить int (size() — беззнаковый, int — знаковый)?
#41
22:28, 4 дек. 2017

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] лучше проходить слева направо.

#42
22:34, 4 дек. 2017

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

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

#43
22:53, 4 дек. 2017

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);
  Почувствуйте разницу, как говорится.
#44
22:54, 4 дек. 2017

Zefick
> Почувствуйте разницу, как говорится.
Почувствовал. Мало того, что работает неправильно, так еще и стало хуже читаться.
Сразу видно кто умеет в классику, а кто нет. xD

Страницы: 1 2 3 4 517 Следующая »
ФлеймФорумПрограммирование

Тема в архиве.