Главная
Блог разработчиков phpBB
 
+ 17 предустановленных модов
+ SEO-оптимизация форума
+ авторизация через соц. сети
+ защита от спама

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

Anna | 24.06.2014 | нет комментариев

Рассмотрим код:

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
}

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

Задача — объединить эти два цикла примерно дальнейшим образом:

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 таков, что никаких экземпляров помимо этих 2-х получить невозможно (не считая копирования).

Выходит, инициализируем 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;
}

 

Источник: programmingmaster.ru

 

Оставить комментарий
Форум phpBB, русская поддержка форума phpBB
Рейтинг@Mail.ru 2008 - 2017 © BB3x.ru - русская поддержка форума phpBB