[Bug libstdc++/106275] New: unordered_map with std::string key, std::hash<std::string>, and custom equality predicate weirdness

["cuzdav at gmail dot com" <gcc-bugzilla@gcc.gnu.org>]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=106275

            Bug ID: 106275
           Summary: unordered_map with std::string key,
                    std::hash<std::string>, and custom equality predicate
                    weirdness
           Product: gcc
           Version: 12.1.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: libstdc++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: cuzdav at gmail dot com
  Target Milestone: ---

g++12.1 (on linux), Does not occur on GCC 11 or earlier.

std::unordered_map<std::string, std::hash<std::string>, CustomPred> acts
strangely such that finds do not seem to use the hasher properly, and seem to
use a linear search, invoking the equality predicate against every key.  

A custom hasher implemented in terms of std::hash<string> fixes it, as does
using the default equality predicate.  It also does not happen with key type
of, say, "int".  I've only seen it for std::string (in my limited
experimentation.)

I added output to the predicate to indicate when it's called, and it shows
excessive calls printed when "SHOWBUG" macro is defined.


////////////////////////////////////////
#include <functional>
#include <iostream>
#include <string>
#include <unordered_map>

struct EqualToWrapper{
    bool operator()(const std::string& key1, const std::string& key2) const {
        std::cout << "equal_to(key1=" << key1 << ", key2=" << key2 << ")\n";
        return std::equal_to<>{}(key1, key2);
    }
};

#ifdef SHOWBUG
using UsageMap =  std::unordered_map<std::string, int, std::hash<std::string>,
EqualToWrapper>;
#else
struct MyHash : public std::hash<std::string> {};
using UsageMap =  std::unordered_map<std::string, int, MyHash, EqualToWrapper>;
#endif

int main() {
    UsageMap m;
    m.insert(std::make_pair("A", 111));
    m.insert(std::make_pair("B", 222));
    m.insert(std::make_pair("C", 333));
    m.insert(std::make_pair("D", 444));
    m.insert(std::make_pair("E", 555));
    m.insert(std::make_pair("F", 666));
    m.find("foo");
}
////////////////////////////////


With a custom equality predicate and my derived-from-std::hash hasher, output
on g++ 12 is:

  equal_to(key1=C, key2=A)   

When run with -DSHOWBUG macro defined, output is:
  equal_to(key1=B, key2=A)
  equal_to(key1=C, key2=B)
  equal_to(key1=C, key2=A)
  equal_to(key1=D, key2=B)
  equal_to(key1=D, key2=C)
  equal_to(key1=D, key2=A)
  equal_to(key1=E, key2=B)
  equal_to(key1=E, key2=D)
  equal_to(key1=E, key2=C)
  equal_to(key1=E, key2=A)
  equal_to(key1=F, key2=E)
  equal_to(key1=F, key2=B)
  equal_to(key1=F, key2=D)
  equal_to(key1=F, key2=C)
  equal_to(key1=F, key2=A)
  equal_to(key1=foo, key2=F)
  equal_to(key1=foo, key2=E)
  equal_to(key1=foo, key2=B)
  equal_to(key1=foo, key2=D)
  equal_to(key1=foo, key2=C)
  equal_to(key1=foo, key2=A)



On Godbolt:
https://godbolt.org/z/GP5dox1qs



$ g++ -v 
Using built-in specs.
COLLECT_GCC=g++
COLLECT_LTO_WRAPPER=/opt/imc/gcc-12.1.0/libexec/gcc/x86_64-pc-linux-gnu/12.1.0/lto-wrapper
Target: x86_64-pc-linux-gnu
Configured with: ../gcc-12.1.0/configure --prefix=/opt/imc/gcc-12.1.0
--enable-languages=c,c++,fortran,lto --disable-multilib
--with-build-time-tools=/build/INSTALLDIR//opt/imc/gcc-12.1.0/bin
--enable-libstdcxx-time=rt
Thread model: posix
Supported LTO compression algorithms: zlib
gcc version 12.1.0 (GCC)