Как избежать копирования при поиске в std :: map с помощью составных ключей - PullRequest
Новая
       13

Как избежать копирования при поиске в std :: map с помощью составных ключей

1 голос
/ 18 марта 2020

Предположим, у меня есть карта, которая отображает две строки в длинную: 

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

Если я хочу выполнить поиск по карте, потребуется std::pair<std::string, std::string>. Если я получаю две строки для поиска по-разному, я должен на лету построить std::pair, который AFAIK копирует строки: 

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

Если поиск на карте LOT, есть ли способ не копировать строки для выполнения поиска? Копировать не нужно, это требуется только по семантике std::map.

РЕДАКТИРОВАТЬ: я не привязан к std :: pair в качестве ключа, это может быть что угодно, даже пользовательская структура, так как Пока он может хранить элементы в карте по значению и искать их без копии.

Ответы [ 2 ]

1 голос
/ 18 марта 2020

C ++ 17

Поскольку вы сказали, что также заинтересованы в решении C ++ 17, вы можете воспользоваться std::string_view, который не выделяет никакой памяти, а просто содержит указатель на фактические данные и длину строки. Таким образом, операция копирования является легкой.

Конечное решение будет выглядеть следующим образом: 

#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

Если вы ограничены C ++ 11, тогда вы можете использовать char const* в качестве std::pair членов, но тогда вам нужно определить пользовательскую функцию сравнения, например: 

#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;
}
0 голосов
/ 18 марта 2020

C ++ 11

К сожалению, у вас еще нет std::string_view.

Если вы получили два std::string на лету, вы всегда можете используйте std::move, чтобы избежать копирования, если это все, что вы хотите сделать.

Например: 

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