Puzzle on STL associative containers or How to solve one problem in eight very different ways

Introduction

In this article I want to talk about my “adventures” when solving the STL problem that arose during the work on a small project (C ++ 11, Visual Studio 2015).

At first glance, the task looked quite simple. But upon closer inspection:
- there was no ready solution in open sources;
- standard OOP approaches on it “stalled”;
- It turned out that even for an experienced developer, the task may be difficult.

I will give several solutions. I dropped some of them before implementation, but some were actually written. From some examples, one can benefit only from the “see and never do that” type, while others may well be used in practice.

Formulation of the problem

So, there is a storage structure, one of the fields of which is the STL associative container std :: map:
')

#include <map> struct Storage { // ... something using Data = std::map<int, double>; Data data; // ... something }; 

Then several instances of the repository are created into which the data is stuffed:

 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; } 

Then (since the development of data structures went hand in hand with writing the code that uses them), it turned out that in fact these storages should not be exactly the same: in some instances, sorting is required in ascending order, in others - in descending order. Those. data can be filled (and even needed) in a uniform way, but using (extracting) the data sorted by default, the map has to be written differently (for some instances - with a direct iterator, for others - the reverse).

The problem with this was that the use of data was planned in many algorithms, and erroneous walking of the container in the wrong direction could lead to serious consequences.

Creating containers with many such storages (or pointers to such storages) was not planned, which of course simplified the task, but if you could solve it for the general case, it would be excellent.

Option 1 - frontal

We supplement the structure with a field of variety, and the responsibility for choosing the correct version is assigned to the user of the structure. Well, a little sweeten the pill - ensure the impossibility of changing the variety after creating an instance:

 #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; } 

Calling it a solution does not turn the language - just a transfer of responsibility, almost not safe from using errors.

Option 2 - template

Associative containers STL (including map) allow you to specify the class of the comparison functor. This feature is quite rarely required, so this parameter has a default value of std :: less. In the literature there are examples of using associative containers with non-standard functors (as well as examples of writing custom functors), and the header file std :: greater is already defined in the header file — just take it and use the ready-made solution.

So, we declare Storage as a template, and we define for it 2 specializations with specific values. At first glance - a beautiful complex-time solution: it is quickly executed, it reveals errors at the compilation stage:

 #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; } 

However, an experienced eye will notice in the example given an important nuance: all the code that performs filling and using the structure had to be reworked into a template form. In this example, this did not cause any difficulties, but in the real project the code, of course, was much more complicated - there were a lot of functions and classes filling the data, and some of them were already templates with several parameters.

Besides:

- the requirement of preserving uniform data filling was actually not fulfilled (the code for filling was ready by that time, unlike the code for using data) - simply with due diligence some of the work could be assigned to the compiler;
- the compiler generates a separate code for each required specialization, and in this case we could talk about a significant increase (up to a doubling) of the size of the executable file.

As a result, this option was recognized as realizable, but too complex for encoding.

Option 3 - fraudulent

The idea is as follows: leave std :: map alone (that is, in both cases use the default comparison functor std :: less, calling operator <), and “treat” the value used as the key.

 #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; } 

It is clear that this option is categorically not suitable for production, because:

- operator <in some cases performs a comparison "<", and in others ">" - a stunningly unexpected behavior, nothing can be said;
- there is no mechanism to prevent adding values ​​to the map with an incorrectly configured key, which is expected to lead to container damage.

Option 4 - encapsulation

"Encapsulation" - placement in one class (or structure, as in this case) and data, and algorithms. Well, if difficulties are caused by differences in the bypass code, this means that this code should be placed in the same place as the container being relocated and the direction flag.

 #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; } 

To make this solution suitable for production, all that remains is:

- write a family of brute force algorithms - in the forward and backward directions, for const and non-const functors;
- hide data in private to exclude the possibility of using the usual (in this case, undesirable) brute force mechanism;
- provide a full-fledged interface to the hidden container, for which to write wrappers for three or four dozen functions and repeat 15 typedefs.

Option 5 - hereditary, it is - unrealizable

The idea of ​​this option is as follows: inherit from std :: map, as a result of which get access to any protected-map mechanisms.

However, this option was not feasible for the following reasons:

- all potentially useful mechanisms were declared to be private rather than protected (possibly Microsoft-specific);
- even if something was found protected, the option would be completely dependent on the specific implementation of STL;
- Inheritance from an STL container is generally a very bad idea, since STL containers do not have a virtual destructor, which can lead to memory leaks.
However, the study of the internal structure of std :: map prompted me to the next option.

Option 6 - specific

During the initial analysis of the problem, it seemed that only the comparison functor class is important (after all, we specify the class as a parameter of the std :: map template, and how the container controls this class is hidden somewhere in the depths of the implementation). However, when studying the STL source codes, it turned out that each instance of std :: map creates and stores an instance of the comparison functor. Thus, the basis of this idea is to configure an instance of the comparison functor in accordance with the required direction of sorting.
In the Microsoft STL implementation of std :: map, there is an undocumented nonstandard _Getcomp () method, one of the versions of which provides access by reference to an instance of the comparison functor, allowing you to change its internal state (setting) according to our needs.

 #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; } 

This solution:

- in contrast to the options considered so far, it is the setting of the container instance that performs;
- containers with different sorting directions are of the same type, which makes it possible to carry out both filling of the container and data retrieval in a uniform manner, as well as creating containers of such containers (or pointers to them);
- it requires that the default constructor compare class functor (which is why CompareType has three possible values ​​instead of two, and also expands the space for incorrect use of the functor);
- is Microsoft-specific;
- based on interference with the internal mechanisms of the map.

The last two points are enough to not recommend it for use.

Option 7 - trick or Trojan

In the std :: map there is also the standard function key_comp (), which returns a copy of the comparison functor instance . Unfortunately, a copy of the functor does not allow us to change the internal state of an instance of a class stored in the depths of std :: map, and will not help in solving our problem.

Do you agree?

Well, see the code:

 #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; } 

Why trick? Yes, because thanks to the properties of the smart pointer std :: shared_ptr we were able to change the internal state of the comparison functor (and therefore the std :: map container itself) using only a copy of the instance, and it is safe to do so in terms of memory leaks. In this example, the absence of a copy constructor and an assignment statement that “correctly handles pointers” is not an encoding error, but exactly what is needed.

Why trojan? Because we gave std :: map something externally very simple and useful, but actually hiding inside some complicated mechanism with unexpected behavior that could affect the operation of the map. The seemingly reliable ways to protect the internal state of the map provided by the developers of the C ++ standard turned out to be powerless against this trick (yes, it’s dangerous for the associative container to work, because changing the mode of the functor after adding a certain number of elements almost guaranteed to damage the container) . Our functor provides protection against changing the operation mode after initialization. But any protection may contain errors.

This method is already very close to the final version. There, however, I do not recommend it for use in production — not because I know about any of its fatal flaws, but only because I discovered a simpler and more “direct” way.

At the same time, the trick applied in this variant may well give an elegant solution to some other practical problem.

Option 8 - final

The correct solution of the problem, of course, turned out to be very simple and elegant.
Among a dozen constructors, std :: map, there were several that take an instance of a comparison functor as an argument. It seems that such use of the map was foresightly provided by the developers of the C ++ standard, for which honor and praise to them.

 #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) const { 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; } 

This solution:

- perfectly consistent with the ideology of STL, and with the standard C + +;
- fully fulfills the task, including the desired item (nothing prevents the creation and uniform processing of the container of such containers);
- has a high level of protection against usage errors (including due to the lack of a default constructor for the comparison functor).

Conclusion

What caused the difficulty in solving this problem?

The main factor was that the fact of storing an instance of a comparison functor inside each instance of an associative container is neither obvious nor widely known. At first glance, only the comparison functor class seems important, which does not fully correspond to the real state of affairs.

PS: despite the presence of side effects and contraindications for use, all examples cited in the article are functional.

Thanks

the_1x

Literature

- C. Meyers - Effective use of STL
- Working Draft, Standard for Programming Language C ++, N3797. Pp 23.2.4.2, 23.2.4.12.