Скрытые обсёры. Remove-erase idiom
В этом посте я рассказал про то, что такое remove-erase идиома. И начал я этот пост с объяснения эффективного способа удаления элементов из неупорядоченного массива. Этот алгоритм все еще прекрасный и волшебный, эффективнее него ничего нет в этом случае. Однако я сказал, что для упорядоченного массива нет такого эффективного способа решения проблемы удаления элементов. Под эффективным алгоритмом в этом случае я понимаю алгоритм с линейным временем работы.
Мало того, из поста как бы логично вытекает, что алгоритм std::remove работает так же на свопах элементов. Это конечно неверно. Как и высказывание из предыдущего абзаца. Спасибо админу Денису, что указал на мой затупок.
Это просто еще один пример того, что каждое ваше убеждение нужно подвергать сомнениям. Особенно, если вы транслируете это убеждение на других людей.
Откуда у меня в голове это было? Как-то раз на собесе мне задали задачку, что надо эффективно удалить нужные элементы из неупорядоченного массива. Я, как образцово-показательный кандидат, рассказал тот алгоритм со свопами и запрогал его. Тут мне прилетает вопрос. А нельзя ли как-нибудь элегантнее решить эту задачу, а то букав слишком много? Из каких-то глубочайших глубин(на тот момент) моего сознания я достал remove-erase идиому и мне засчитали ответ на вопрос верным. И я сложил 2 и 2 и объединил у себя в голове алгоритм со свопами и remove-erase идиому. Я не оправдываюсь, что во всем виноват интервьюер. Просто говорю, как могут ложные утверждения в голове появляться. Как говорил великий: "для кого-то, наверное, это будет оправданием, а я просто объясняю".
Так и что. Алгоритм std::remove действительно эффективно удаляет элементы из массива и при этом сохраняет относительный порядок оставшихся элементов. Делает он это, конечно, не так элегантно, как способ со свопами, но тоже за линейное время.
И я даже записал мой первый видос(!), в котором я объясняю то, как на самом деле работает std::remove. И даже выложил его на ютуб! Вот ссылочка на него жмак
Монтаж, сценарий и звук, естественно, на высоте(нет). Но это первое видео в жизни, слишком много неопределенностей было на всех этапах его создания. Недостатков много, но уже хотелось его побыстрее залить, а то оно на протяжении 2-х недель не давало мне покоя. Дальше будет лучше.
Видео в первую очередь для вас, дорогих подписчиков. Но почему бы не воспользоваться возможностями платформы для привлечения аудитории. Если у кого-то есть желание поддержать проект, то можете посмотреть второй раз на минимальной скорости и с включенными субтитрами. Алгоритмам ютуба так приятнее будет продвигать видос.
Критика, любые комментарии - все приветствуется. Буду рад дельным советам.
Stay self-critique. Stay cool.
В этом посте я рассказал про то, что такое remove-erase идиома. И начал я этот пост с объяснения эффективного способа удаления элементов из неупорядоченного массива. Этот алгоритм все еще прекрасный и волшебный, эффективнее него ничего нет в этом случае. Однако я сказал, что для упорядоченного массива нет такого эффективного способа решения проблемы удаления элементов. Под эффективным алгоритмом в этом случае я понимаю алгоритм с линейным временем работы.
Мало того, из поста как бы логично вытекает, что алгоритм std::remove работает так же на свопах элементов. Это конечно неверно. Как и высказывание из предыдущего абзаца. Спасибо админу Денису, что указал на мой затупок.
Это просто еще один пример того, что каждое ваше убеждение нужно подвергать сомнениям. Особенно, если вы транслируете это убеждение на других людей.
Откуда у меня в голове это было? Как-то раз на собесе мне задали задачку, что надо эффективно удалить нужные элементы из неупорядоченного массива. Я, как образцово-показательный кандидат, рассказал тот алгоритм со свопами и запрогал его. Тут мне прилетает вопрос. А нельзя ли как-нибудь элегантнее решить эту задачу, а то букав слишком много? Из каких-то глубочайших глубин(на тот момент) моего сознания я достал remove-erase идиому и мне засчитали ответ на вопрос верным. И я сложил 2 и 2 и объединил у себя в голове алгоритм со свопами и remove-erase идиому. Я не оправдываюсь, что во всем виноват интервьюер. Просто говорю, как могут ложные утверждения в голове появляться. Как говорил великий: "для кого-то, наверное, это будет оправданием, а я просто объясняю".
Так и что. Алгоритм std::remove действительно эффективно удаляет элементы из массива и при этом сохраняет относительный порядок оставшихся элементов. Делает он это, конечно, не так элегантно, как способ со свопами, но тоже за линейное время.
И я даже записал мой первый видос(!), в котором я объясняю то, как на самом деле работает std::remove. И даже выложил его на ютуб! Вот ссылочка на него жмак
Монтаж, сценарий и звук, естественно, на высоте(нет). Но это первое видео в жизни, слишком много неопределенностей было на всех этапах его создания. Недостатков много, но уже хотелось его побыстрее залить, а то оно на протяжении 2-х недель не давало мне покоя. Дальше будет лучше.
Видео в первую очередь для вас, дорогих подписчиков. Но почему бы не воспользоваться возможностями платформы для привлечения аудитории. Если у кого-то есть желание поддержать проект, то можете посмотреть второй раз на минимальной скорости и с включенными субтитрами. Алгоритмам ютуба так приятнее будет продвигать видос.
Критика, любые комментарии - все приветствуется. Буду рад дельным советам.
Stay self-critique. Stay cool.