Унификация ассоциативных 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>) }; 

Привожу полный пример, демонстрирующий работоспособность обоих решений (обработка мультимножеств сведена к выводу их элементов, что демонстрирует правильный порядок сортировки):

#include <iostream> #include <set>  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() { 	typedef std::multiset<int, Comparator<int> > Set; 	static size_t const N = 2; 	Set sets[N] = { Set(Comparator<int>::Asc()), Set(Comparator<int>::Desc()) }; 	int unsorted[] = {4, 6, 3, 4, 7, 8, 1, 2}; 	for (size_t i = 0; i < N; ++i) { 		sets[i].insert(unsorted, unsorted + (sizeof (unsorted) / sizeof (*unsorted))); 	} 	for (size_t i = 0; i < N; ++i) { 		for (auto const& it : sets[i]) { 			std::cout << it << " "; 		} 		std::cout << "\n"; 	} 	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(unsorted, unsorted + (sizeof (unsorted) / sizeof (*unsorted))); 	} 	for (size_t i = 0; i < N; ++i) { 		for (auto const& it : sets[i]) { 			std::cout << it << " "; 		} 		std::cout << "\n"; 	} 	return 0; }