Удалить наложение из векторов векторов

Question

Что я в основном делаю, так это задаю заданное покрытие, удаляя дубликаты из векторов с одинаковыми номерами.Пример:

У меня есть следующие векторы векторов после сортировки:

{{1,2,3,4,5},{2,3,7,8},{10,11,12}}

СЕЙЧАС, я хотел бы удалить вхождение из вектора 2nd, который равен 2,3, и снова выполнить сортировку...

 {{1,2,3,4,5},{10,11,12},{7,8}}

Я реализовал некоторый код для сортировки векторов векторов, но у меня проблема с удалением вхождений из вектора, который имеет меньший размер?

Функция сортировки:

sort(ROWS.begin(),ROWS.end(),VectorsSort());

Спасибо за помощь.

Answer 1

Разбери это и возьми то, что тебе нужно:

#include <algorithm>
#include <vector>

struct binary_search_pred
{
    typedef bool result_type;

    explicit binary_search_pred(std::vector<int> const& v) : v_(&v) { }

    bool operator ()(int const& i) const
    {
        return std::binary_search(v_->begin(), v_->end(), i);
    }

private:
    std::vector<int> const* v_;
};

struct size_comparison_desc
{
    typedef bool result_type;

    typedef std::vector<int> const& arg_t;
    bool operator ()(arg_t a, arg_t b) const
    {
        return b.size() < a.size();
    }
};

void set_cover(std::vector<std::vector<int> >& vec)
{
    typedef std::vector<std::vector<int> > vec_t;
    typedef vec_t::iterator iter_t;
    typedef vec_t::const_iterator citer_t;

    if (vec.empty() || vec.size() == 1)
        return;

    for (iter_t v = vec.begin() + 1, v_end = vec.end(); v != v_end; ++v)
        for (citer_t p = vec.begin(); p != v; ++p)
            v->erase(
                std::remove_if(v->begin(), v->end(), binary_search_pred(*p)),
                v->end()
            );
    std::sort(vec.begin(), vec.end(), size_comparison_desc());
}

(Обратите внимание, что set_cover требует, чтобы содержащиеся std::vector<int> с данными должны уже быть отсортированы.)

---

РЕДАКТИРОВАТЬ # 1:

Как было запрошено в удаленных комментариях, версия ориентирована на std::map<int, std::vector<int>> вместо std::vector<std::vector<int>> (используйте binary_search_pred из исходного кода):

#include <algorithm>
#include <map>
#include <vector>

void set_cover(std::map<int, std::vector<int> >& m)
{
    typedef std::map<int, std::vector<int> > map_t;
    typedef map_t::iterator iter_t;
    typedef map_t::const_iterator citer_t;

    if (m.empty() || m.size() == 1)
        return;

    for (iter_t v = ++m.begin(), v_end = m.end(); v != v_end; ++v)
        for (citer_t p = m.begin(); p != v; ++p)
            v->second.erase(
                std::remove_if(
                    v->second.begin(),
                    v->second.end(),
                    binary_search_pred(p->second)
                ),
                v->second.end()
            );
}

Обратите внимание, что map здесь всегда будет сортироваться по его ключу, а не по размеру содержащегося vector (это то, что вам нужно). Может быть, вы хотите std::vector<std::pair<int, std::vector<int>>> вместо этого?

---

РЕДАКТИРОВАТЬ # 2:

В соответствии с запросом в удаленных комментариях версия ориентирована на std::vector<std::pair<int, std::vector<int>>> вместо std::map<int, std::vector<int>> (используйте binary_search_pred из исходного кода):

#include <algorithm>
#include <utility>
#include <vector>

struct size_comparison_desc
{
    typedef bool result_type;

    typedef std::pair<int, std::vector<int> > const& arg_t;
    bool operator ()(arg_t a, arg_t b) const
    {
        return b.second.size() < a.second.size();
    }
};

void set_cover(std::vector<std::pair<int, std::vector<int> > >& vec)
{
    typedef std::vector<std::pair<int, std::vector<int> > > vec_t;
    typedef vec_t::iterator iter_t;
    typedef vec_t::const_iterator citer_t;

    if (vec.empty() || vec.size() == 1)
        return;

    for (iter_t v = vec.begin() + 1, v_end = vec.end(); v != v_end; ++v)
        for (citer_t p = vec.begin(); p != v; ++p)
            v->second.erase(
                std::remove_if(
                    v->second.begin(),
                    v->second.end(),
                    binary_search_pred(p->second)
                ),
                v->second.end()
            );
    std::sort(vec.begin(), vec.end(), size_comparison_desc());
}

Answer 2

1. Вам не нужно определять предикат векторной сортировки.Вектор уже определяет operator<, который основан на std::lexicographical_compare.

2. Это то, что вы имеете в виду?

std::for_each(rows.begin(), rows.end(), [](std::vector<int>& row) {
    row.erase(std::remove_if(row.begin(), row.end(), [](int number) -> bool {
        return (number == 2) || (number == 3);
    }), row.end());
});