Converting between the containers with transparent and non-transparent comparators

Question

I have a class A that has a member std::map<std::string, Data, std::less<>> where Data is another class from a library whose source code I'd rather leave intact. I have opted in to use the transparent comparator by using std::less<> as the template argument since I want to be able to benefit from std::string_view.

The library can only take a std::map<std::string, Data>&. So I need to somehow convert between std::map<std::string, Data, std::less<>> and std::map<std::string, Data>. However, these two types are unrelated from the C++ language point of view, even though the internal structure of rb tree would be exactly the same (assuming the implementation uses rb tree to implement std::map, but that's just implementation detail), so directly casting will fail.

So is the following snippet the best way to achieve the goal or is there a better way to perform such a conversion?

#include <map>
#include <string>
#include <string_view>
#include <optional>

// Inside the library
namespace Library{
    class Data {
        //...
    };
    typedef std::map<std::string, Data> DataMap_t;
    void processMap(DataMap_t& map){
        //Mutates Data inside the map based on map key and other info
    }
}

// In the application code
class A{
    public:
        typedef std::map<std::string, Library::Data, std::less<>> TransparentDataMap_t;
        void processMap(){
            Library::DataMap_t dataMap;
            // This doesn't work, of course
            //dataMap = static_cast<Library::DataMap_t>(transparentDataMap);
            dataMap.merge(transparentDataMap);
            Library::processMap(dataMap);
            transparentDataMap.merge(dataMap);
        }
        std::optional<Library::Data> dataAt(std::string_view sv){
            const auto iter = transparentDataMap.find(sv);
            if(iter == transparentDataMap.end()){
                return {};
            }
            return iter->second;
        }
        //Other member functions ...
    private:
        TransparentDataMap_t transparentDataMap;
        //Other data members ...
};

Answer 1

For whatever reason, this library requires a reference to a map that uses a std::less<std::string> comparator, but you have a map that uses a std::less<void> comparator. As you say, these specialisations of std::map are two unrelated types, so there is no well-defined cast between them. You must create a separate object and copy or move the contents over, as in your snippet.

However, you can improve the time complexity. std::map::merge does not assume any relationship between the two comparators, so its use in your snippet is only guaranteed by the standard to have a time complexity of O(n log n). By writing your own merge that takes advantage of the identical ordering, you can reduce this to O(n):

template <typename K, typename V, typename Allocator, typename C1, typename C2>
void mergeSameOrder(std::map<K, V, C1, Allocator> &dest, std::map<K, V, C2, Allocator> &source) {
    while (!source.empty()) {
        dest.insert(dest.cend(), source.extract(source.cbegin()));
    }
}