Как удалить из любого контейнера? - PullRequest
Новая
       68

Как удалить из любого контейнера?

0 голосов
/ 15 декабря 2018

Я бы хотел удалить определенные предметы из контейнера.Проблема в том, что я не знаю, что это за контейнер.Большинство STL-алгоритмов, как известно, не заботятся о контейнере: например, find_if, copy_if и т. Д. Все работают более или менее с любым типом контейнера.

Но как насчет удаления?Для vector -подобных контейнеров существует идиома удаления-стирания, которая, однако, не может применяться к, например, set -подобным контейнерам.Используя специализацию шаблонов или перегрузку, я мог бы специализироваться для определенных контейнеров, но это не масштабируется, когда следует учитывать и другие контейнеры (unordered_set, list, ...).

Мой вопрос: Как реализовать функцию, которая удаляет определенные элементы из любого контейнера эффективно ?Предпочитаемая подпись: 

template<typename Ts, typename Predicate>
void remove_if(Ts& ts, const Predicate& p);

Или, более конкретно: как различить контейнеры, подобные set (быстрая вставка / удаление, нет произвольного заказа), и контейнеры, подобные vector (медленная вставка / удаление, изготовленный на заказ заказ)?Есть ли (обычно используемый) контейнер, который не подходит ни к одной из категорий?

Редактировать: Я только что нашел std::experimental::erase_if, который перегружен для многих (всех?) Контейнеров.То есть я приму решение, только если оно не использует std::experimental.

Ответы [ 2 ]

0 голосов
/ 15 декабря 2018

std::erase и std::erase_if будут частью C ++ 20.См. P1209

Libc ++ (trunk) реализует это уже (по состоянию на вчерашний день :-)), и это будет частью clang 8.0.

0 голосов
/ 15 декабря 2018

Редактировать:

Поскольку отмечено @pasbi, кажется, что у нас уже есть std::experimental::erase_if, который делает именно это!Он будет объединен с std:: в C ++ 20.

Если вы хотите персонализированную реализацию, читайте дальше.

Вам не нужно специализироваться для конкретных контейнеров.Вместо этого вы можете использовать черты типа и SFINAE для определения «категории» контейнера.

Существует ли (обычно используемый) контейнер, который не подходит ни к одной из категорий?

Я бы сказал, да.Есть std::list и std::forward_list, которые имеют .remove_if() функцию-член, которая должна быть быстрее, чем стирание-удаление.

Таким образом, у нас есть три возможных реализации:

Мыиспользуйте .remove_if(), если он доступен (как определено std::experimental::is_detected).
Таким образом, мы обрабатываем std::list и std::forward_list.

В противном случае мы используем удаление-удаление, если это возможно.(Это возможно, если элементы контейнера можно назначать перемещением, что можно проверить с помощью std::is_move_assignable.)
Таким образом, мы обрабатываем все остальные стандартные контейнеры, кроме std::[unordered_]map и std::[unordered_]set.(Это то, что вы называете vector -подобными контейнерами.)

В противном случае мы прибегаем к простому циклу стирания элементов.
Таким образом, мы обрабатываем std::[unordered_]map и std::[unordered_]set.

Пример реализации: 

#include <algorithm>
#include <iterator>
#include <experimental/type_traits>
#include <utility>

inline auto dummy_predicate = [](auto &&){return false;};

template <typename T> using detect_member_remove_if =
    decltype(std::declval<T&>().remove_if(dummy_predicate));

template <typename T, typename F> void remove_if(T &container, F &&func)
{
    using element_t = std::remove_reference_t<decltype(*std::begin(container))>;

    if constexpr (std::experimental::is_detected_v<detect_member_remove_if, T>)
    {
        container.remove_if(std::forward<F>(func));
    }
    else if constexpr (std::is_move_assignable_v<element_t>)
    {
        auto new_end = std::remove_if(std::begin(container), std::end(container),
                                      std::forward<F>(func));
        container.erase(new_end, std::end(container));
    }
    else
    {
        auto it = std::begin(container);
        while (it != std::end(container))
        {
            if (func(*it))
                it = container.erase(it);
            else
                it++;
        }
    }
}

Я бы предпочел что-то без experimental

Вот пользовательская замена для std::experimental::is_detected_v: 

namespace impl
{
    template <typename ...P> struct void_impl {using type = void;};
    template <typename ...P> using void_t = typename void_impl<P...>::type;

    template <typename Dummy, template <typename...> typename A, typename ...B>
    struct is_detected : std::false_type {};

    template <template <typename...> typename A, typename ...B>
    struct is_detected<void_t<A<B...>>, A, B...> : std::true_type {};
}

template <template <typename...> typename A, typename ...B>
inline constexpr bool is_detected_v = impl::is_detected<void, A, B...>::value;

Обратите внимание, что мы не используем C ++ 17 std::void_t, потому что, насколько я знаю, в Clang он по-прежнему работает неправильно.

...