Реверсирование содержимого набора в C ++

Question

Я хочу перевернуть содержимое std::set (не просто итерацию, а обратное, но и реверсирование содержимого).Я обнаружил, что std::set принимает сравнение как функциональный объект для своего конструктора.Поэтому я придумал следующий код, чтобы сделать то же самое:

#include <set>
using namespace std;
struct Comparator
{
    Comparator(bool g) : m_g(g){}
     bool operator()(int i1, int i2) const
    {
        if(m_g)
        {
            return i1>i2;
        }
        return i1<i2;
    }
        bool m_g;
};

int main(int argc, char** argv)
{
    Comparator l(false);
    set<int,Comparator> a(l);
    a.insert(1);
    a.insert(2);
    a.insert(3);
    Comparator g(true);
    set<int,Comparator> b(g);
    copy(a.begin(), a.end(), inserter(b, b.begin()));
    a = b;
    return 0;
}

Кажется, это работает в VC9.Но правильный ли этот код?Мои сомнения возникают из-за того, что у моего Comparator есть состояние, связанное с ним.Разрешено ли компараторам иметь состояния?

Answer 1

Да, это законно.Учтите, что если бы компаратору не было разрешено иметь состояние, не было бы никакого смысла позволять вам передавать компаратор в качестве параметра конструктора.:)

Пока компаратор обеспечивает строгий слабый порядок, это нормально (что, помимо прочего, означает, что он должен быть последовательным. Вы не можете изменить его состояние на полпути, так чтоон заказывает элементы по-разному)

Answer 2

Это нормально, но это излишне сложно.

Вы можете просто использовать std::less (значение по умолчанию для этого параметра шаблона!) Или std::greater из стандартной библиотеки.Они предоставляются <functional>.

Answer 3

Более общее решение. boost :: assign и c ++ 11 просто для удобства (и забавный автореверс )

    # include <iostream>
# include <set>
# include <boost/assign.hpp>


using namespace boost::assign;

template <typename CL , typename Pred>
struct revPred {
    revPred (Pred pred) : pred_(pred) {}
bool operator()(const CL & a, const CL& b)
{
 return pred_(b,a);
 }
Pred pred_;
};

template <typename CL , typename Pred, typename alloc>
inline
std::set<CL,revPred<CL,Pred>,alloc> reverseSet(const std::set<CL,Pred,alloc> & set) {
    std::set<CL,revPred<CL,Pred>,alloc> res(revPred<CL,Pred>(set.key_comp()));
    std::copy(set.begin(), set.end(), std::inserter(res, res.begin())); 
    return res;
    }

int main()
{
 std::set<int> s; s += 0 , 1 , 2 , 3;
 std::for_each(s.begin(), s.end(), [](int x) { std::cout << x << " "; }); 
 std::cout << std::endl;
 auto reverse = reverseSet(s);
 std::for_each(reverse.begin(), reverse.end(), [](int x) { std::cout << x << " "; }); 
 std::cout << std::endl;
 return 0; 
}

Answer 4

Это нормально, поскольку ваше сравнение не изменяется динамически и обеспечивает строгое слабое упорядочение.

Однако, если вы делаете это так, чтобы тип набора был одинаковым даже при изменении порядка, я мог бы предложить альтернативную идею. Вместо этого сравнения вы используете два различных типа набора с std::less и std::greater и используете интерфейс итератора, как это делает стандартная библиотека, а не интерфейс контейнера, который зависит от всех параметров шаблона.

И, наконец, как отмечено в ответе @parapura rajkumar, вы должны использовать конструктор пары итераторов, а не std::copy:

// Assuming my other comments don't apply, modify as needed if they do:
Comparator g(true);
set<int, Comparator> b(a.rbegin(), a.rend(), g);

Answer 5

В вашем коде нет ничего плохого.

И нет ничего плохого в том, что компараторы имеют состояние.

Answer 6

Если у вас достаточно большой набор, вы уже заплатили штраф O (NlogN), чтобы создать сбалансированное двоичное дерево.Слепая вставка в набор назначения, вам придется снова заплатить штраф.

Рассмотрите возможность использования одной из этих перегрузок вставки.

 void insert ( InputIterator first, InputIterator last );
 iterator insert ( iterator position, const value_type& x );

Вставка диапазона имеет линейную сложность, если [first,последний) отсортированы уже.

Answer 7

Вам не нужно предоставлять функциональный объект, который поддерживает состояние. Просто используйте обычную функцию, и она должна делать эту работу. Pls. не против использования лямбды Используется как ярлык для печати. ​​

typedef bool (*Cmp)(int x, int y);

bool Compare(int x, int y)
{
    return x < y;
}


bool CompareR(int x , int y)
{
    return !Compare(x, y);
}

 void SetReverse()
{

    std::set<int, Cmp> s1(Compare);

    s1.insert(1);
    s1.insert(3);
    s1.insert(2);
    s1.insert(4);

    std::for_each(s1.begin(), s1.end(), [](int x) { std::cout << x << "\n"; });

    std::set<int, Cmp> s2(CompareR);

    s2.insert(s1.begin(), s1.end());
    std::for_each(s2.begin(), s2.end(), [](int x) { std::cout << x << "\n"; });

          s1 = s2;

}