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)