Avoiding a copy while searching in a std::map with composite keys

user_1043352 0
Viewed 239

Suppose I have a map that maps two strings into a long:

std::map<std::pair<std::string, std::string>, long> sums = 
{
    {{"1", "2"}, 3},
    {{"3", "4"}, 7},
    {{"5", "6"}, 11},
};

If I want to search in a map, it takes a std::pair<std::string, std::string>. If I receive the two strings to search by via different ways, I have to construct std::pair on the fly, which AFAIK copies the strings:

std::string one = "1";
std::string two = "2";
std::pair<std::string, std::string> myPair = std::make_pair(one, two);
std::map<std::pair<std::string, std::string>, long>::const_iterator it = sums.find(myPair);

If the map is searched A LOT, is there a way to not copy the strings to perform the search? There is no need to do a copy, it is required just by semantics of std::map.

EDIT: I am not attached to std::pair as key, it can be anything, even custom struct, as long as it is able to hold elements in the map by-value and search for them without a copy.

stdmap copy c++11
3 Answers

C++17

Since you said you are interested in a C++17 solution too, you can take advantage of std::string_view which does not allocate any memory but just holds the pointer to the actual data and the string length. Therefore, copy operation is lightweight.

The end solution would look like:

#include <iostream>
#include <string_view>
#include <map>

int main() {
    std::map<std::pair<std::string_view, std::string_view>, long> sums = {
        {{"1", "2"}, 3},
        {{"3", "4"}, 7},
        {{"5", "6"}, 11}
    };

    std::pair<std::string_view, std::string_view> myPair = std::make_pair("1", "2");
    auto it = sums.find(myPair);
    std::cout << it->second << std::endl; // output: 3

    return 0;
}

C++11

If you are limited to C++11, then you can use char const* as your std::pair members but then you need to define custom compare function like:

#include <iostream>
#include <cstring>
#include <map>

struct cmp_str {
   bool operator()(std::pair<char const*, char const*> const& a,
                   std::pair<char const*, char const*> const& b) const {
      return std::strcmp(a.first, b.first) < 0;
   }
};

int main() {
    std::map<std::pair<char const*, char const*>, long, cmp_str> sums = {
        {{"1", "2"}, 3},
        {{"3", "4"}, 7},
        {{"5", "6"}, 11}
    };

    std::pair<char const*, char const*> myPair = std::make_pair("1", "2");
    auto it = sums.find(myPair);
    std::cout << it->second << std::endl;
    return 0;
}
user_55173780

C++ 11

Unfortunately you don't have std::string_view yet.

If you've received two std::string on the fly, you can always use std::move to avoid a copy if that's all that you want to do.

e.g. :

void findInMap(std::map<std::pair<std::string, std::string>, long> map, 
   std::string && string1, std::string && string2)
{
   const auto key = std::make_pair(std::move(string1), std::move(string2));
   const auto itr = map.find(key);
   if(itr != map.end())
   {
      const auto value = itr->second;
   }
}
user_88702240

C++11 "Solution"

If you define a map such that the Key's const char* members point to strings that are safely stored in the value, you can probably do what you want. I've got the Value inside a std::unique_ptr to ensure that the const char* in the key always points to safe memory. It's possible that the std::strings in Value return the same value from c_str before and after moves, but I don't think the standard requires this.

struct Key
{
   const char* key1;
   const char* key2;
   bool operator<(const Key& k) {
     auto cmp1 = strcmp(key1, k.key1);
     if (cmp1 < 0) return true;
     if (cmp1 == 0) return strcmp(key2,k.key2) < 0;
     return false;
   }
};
struct Value
{
   const std::string key1;
   const std::string key2;
   long value;
};
 
std::map<Key, std::unique_ptr<Value>> map;

When inserting into such a monstrosity, you need to be careful though. Insert must be implemented using the map's value type - not (ever!) by using the [] operator. This is because the map's key cannot be changed, and using the [] operator default-creates the value. So after [] returns, it's too late to set the const char*'s in the key to what they need to be.

Instead you have to jump through these hoops.

std::pair<Key, std::unique_ptr<Value>> new_value;

new_value.second = std::make_unique<Value>(Value{"String1","String2"});
new_value.first = Key{new_value.second.key1.c_str(), new_value.second.key2.c_str()};

map.insert(std::move(new_value));

Lookups may then be performed without copying of strings

map.find(Key{"String1","String2"});

Whether or not this is worth it is left as an exercise for the reader.

user_9869610
Related