Головоломка по ассоциативным контейнерам STL или Как решить одну задачу восемью очень разными способами

Введение

В данной статье я хочу рассказать о своих «приключениях» при решении задачи по STL, возникшей в ходе работы над небольшим проектом (C++11, Visual Studio 2015).

На первый взгляд, задача выглядела весьма просто. Но при ближайшем рассмотрении:
— в открытых источниках готового решения не нашлось;
— стандартные ООП-подходы на ней «забуксовали»;
— оказалось, что даже для опытного разработчика задача может представлять сложность.

Я приведу несколько вариантов решения. Часть из них я отбросил до реализации, но некоторые были реально написаны. Из одних примеров можно извлечь пользу только типа «смотри и никогда так не делай», другие же вполне могут найти применение на практике.

Постановка задачи

Итак, есть структура-хранилище, одним из полей которой является ассоциативный контейнер std::map из STL:

#include <map>

struct Storage
{
	// ... something

	using Data = std::map<int, double>;
	Data data;

	// ... something
};

Затем создаются несколько экземпляров хранилища, в которые набиваются данные:

void Fill(Storage &storage)
{
	int i;
		for ( i = 0; i < 5; ++i )
		{
			storage.data.insert( {i, i} );
		}
}


int main()
{
	Storage data1, data2;

	Fill(data1);
	Fill(data2);

	return 0;
}

Далее (т.к. разработка структур данных шла параллельно с написанием кода, использующего их) выяснилось, что на самом деле эти хранилища должны быть не совсем одинаковыми: в одних экземплярах требуется сортировка в возрастающем порядке, в других — в убывающем. Т.е. наполнение данными можно (и даже нужно) производить единообразно, но вот использование (извлечение) данных сортированной по умолчанию map приходится писать по-разному (для одних экземпляров — прямым итератором, для других — обратным).

Проблема при этом заключалась в том, что использование данных планировалось во многих алгоритмах, а ошибочный обход контейнера в неправильном направлении мог привести к серьезным последствиям.

Создание контейнеров с множеством таких хранилищ (или указателей на такие хранилища) не планировалось, что конечно упрощало задачу, но если бы удалось решить ее для общего случая — это было бы вообще отлично.

Вариант 1 — лобовой

Дополняем структуру полем разновидности, а ответственность за выбор корректного варианта возлагаем на пользователя структуры. Ну и немного подслащаем пилюлю — обеспечиваем невозможность изменения разновидности после создания экземпляра:

#include <map>
#include <iostream>


struct Storage
{
	// ... something

	using Data = std::map<int, double>;
	Data data;

	enum Type { forward, reverse };
	const Type type;

	Storage() = delete;
	Storage(Type initType) : type(initType) {};

	// ... something
};


void Fill(Storage &storage)
{
	int i;
		for ( i = 0; i < 5; ++i )
		{
			storage.data.insert( {i, i} );
		}
}


std::ostream& operator<<(std::ostream &stream, const Storage &storage)
{
		if ( storage.type == Storage::forward )
				// Перебор в прямом порядке
				for (const auto &iter : storage.data)
					stream << std::endl << iter.first << " " << iter.second;
		else
				// Перебор в обратном порядке
				for (auto iter = storage.data.crbegin(); iter != storage.data.crend(); ++iter)
					stream << std::endl << iter->first << " " << iter->second;

	return stream;
}


int main()
{
	Storage data1(Storage::forward), data2(Storage::reverse);

	Fill(data1);
	Fill(data2);

	std::cout << data1 << std::endl << data2 << std::endl;

	return 0;
}

Назвать это решением язык не поворачивается — просто перенос ответственности, почти не страхующий от ошибок использования.

Вариант 2 — шаблоновый

Ассоциативные контейнеры STL (map в том числе) позволяют указывать класс функтора сравнения. Такая возможность требуется довольно редко, поэтому данный параметр имеет значение по умолчанию std::less. В литературе имеются примеры использования ассоциативных контейнеров с нестандартными функторами (как и примеры написания пользовательских функторов), а в заголовочном файле уже определен подходящий нам функтор std::greater — вот просто бери и пользуйся готовым решением.

Итак, объявляем Storage как шаблон, и определяем для него 2 специализации конкретными значениями. На первый взгляд — красивое сompile-time решение: быстро исполняется, выявляет ошибки на этапе компиляции:

#include <map>
#include <iostream>
#include <functional>


enum Type { ascending, descending };


struct StorageAncestor
{
	// ... something
};


template<Type T> struct Storage : StorageAncestor
{
};


template<> struct Storage<ascending>
{
	using Data = std::map<int, double, std::less<int>>;
	Data data;
};


template<> struct Storage<descending>
{
	using Data = std::map<int, double, std::greater<int>>;
	Data data;
};


template<Type T> void Fill(Storage<T> &storage)
{
	int i;
		for ( i = 0; i < 5; ++i )
		{
			storage.data.insert( {i, i} );
		}
}


template<Type T> std::ostream& operator<<(std::ostream &stream, const Storage<T> &storage)
{
		// Перебор в прямом порядке
		for (const auto &iter : storage.data)
			stream << std::endl << iter.first << " " << iter.second;

	return stream;
}


int main()
{
	Storage<ascending> data1;
	Storage<descending> data2;

	Fill(data1);
	Fill(data2);

	std::cout << data1 << std::endl << data2 << std::endl;

	return 0;
}

Однако опытный глаз заметит в приведенном примере важный нюанс: весь код, осуществляющий наполнение и использование структуры, пришлось переработать в форму шаблона. В данном примере это не вызвало затруднений, но в реальном проекте код, конечно же, был намного сложнее — функций и классов, осуществляющих наполнение данными, было много, и некоторые из них уже были шаблонами с несколькими параметрами.

Кроме того:
— фактически не было выполнено требование сохранения единообразного наполнения данными (код для наполнения был к тому моменту готов, в отличие от кода по использованию данных) — просто при должном усердии часть работы можно было бы возложить на компилятор;
— компилятор генерирует отдельный код для каждой требуемой специализации, и в данном случае речь могла идти о существенном увеличении (вплоть до удвоения) объёма исполняемого файла.

В результате этот вариант был признан реализуемым, но слишком сложным для кодирования.

Вариант 3 — обманный

Идея заключается в следующем: оставить std::map в покое (т.е. в обоих случаях использовать функтор сравнения по умолчанию std::less, вызывающий operator<), а «полечить» значение, использующееся в качестве ключа.

#include <map>
#include <iostream>


enum Type { ascending, descending };


template<typename T> class FraudulentValue
{
	public:
		FraudulentValue(const T &t, Type initType) : m_value(t), m_type(initType) {};
		bool operator< (const FraudulentValue<T> &comp) const
		{
			return (m_type == ascending) ? (m_value < comp.m_value) : (m_value > comp.m_value);
		};
		operator T() const {return m_value;};
	protected:
		T m_value;
		Type m_type;
		FraudulentValue() = delete;
};


struct Storage
{
	// ... something

	using Data = std::map<FraudulentValue<int>, double>;
	Data data;

	const Type type;

	Storage() = delete;
	Storage(Type initType) : type(initType) {};

	// ... something
};


void Fill(Storage &storage)
{
	int i;
		for ( i = 0; i < 5; ++i )
		{
			storage.data.insert( {FraudulentValue<int>(i, storage.type), i} );
		}
}


std::ostream& operator<<(std::ostream &stream, const Storage &storage)
{
		// Перебор в прямом порядке
		for (const auto &iter : storage.data)
			stream << std::endl << iter.first << " " << iter.second;

	return stream;
}


int main()
{
	Storage data1(ascending), data2(descending);

	Fill(data1);
	Fill(data2);

	std::cout << data1 << std::endl << data2 << std::endl;

	return 0;
}

Понятно, что данный вариант категорически не годится для production, т.к.:
— operator< в одних случаях выполняет сравнение "<", а в других ">" — сногсшибательно неожиданное поведение, ничего не скажешь;
— нет механизма, предотвращающего добавление в map значения с неправильно настроенным ключом, что ожидаемо приведет к порче контейнера.

Вариант 4 — инкапсуляционный

«Инкапсуляция» — размещение в одном классе (или структуре, как в данном случае) и данных, и алгоритмов. Что ж, если затруднения вызваны различиями кода обхода — значит, этот код надо разместить там же, где находится и перебираемый контейнер, и флаг направления.

#include <map>
#include <iostream>
#include <functional>


struct Storage
{
	// ... something

	using Data = std::map<int, double>;
	Data data;

	enum Type { forward, reverse };
	const Type type;

	Storage() = delete;
	Storage(Type initType) : type(initType) {};

	using const_functor = std::function<void(const Data::value_type&)> const;

	void for_each(const_functor &functor) const
	{
			if ( type == Storage::forward )
					// Перебор в прямом порядке
					for (auto &iter : data)
						functor(iter);
			else
					// Перебор в обратном порядке
					for (auto iter = data.crbegin(); iter != data.crend(); ++iter)
						functor(*iter);
	};

	// ... something
};


void Fill(Storage &storage)
{
	int i;
		for ( i = 0; i < 5; ++i )
		{
			storage.data.insert( {i, i} );
		}
}


std::ostream& operator<<(std::ostream &stream, const Storage &storage)
{
	storage.for_each([&](const Storage::Data::value_type &value)
		{
			stream << std::endl << value.first << " " << value.second;
		}
	);

	return stream;
}


int main()
{
	Storage data1(Storage::forward), data2(Storage::reverse);

	Fill(data1);
	Fill(data2);

	std::cout << data1 << std::endl << data2 << std::endl;

	return 0;
}

Чтобы данное решение стало пригодным для production, остается всего-навсего:
— написать семейство алгоритмов перебора — в прямом и в обратном направлении, для conts и не-const функторов;
— скрыть data в private, чтобы исключить возможность использования обычного (в данном случае нежелательного) механизма перебора;
— обеспечить полноценный интерфейс к спрятанному контейнеру, для чего написать обертки для трех-четырех десятков функций и повторить 15 typedef'ов.

Вариант 5 — наследовательный, он же — нереализуемый

Идея данного варианта следующая: унаследоваться от std::map, в результате чего получить доступ к каким-либо protected-механизмам map.
Однако данный вариант оказался нереализуемым по следующим причинам:
— все потенциально полезные механизмы оказались объявлены как private, а не protected (возможно, Microsoft-specific);
— даже если бы в protected нашлось что-нибудь подходящее — вариант полностью зависел бы от конкретной реализации STL;
— наследование от STL-контейнера вообще является очень плохой идеей, т.к. STL-контейнеры не имеют виртуального деструктора, что может привести к утечке памяти.
Однако исследование внутреннего устройства std::map натолкнуло меня на следующий вариант.

Вариант 6 — специфичный

При первоначальном анализе задачи казалось, что важен только класс функтора сравнения (ведь мы указываем класс в качестве параметра шаблона std::map, а как именно контейнер распоряжается этим классом — скрыто где-то в недрах реализации). Однако при изучении исходных кодов STL оказалось, что каждый экземпляр std::map создает и хранит экземпляр функтора сравнения. Таким образом, в основе данной идеи лежит настройка экземпляра функтора сравнения в соответствии с требуемым направлением сортировки.
В Microsoft-реализации STL у std::map присутствует недокументированный нестандартный метод _Getcomp(), одна из версий которого предоставляет доступ по ссылке к экземпляру функтора сравнения, позволяя осуществить изменение его внутреннего состояния (настройку) в соответствии с нашими нуждами.

#include <map>
#include <iostream>


enum SortingType { ascending, descending };
enum CompareType { none, less, greater };


template<typename T> class AdjustableCompare
{
	public:
		AdjustableCompare() : m_type(none) {};
		bool operator()(const T &_Left, const T &_Right)
		{
				if ( m_type == less )
					return (_Left < _Right);
				if ( m_type == greater )
					return (_Left > _Right);
			throw std::runtime_error("AdjustableCompare was not initialized");
		};

		void setTypeOnce(CompareType type)
		{
				if ( m_type != none )
					throw std::runtime_error("AdjustableCompare double set");
			m_type = type;
		};
	private:
		CompareType m_type;
};



struct Storage
{
	// ... something

	using Data = std::map<int, double, AdjustableCompare<int>>;
	Data data;

	Storage() = delete;
	Storage(SortingType initType)
	{
		data._Getcomp().setTypeOnce( (initType == ascending) ? less : greater );
	};

	// ... something
};


void Fill(Storage &storage)
{
	int i;
		for ( i = 0; i < 5; ++i )
		{
			storage.data.insert( {i, i} );
		}
}


std::ostream& operator<<(std::ostream &stream, const Storage &storage)
{
		// Перебор в прямом порядке
		for (const auto &iter : storage.data)
			stream << std::endl << iter.first << " " << iter.second;

	return stream;
}


int main()
{
	Storage data1(ascending), data2(descending);

	Fill(data1);
	Fill(data2);

	std::cout << data1 << std::endl << data2 << std::endl;

	return 0;
}

Такой вариант решения:
— в отличие от рассмотренных до сих пор вариантов, осуществляет именно настройку экземпляра контейнера;
— контейнеры с разными направлениями сортировки имеют одинаковый тип, что позволяет единообразно осуществлять как наполнение контейнера, так и извлечение данных, а также создавать контейнеры таких контейнеров (или указателей на них);
— требует наличия у класса функтора сравнения конструктора по умолчанию (из-за чего CompareType имеет три возможных значения вместо двух, а также расширяется пространство некорректного применения функтора);
— является Microsoft-specific;
— основан на вмешательстве во внутренние механизмы map.

Последних двух пунктов достаточно, чтобы не рекомендовать его к применению.

Вариант 7 — трюковой, или троянский

В std::map присутствует также стандартная функция key_comp(), возвращающая копию экземпляра функтора сравнения. К сожалению, копия функтора не позволяет изменить внутреннее состояние экземпляра класса, хранящегося в недрах std::map, и не поможет в решении нашей задачи.

Согласны?

Ну что же, смотрите код:

#include <map>
#include <iostream>
#include <memory>


enum SortingType { ascending, descending };
enum CompareType { none, less, greater };


template<typename T> class TrickyCompare
{
	public:
		TrickyCompare() : m_type(new CompareType(none)) {};
		bool operator()(const T &_Left, const T &_Right)
		{
				if ( *m_type == less )
					return (_Left < _Right);
				if ( *m_type == greater )
					return (_Left > _Right);
			throw std::runtime_error("TrickyCompare was not initialized");
		};

		void setTypeOnce(CompareType type)
		{
				if ( *m_type != none )
					throw std::runtime_error("TrickyCompare double set");
			*m_type = type;
		};
	private:
		std::shared_ptr<CompareType> m_type;
};



struct Storage
{
	// ... something

	using Data = std::map<int, double, TrickyCompare<int>>;
	Data data;

	Storage() = delete;
	Storage(SortingType initType)
	{
		data.key_comp().setTypeOnce( (initType == ascending) ? less : greater );
	};

	// ... something
};


void Fill(Storage &storage)
{
	int i;
		for ( i = 0; i < 5; ++i )
		{
			storage.data.insert( {i, i} );
		}
}


std::ostream& operator<<(std::ostream &stream, const Storage &storage)
{
		// Перебор в прямом порядке
		for (const auto &iter : storage.data)
			stream << std::endl << iter.first << " " << iter.second;

	return stream;
}


int main()
{
	Storage data1(ascending), data2(descending);

	Fill(data1);
	Fill(data2);

	std::cout << data1 << std::endl << data2 << std::endl;

	return 0;
}

Почему трюковой? Да потому, что благодаря свойствам «умного указателя» std::shared_ptr нам удалось изменить внутреннее состояние функтора сравнения (а значит, и самого контейнера std::map), воспользовавшись лишь копией экземпляра, причем сделать это безопасно в смысле утечек памяти. В данном примере отсутствие конструктора копирования и оператора присваивания, «корректно обрабатывающих указатели» — это не ошибка кодирования, а именно то, что нужно.

Почему троянский? Потому, что мы дали std::map что-то внешне очень простое и полезное, но на самом деле скрывающее внутри некий сложный механизм с неожиданным поведением, способный повлиять на работу map. Против такой хитрости оказались бессильны казалось бы надежные способы защиты внутреннего состояния map, предусмотренные разработчиками стандарта C++ (да-да, это опасно для работы ассоциативного контейнера, т.к. изменение режима работы функтора после добавления некоторого количества элементов почти гарантированно приведет к порче контейнера). В нашем функторе предусмотрена защита от изменения режима работы после инициализации. Но любая защита может содержать ошибки.

Данный способ уже очень близок к финальному варианту. Там не менее, я не рекомендую его к применению в production — не потому, что знаю о каких-либо его фатальных недостатках, а только лишь потому, что обнаружил более простой и «прямой» способ.

В то же время, примененный в данном варианте трюк вполне может дать изящное решение какой-нибудь другой практической задачи.

Вариант 8 — финальный

Корректное решение задачи, конечно же, оказалось очень простым и элегантным.
Среди десятка конструкторов std::map нашлись несколько, принимающие в качестве аргумента экземпляр функтора сравнения. Похоже, подобное использование map было дальновидно предусмотрено разработчиками стандарта C++, за что честь им и хвала.

#include <map>
#include <iostream>
#include <memory>


template<typename T> class Compare
{
	public:
		enum Type { less, greater };
		Compare() = delete;
		Compare(Type type) : m_type(type) {};
		bool operator()(const T &_Left, const T &_Right)
		{
				if ( m_type == less )
					return (_Left < _Right);
				else
					return (_Left > _Right);
		};
	private:
		Type m_type;
};


struct Storage
{
	// ... something

	using Data = std::map<int, double, Compare<int>>;
	Data data;

	enum Type { ascending, descending };

	Storage() = delete;
	Storage(Type initType) : data((initType == ascending) ? Compare<int>::less : Compare<int>::greater) {};

	// ... something
};


void Fill(Storage &storage)
{
	int i;
		for ( i = 0; i < 5; ++i )
		{
			storage.data.insert( {i, i} );
		}
}


std::ostream& operator<<(std::ostream &stream, const Storage &storage)
{
		// Перебор в прямом порядке
		for (const auto &iter : storage.data)
			stream << std::endl << iter.first << " " << iter.second;

	return stream;
}


int main()
{
	Storage data1(Storage::ascending), data2(Storage::descending);

	Fill(data1);
	Fill(data2);

	std::cout << data1 << std::endl << data2 << std::endl;

	return 0;
}

Данное решение:
— отлично согласуется как с идеологией STL, так и со стандартом C++;
— полностью выполняет поставленную задачу, в том числе желательный пункт (ничто не мешает созданию и единообразной обработке контейнера таких контейнеров);
— имеет высокий уровень защиты от ошибок использования (в том числе по причине отсутствия конструктора по умолчанию у функтора сравнения).

Вывод

Чем же были обусловлены сложности в решении данной задачи?

Основным фактором явилось то, что факт хранения экземпляра функтора сравнения внутри каждого экземпляра ассоциативного контейнера не является ни очевидным, ни широко известным. На первый взгляд важным кажется лишь класс функтора сравнения, что не полностью соответствует реальному положению вещей.

P.S.: несмотря на наличие побочных эффектов и противопоказаний к применению, все примеры, приведенные в статье, функциональны.

Благодарности

the_1x

Литература

— C. Мейерс — Эффективное использование STL
— Working Draft, Standard for Programming Language C++, N3797. П.п. 23.2.4.2, 23.2.4.12.

Автор: Dubovik_a

Источник