Блог

Я хочу изменить содержимое a std::set (не просто повторяя его в обратном порядке, а изменяя содержимое iteslf). Я обнаружил, что 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. Но корректен ли этот код? Мои сомнения возникают из-за того, что у my Comparator есть состояние, связанное с ним. Разрешено ли компараторам иметь состояния?

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

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

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

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

Более общее решение. 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 amp; a, const CLamp; 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> amp; 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; 
}
  

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

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

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

Однако, если вы делаете это так, чтобы тип набора оставался неизменным даже при изменении порядка, я мог бы предложить альтернативную идею. Вместо этого сравнения вы используете два разных типа набора с 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);
  

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

 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;

}
  

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

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

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

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