Início / coding / Perguntas / 77813605
Accepted
Voivoid
Asked: 2024-01-14 08:48:39 +0800 CST

Pesquisa transparente por um std::map com um std::pair como chave

  • 772

Se houver, std::map<std::pair<std::string, std::string>, some_type>qual é a melhor maneira de encontrar seus valores?

Acho que o mais óbvio é fazer algo assim: map.find(std::make_pair(str1, str2)); mas isso levará a uma construção de cópia das strings str1e str2durante a construção do par.

Eu esperava que talvez map.find(std::make_pair(std::ref(str1), std::ref(str2)));pudesse ajudar, mas infelizmente não, isso ainda produz cópias de strings.

map.find(std::make_pair(std::move(str1), std::move(str2))deve funcionar, mas vamos supor que essas strings ( str1, str2) sejam const ou não devam ser movidas.

Então, estou perguntando se existe alguma outra maneira de fazer uma pesquisa no mapa sem fazer cópias redundantes de strings.

(Observe que usar std::string_viewfor the std::map keyNÃO é uma opção, pois o mapa deve possuir suas strings.)

c++

3 respostas

  1. Best Answer

    C++ 14 adicionou a seguinte sobrecarga para std::map::finda qual permite pesquisa transparente:

    template< class K >
const_iterator find( const K& x ) const;

    Para fazer uso disso, você ainda precisa std::mapter um comparador adequado:

    struct pair_less {
    // important for transparent comparison, see std::map:find documentation
    using is_transparent = std::true_type;

    template <typename T, typename U>
      requires pair_less_than_comparable<T, U> // C++20, see below
    bool operator()(const T& a, const U& b) const {
        if (a.first < b.first) return true;
        if (b.first < a.first) return false;
        return a.second < b.second;
    }
};

int main() {
    std::map<std::pair<std::string, std::string>, int, pair_less> m { /* ... */ };
    // ...
    std::string a = "a", b = "b";
    // now works and creates no copies
    auto pos = m.find(std::make_pair(std::ref(a), std::ref(b)));
}

    Isto pair_lessé totalmente transparente. Ele pode ser comparado diretamente std::pair<X, Y>com std::pair<const X&, const Y&>.

    Nota sobrestd::pair::operator<

    O padrão C++ exige std::pair::operator<ser transparente desde LWG Defect 3865 . Teoricamente, isso seria std::less<void>suficiente std::ranges::lesscomo um comparador transparente.

    No entanto, libstdc++ ainda não implementa std::paircomparações transparentes no momento da escrita, portanto std::less<void>funcionaria apenas para compiladores diferentes do GCC.

    Restrições adequadas do C++ 20

    Restringir adequadamente o operador de chamada pair_lessnão é tão fácil. De qualquer forma, não é estritamente necessário, mas move o erro para o local de chamada da operadora e pode ser melhor para diagnóstico.

    A abordagem usual seria algo como

    template <typename T, typename U>
concept pair_less_than_comparable
  = requires (const T& t, const U& u) {
      { t.first < u.first } -> /* boolean-testable */;
      { t.second < u.second } -> /* boolean-testable */;
  }

    Veja também boolean-testable.

    • 12

  2. Para evitar a construção de chave, você pode usar std::mapum comparador transparente. Em muitos casos, você não precisa implementar o seu próprio - o padrão fornece std::less<>isso para fazer o trabalho.

    Infelizmente, não funcionará com std::pairchaves porque std::pair faltam comparações heterogêneas : você não pode comparar std::pair<std::string, std::string>com std::pair<const std::string&, const std::string&>.

    Mas se você pudesse mudar std::pairpara std::tuple, funcionaria:

    std::map<std::tuple<std::string, std::string>, int, std::less<>> map;
// ...
auto pos = map.find(std::make_tuple(std::cref(str1), std::cref(str2)));
    • 7

  3. Mesmo que você não possa ter std::string_viewchaves, você ainda pode usar std::string_viewpara seu comparador (já que você pode converter facilmente um std::string-> std::string_view):

    struct string_pair_comparator {
    constexpr bool operator()(std::tuple<std::string_view, std::string_view> l, std::tuple<std::string_view, std::string_view> r) const noexcept {
#ifdef __cpp_lib_three_way_comparison
        auto cmp = l <=> r;
#else
        auto cmp = std::get<0>(l).compare(std::get<0>(r));
        if (cmp == 0) cmp = std::get<1>(l).compare(std::get<1>(r));
#endif
        return cmp < 0;
    }

    using is_transparent = void;
};

std::map<std::pair<std::string, std::string>, some_type, string_pair_comparator> map;

    std::tuplefoi usado em vez de std::pairporque você pode converter pair-> tuple, mas não o contrário. Isso significa que você também pode usar teclas de tupla, que possuem funções úteis de fábrica:

    map.find(std::tie(str1, str2))
map.find(std::forward_as_tuple(str1, str2))
// pairs also still work
map.find(std::make_pair(std::ref(str1), std::ref(str2)))

    Dois compares foram usados ​​em vez de l < rporque as tuplas anteriores ao C++ 20 operator<resultariam em três memcmps em vez de dois ( l[0] < r[0]; r[0] < l[0]; l[1] < r[1]. Eles não parecem estar otimizados).

    • 0

relate perguntas