Pull to refresh

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

Reading time6 min
Views9.4K
Рассмотрим код:
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;
}
Tags:
Hubs:
Total votes 19: ↑13 and ↓6+7
Comments14

Articles