Corrupted map from using `insert_at_position`

[BenjiHansell]

Firstly, thank you @Tessil for your selection brilliant open source hash tables.

An example of my issue would be:

tsl::ordered_set<std::string_view> foo;
foo.emplace("kind");
foo.emplace("oldUri");
foo.emplace("newUri");
foo.insert_at_position(foo.begin(), "annotationId");
std::cout << foo.count("kind") << std::endl; // incorrectly prints "0"

Making further calls on the same set reveals that the "kind" key is actually present:

std::cout << foo.size() << std::endl; // correctly prints "4"
for (auto key : foo) {
  std::cout << key << ", "; // correctly prints "annotationId, kind, oldUri, newUri, "
}
std::cout << std::endl;

And we can even get a duplicate key to appear in the map:

foo.emplace("kind");
std::cout << foo.count("kind") << std::endl; // prints "1"
std::cout << foo.size() << std::endl; // prints "5"
for (auto key : foo) {
  std::cout << key << ", "; // prints "annotationId, kind, oldUri, newUri, kind, "
}
std::cout << std::endl;

That is with Apple clang version 14.0.0 (clang-1400.0.29.202) using libc++.

ordered-map version: 1.0.0

[Tessil]

Thank you for the report.

From a quick test with clang++-14.0.6 and g+-12.2.0 with -O3 using libstdc++ on you provided example I get the expected results:

1
4
annotationId, kind, oldUri, newUri, 
1
4
annotationId, kind, oldUri, newUri,

I'll check more in depth when I have some time as your results are quite worrying.

[BenjiHansell]

In case it helps, I've managed to create a better reproduction which fails on every platform I've tried it on:

  tsl::ordered_set<std::size_t, IdentityHash> foo;
  foo.emplace(1657314675755591361ull);
  foo.emplace(8148226713986838624ull);
  foo.insert_at_position(foo.begin(), 17991626144733246576ull);
  std::cout << foo.count(1657314675755591361ull); // always prints 0

where

struct IdentityHash {
  std::size_t operator()(std::size_t x) const { return x; }
};

that fails on

• Visuals Studio 2019 (192930143)
• Apple clang 14.0.0 (libc++) (both ARM & x64)
• GCC 11.2 (not sure which standard lib) (both ARM & x64)

On at least some of those I've tested with and without NDEBUG and with varied optimisation levels. So I'm pretty sure this version will reproduce on any compiler or standard library you care to try.

[Tessil]

Thank you very much for the example.

I was able to reproduce the error and pushed a fix. Both insert_at_position and erase are affected (not unordered_erase and pop_back). Could you try it out?

I'll check to add some extra tests later.

[Tessil]

I merged the PR and created a new release. Thanks for the help.

I will close the issue. Let me know if you encounter any problem and I can reopen it.

[BenjiHansell]

Many thanks for the speedy fix. It works on my end too.