Unification of associative STL-containers by a template parameter - comparator
Consider the code:
The processing in the cycle bodies is the same, in other words, the elements of two multisets are required to be processed in the same way: the first in the direct order, the second in the reverse.
The task is to combine these two cycles approximately as follows:
It is clear that since the set1 elements are iterated in the reverse order for the processing cycle and the forward in sets [1], in order to preserve the processing order, the sets [1] need to store the elements in the reverse order with respect to set1. The STL associative containers have a generic parameter — a comparator, which by default has a value of std :: less. So in a first approximation, in order to make the code work, you need to initialize sets approximately as follows:
The classes std :: multiset <int, std :: less> and std :: multiset <int, std :: greater> are different and do not have a common ancestor, therefore they cannot be stored in the same array and the above code simply cannot be compiled. (By the way, the iterators std :: multiset :: const_iterator and std :: multiset :: const_reverse_iterator are also different classes without a common ancestor, so an array of iterators instead of an array of containers will also not solve the problem). The task is reduced to the unification of containers in order to store them in a common array.
In associative STL containers, a comparator is a parameter not only of the type, but also of each instance of the container. For trivial cases like std :: less by default, the comparator class does not contain any data and, therefore, all containers perform the same comparison operation, in particular, they store elements in the same order. For a more complex case, you can store data in the comparator, for example, about the sort order. In this case, different instances of containers of the same class will sort the elements differently depending on the value of the field in the comparator instance, which in turn is the field of the container instance. So, the class of the comparator allows you to compare in different ways:
In fact, only 2 instances of this class are required for each type of element T, therefore these 2 instances are created statically, and the interface of the Comparator class is such that no instances except these two can be obtained (not counting copying).
So, we initialize sets as follows:
Thus, the resulting workable solution was reduced to the correct initialization of associative containers.
')
Interestingly, since the comparator instance is stored in the container by value, not by pointer or reference, the solution is fundamentally non-polymorphic. However, you can offer a solution similar to dynamic polymorphism from the point of view that is based on an indirect call of functions. Consider the functions:
They have the same signature, therefore, the same type, which may be the type of comparator in an associative container. The solution comes down to the following array initialization:
UPD: Thanks to the Unrul idea of using std :: function, 4 more were added to the two options:
Option 3: Lyabda functions
Option 4: std :: less, wrapped in std :: function, for reverse sorting, the parameters std :: less are rearranged with std :: bind
Option 5: std :: less and std :: greater wrapped in std :: function
Option 6: combines options 2 and 3: std :: function reduced to a function pointer
I give a complete example that demonstrates the performance of all solutions (processing of multisets is reduced to the conclusion of their elements, which demonstrates the correct sorting order):
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 } The processing in the cycle bodies is the same, in other words, the elements of two multisets are required to be processed in the same way: the first in the direct order, the second in the reverse.
The task is to combine these two cycles approximately as follows:
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 } } It is clear that since the set1 elements are iterated in the reverse order for the processing cycle and the forward in sets [1], in order to preserve the processing order, the sets [1] need to store the elements in the reverse order with respect to set1. The STL associative containers have a generic parameter — a comparator, which by default has a value of std :: less. So in a first approximation, in order to make the code work, you need to initialize sets approximately as follows:
std::multiset<int> sets[N] = {std::multiset<int, std::less>(), std::multiset<int, std::greater>()}; The classes std :: multiset <int, std :: less> and std :: multiset <int, std :: greater> are different and do not have a common ancestor, therefore they cannot be stored in the same array and the above code simply cannot be compiled. (By the way, the iterators std :: multiset :: const_iterator and std :: multiset :: const_reverse_iterator are also different classes without a common ancestor, so an array of iterators instead of an array of containers will also not solve the problem). The task is reduced to the unification of containers in order to store them in a common array.
In associative STL containers, a comparator is a parameter not only of the type, but also of each instance of the container. For trivial cases like std :: less by default, the comparator class does not contain any data and, therefore, all containers perform the same comparison operation, in particular, they store elements in the same order. For a more complex case, you can store data in the comparator, for example, about the sort order. In this case, different instances of containers of the same class will sort the elements differently depending on the value of the field in the comparator instance, which in turn is the field of the container instance. So, the class of the comparator allows you to compare in different ways:
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); In fact, only 2 instances of this class are required for each type of element T, therefore these 2 instances are created statically, and the interface of the Comparator class is such that no instances except these two can be obtained (not counting copying).
So, we initialize sets as follows:
typedef std::multiset<int, Comparator<int> > Set; Set sets[N] = { Set(Comparator<int>::Asc()), Set(Comparator<int>::Desc()) }; Thus, the resulting workable solution was reduced to the correct initialization of associative containers.
')
Interestingly, since the comparator instance is stored in the container by value, not by pointer or reference, the solution is fundamentally non-polymorphic. However, you can offer a solution similar to dynamic polymorphism from the point of view that is based on an indirect call of functions. Consider the functions:
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; } They have the same signature, therefore, the same type, which may be the type of comparator in an associative container. The solution comes down to the following array initialization:
typedef bool (*compareFn)(int const&, int const&); typedef std::multiset<int, compareFn> Set2; Set2 sets2[N] = { Set2(compareLess<int>), Set2(compareGreater<int>) }; UPD: Thanks to the Unrul idea of using std :: function, 4 more were added to the two options:
Option 3: Lyabda functions
Option 4: std :: less, wrapped in std :: function, for reverse sorting, the parameters std :: less are rearranged with std :: bind
Option 5: std :: less and std :: greater wrapped in std :: function
Option 6: combines options 2 and 3: std :: function reduced to a function pointer
I give a complete example that demonstrates the performance of all solutions (processing of multisets is reduced to the conclusion of their elements, which demonstrates the correct sorting order):
#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; } Source: https://habr.com/ru/post/210746/
All Articles