Унификация ассоциативных STL-контейнеров шаблонным параметром — компаратором

    Рассмотрим код:
    std::multiset<int> set0, set1;
    for (auto it = set0.begin(); it != set0.end(); ++it) {
    	// длинная
    	// обработка
    	// *it
    }
    for (auto it = set1.rbegin(); it != set1.rend(); ++it) {
    	// длинная
    	// обработка
    	// *it
    }
    

    Обработка в телах циклов — одинаковая, иными словами требуется одинаково обработать элементы двух мультимножеств: первого — в прямом порядке, второго — в обратном.

    Задача — объединить эти два цикла приблизительно следующим образом:
    size_t const N = 2;
    std::multiset<int> sets[N] = {/* как инициализировать? */};
    for (size_t i = 0; i < N; ++i) {
    	for (auto const& val: sets[i]) {
    		// длинная
    		// обработка
    		// val
    	}
    }
    

    Понятно, что поскольку для цикла обработки set1 элементы перебираются в обратном порядке, а в sets[1] — в прямом, для сохранения порядка обработки нужно чтобы в sets[1] элементы хранились в обратном порядке по отношению к set1. В ассоциативных контейнерах STL предусмотрен шаблонный параметр — компаратор, по умолчанию имеющий значение std::less. Так что в первом приближении для того чтобы заставить заработать код нужно инициализировать sets приблизительно следующим образом:
    std::multiset<int> sets[N] = {std::multiset<int, std::less>(), std::multiset<int, std::greater>()};
    

    Классы std::multiset<int, std::less> и std::multiset<int, std::greater> — разные и не имеют общего предка, поэтому их нельзя хранить в одном массиве и приведенный код попросту не скомпилируется. (Кстати, итератеры std::multiset::const_iterator и std::multiset::const_reverse_iterator — также различные классы без общего предка, поэтому массивом итераторов вместо массива контейнеров задачу также не решить). Задача сводится к унификации контейнеров с целью хранения их в общем массиве.

    В ассоциативных контейнерах STL компаратор является параметром не только типа, но и каждого экземпляра контейнера. Для тривиальных случаев, как std::less по умолчанию, класс-компаратор не содержит никаких данных и, следовательно, все контейнеры выполняют одну и ту же операцию сравнения, в частности, хранят элементы в одном и том же порядке. Для более сложного случая можно хранить в компараторе данные, например, о порядке сортировки. В этом случае разные экземпляры контейнеров одного и того же класса будут сортировать элементы по разному в зависимости от значения поля в экземляре компаратора, который в свою очередь является полем экземпляра контейнера. Итак, класс компаратора, позволяющего сравнивать по разному:
    template <typename T> class Comparator {
    public:
    	bool operator()(const T& l, const T& r) const {
    		return ASC == order_ ? (l < r) : (l > r);
    	}
    	static Comparator const& Asc() {
    		return asc_;
    	}
    	static Comparator const& Desc() {
    		return desc_;
    	}
    private:
    	enum Order_ {ASC, DESC} const order_;
    	Comparator(Order_ order) : order_(order) {};
    	static Comparator asc_;
    	static Comparator desc_;
    };
    
    template<typename T> Comparator<T> Comparator<T>::asc_(Comparator<T>::ASC);
    template<typename T> Comparator<T> Comparator<T>::desc_(Comparator<T>::DESC);
    

    Фактически, всего требуется по 2 экземпляра данного класса для каждого типа элемента T, поэтому эти 2 экземпляра создаются статически, а интерфейс класса Comparator таков, что никаких экземпляров кроме этих двух получить нельзя (не считая копирования).

    Итак, инициализируем sets следующим образом:
    typedef std::multiset<int, Comparator<int> > Set;
    Set sets[N] = { Set(Comparator<int>::Asc()), Set(Comparator<int>::Desc()) };
    

    Таким образом полученное работоспособное решение свелось к правильной инициализации ассоциативных контейнеров.

    Интересно, что поскольку экземпляр компаратора хранится в контейнере по значению, а не по указателю или ссылке, решение принципиально является не полиморфным. Однако можно предложить и решение схожее с динамическим полиморфизмом с той точки зрения, что основано на косвенном вызове функций. Рассмотрим функции:
    template<typename T> bool compareLess(const T& l, const T& r) {
    	return l < r;
    }
    
    template<typename T> bool compareGreater(const T& l, const T& r) {
    	return l > r;
    }
    

    Они имеют одинаковую сигнатуру, следовательно, одинаковый тип, который может быть типом компаратора в ассоциативном контейнере. Решение сводится к следующей инициализации массива:
    typedef bool (*compareFn)(int const&, int const&);
    typedef std::multiset<int, compareFn> Set2;
    Set2 sets2[N] = { Set2(compareLess<int>), Set2(compareGreater<int>) };
    

    UPD: Благодаря идее Unrul использовать std::function к двум вариантам добавились еще 4:
    Вариант 3: лябда-функции
    Вариант 4: std::less, обернутая в std::function, для обратной сортировки параметры std::less переставляются при помощи std::bind
    Вариант 5: std::less и std::greater обернутые в std::function
    Вариант 6: объединяет варианты 2 и 3: std::function приведенная к указателю на функцию

    Привожу полный пример, демонстрирующий работоспособность всех решений (обработка мультимножеств сведена к выводу их элементов, что демонстрирует правильный порядок сортировки):
    #include <iostream>
    #include <set>
    #include <functional>
    
    using namespace std::placeholders;
    
    template <typename T> class Comparator {
    public:
    	bool operator()(const T& l, const T& r) const {
    		return ASC == order_ ? (l < r) : (l > r);
    	}
    	static Comparator const& Asc() {
    		return asc_;
    	}
    	static Comparator const& Desc() {
    		return desc_;
    	}
    private:
    	enum Order_ {ASC, DESC} const order_;
    	Comparator(Order_ order) : order_(order) {};
    	static Comparator asc_;
    	static Comparator desc_;
    };
    
    template<typename T> Comparator<T> Comparator<T>::asc_(Comparator<T>::ASC);
    template<typename T> Comparator<T> Comparator<T>::desc_(Comparator<T>::DESC);
    
    template<typename T> bool compareLess(const T& l, const T& r) {
    	return l < r;
    }
    
    template<typename T> bool compareGreater(const T& l, const T& r) {
    	return l > r;
    }
    
    int main() {
    	static size_t const N = 2;
    	int unsorted[] = {4, 6, 3, 4, 7, 8, 1, 2};
    	//1
    	{
    		typedef std::multiset<int, Comparator<int> > Set;
    		Set sets[N] = { Set(Comparator<int>::Asc()), Set(Comparator<int>::Desc()) };
    		for (size_t i = 0; i < N; ++i) {
    			sets[i].insert(std::begin(unsorted), std::end(unsorted));
    		}
    		for (size_t i = 0; i < N; ++i) {
    			for (auto const& it : sets[i]) {
    				std::cout << it << " ";
    			}
    			std::cout << "\n";
    		}
    	}
    	//2
    	{
    		typedef bool (*compareFn)(int const&, int const&);
    		typedef std::multiset<int, compareFn> Set2;
    		Set2 sets2[N] = { Set2(compareLess<int>), Set2(compareGreater<int>) };
    		for (size_t i = 0; i < N; ++i) {
    			sets2[i].insert(std::begin(unsorted), std::end(unsorted));
    		}
    		for (size_t i = 0; i < N; ++i) {
    			for (auto const& it : sets2[i]) {
    				std::cout << it << " ";
    			}
    			std::cout << "\n";
    		}
    	}
    	//3
    	{
    		typedef std::multiset<int, std::function<bool(int,int)>> Set3;
    		Set3 sets3[N] = {Set3([](int a, int b){ return a < b; }), Set3([](int a, int b){ return a > b; })};
    		for (size_t i = 0; i < N; ++i) {
    			sets3[i].insert(std::begin(unsorted), std::end(unsorted));
    		}
    		for (size_t i = 0; i < N; ++i) {
    			for (auto const& it : sets3[i]) {
    				std::cout << it << " ";
    			}
    			std::cout << "\n";
    		}
    	}
    	//4
    	{
    		typedef std::multiset<int, std::function<bool(int,int)>> Set4;
    		Set4 sets4[N] = {Set4(std::less<int>()), Set4(std::bind(std::less<int>(), _2, _1))};
    		for (size_t i = 0; i < N; ++i) {
    			sets4[i].insert(std::begin(unsorted), std::end(unsorted));
    		}
    		for (size_t i = 0; i < N; ++i) {
    			for (auto const& it : sets4[i]) {
    				std::cout << it << " ";
    			}
    			std::cout << "\n";
    		}
    	}
    	//5
    	{
    		typedef std::multiset<int, std::function<bool(int,int)>> Set5;
    		Set5 sets5[N] = {Set5(std::less<int>()), Set5(std::greater<int>())};
    		for (size_t i = 0; i < N; ++i) {
    			sets5[i].insert(std::begin(unsorted), std::end(unsorted));
    		}
    		for (size_t i = 0; i < N; ++i) {
    			for (auto const& it : sets5[i]) {
    				std::cout << it << " ";
    			}
    			std::cout << "\n";
    		}
    	}
    	//6: объединяет варианты 2 и 3
    	{
    		typedef bool (*compareFn)(int const&, int const&);
    		typedef std::multiset<int, compareFn> Set6;
    		Set6 sets6[N] = {Set6([](int const& a, int const& b){ return a < b; }),
    				Set6([](int const& a, int const& b){ return a > b; })};
    		for (size_t i = 0; i < N; ++i) {
    			sets6[i].insert(std::begin(unsorted), std::end(unsorted));
    		}
    		for (size_t i = 0; i < N; ++i) {
    			for (auto const& it : sets6[i]) {
    				std::cout << it << " ";
    			}
    			std::cout << "\n";
    		}
    	}
    	return 0;
    }
    
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 14

      +5
      Я, наверное, не совсем понял постановку задачи.
      А не проще ли было вынести «длинную обработку it» в отдельную функцию?
        0
        Объединение циклов — в самой постановке задачи. Не могу целиком привести условие, хотя бы из-за того, что слишком долго. Семантически там нужно сделать одно и то же действие N=2 раза в разном порядке. К тому же если N не 2 а 1000, то просто функция уже не прокатит
          +7
          Однако… А ведь можно уложиться только в одни стандартные возможности библиотеки.

              typedef std::multiset<int, std::function<bool(int,int)>> Set;
              Set set0([](int a, int b){ return a < b; });
              Set set1([](int a, int b){ return a > b; });
              Set sets[] = {set0, set1};
          
              for (size_t i = 0; i < 2; ++i) {
                  for (auto const& val: sets[i]) {
          
                  }       
              }
          
            +3
            Или даже так, если хочется, чтобы было короче :)

                Set set0(bind(less<int>(), _1, _2));
                Set set1(bind(less<int>(), _2, _1));
            
              +2
              bind(less(), _1, _2) — тавталогия?

              Еще короче:
                  Set set0(less<int>());
                  Set set1(greater<int>());
              


              А вообще очень хорошая идея с function, я не достаточно знаю с++11, чтобы самому догадаться, спасибо
                0
                >> bind(less(), _1, _2) — тавталогия?

                Иначе не будет компилироваться (по крайней мере в 12 студии). Вообще, это всё фичи из boost и могут использоваться без с++11.
                  0
                  В gcc-4.7 такое компилируется и работает:
                  		typedef std::multiset<int, std::function<bool(int,int)>> Set4;
                  		Set4 sets4[N] = {Set4(std::less<int>()), Set4(std::bind(std::less<int>(), _2, _1))};
                  

                  Не могу понять, почему в принципе в вс12 может не компилироваться такой код: bind(less(), _1, _2) подходит под тип function<bool(int,int)>> а less() — нет?
                    0
                    Может быть из-за того, что less::operator()(int const&, int const&) определен с параметрами int const&, а не int, и вариант:
                            typedef std::multiset<int, std::function<bool(int const&, int const&)>> Set4;
                            Set4 sets4[N] = {Set4(std::less<int>()), Set4(std::bind(std::less<int>(), _2, _1))};
                    

                    будет работать и в вс12?
            0
            В пример программы внесны изменения, в частности, добавлены варианты использования std::function — спасибо Unrul
              0
              Нужно заметить, что мультисеты, параметризованные «по возрастанию» и «по убыванию» — это, фактически, мультисеты разных типов.
              Пусть с точки зрения компилятора, они однотипны, так же, как однотипны объекты, доступные через однотипные указатели.
              Это такой ad hoc полиморфизм.

              Поэтому при работе с ними нужна определённая гигиена.
              Скажем,
              my_multiset_compiletime<ASCENDING> ac;
              my_multiset_compiletime<DESCENDING> dc;
              my_multiset_runtime ar(ASCENDING);
              my_multiset_runtime dr(DESCENDING);
              
              ac.insert(1); ac.insert(3); ac.insert(2); // {1,2,3}
              
              // поскольку между разнотипными мультисетами нет оператора присваивания, - явно копируем данные
              // ну или, если мы делаем свой класс мультисета, то пишем шаблонный оператор присваивания...
              
              ar.insert(ac.begin(), ac.end()); // {1,2,3}
              dc.insert(ac.begin(), ac.end()); // {3,2,1}
              
              // а вот между отнотипными - оператор присваивания есть из коробки
              
              dr = ar; // {1,2,3}, заодно скопировали настройки компаратора!!!
              

                +1
                Вообще, начали с того, что хотели припахать foreach для перебора в двух разных направлениях, а вместо этого стали делать разные компараторы.
                Не проще ли было взять адаптер диапазона?
                #include <boost/range/adaptor/reversed.hpp>
                
                .....
                
                std::multiset<int> ms;
                for(auto i : ms) { ..... }
                for(auto i : boost::adaptors::reverse(ms)) { ..... }
                

                  0
                  важнее не перебрать сеты в разных направлениях, а объединить циклы
                  0
                  Зачем городить огород с компараторами, если достаточно лямбды и итераторов?

                  #include <iostream>
                  #include <set>
                  #include <algorithm>
                  
                  using namespace std;
                  
                  int main()
                  {
                      multiset<int> set0 = { 0, 1, 2 };
                      multiset<int> set1 = { 3, 4, 5 };
                  
                      auto& process = [&](int n) {
                          cout << n << ' ';
                      };
                      for_each(set0.begin(), set0.end(), process);
                      for_each(set1.rbegin(), set1.rend(), process);
                  
                      return 0;
                  }
                  

                    0
                    опять же, самым главным является объединение циклов, а не свертки тела цикла в функцию

                  Only users with full accounts can post comments. Log in, please.