Mutable sorters (original) (raw)

cpp-sort currently gives the middle finger to mutable sorters, which might not be the right reaction to have. It never really mattered because every sorter in the library is immutable. However, we might want to have mutable sorters at some point, for example sorters that can reuse memory instead of allocating new memory whenever they're called. A few design points to take into account:

• Sorter adapters should be able to take sorter instances and use them instead of generating new instances on-the-fly
• Mutable sorters won't convert to function pointers, and sorter_facade wil have to handle that
• A sorter adapter should be made immutable when the adapted sorter is immutable: an std::is_empty check should be enough to guarantee immutability
• If it is not enough, introduce an utility::is_immutable trait which falls back to std::is_empty and can be specialized by users

Mutable sorters could allow to pass additional runtime parameters to existing sorter. For example counting_sorter needs one less pass over the collection if the min and max values are known ahead of the sort. They could be passed as follows:

counting_sorter(min, max)(collection);

Such a sorter wouldn't be convertible to a function pointer, but it allows to pass additional runtime parameters to the sorter without having to change the generic sorting interface. Basically: constructor parameters would serve to pass sorter-specific parameters while function-call parameters would serve to pass the generic collection/comparison/projection parameters. Hence mutable sorters are useful.

Another example: one could pass a runtime buffer to merge-sort so that several calls to the algorithm are able to reuse the same memory instead of allocating its own.

Usual TODO list:

• Actually store sorters in adapters
• Make sure the instance of a sorter called by a given adapter is always the same
• Make sorter_facade handle mutable sorters
• Make adapters handle mutable sorters when it makes sense
• Handle hybrid_adapter properly
• Add tests
• Update documentation
• Check that examples still work