https://gcc.gnu.org/bugzilla/show_bug.cgi?id=87135
Bug ID: 87135
Summary: [C++17] unordered containers violate iterator validity
requirements
Product: gcc
Version: 9.0
Status: UNCONFIRMED
Severity: normal
Priority: P3
Component: libstdc++
Assignee: unassigned at gcc dot gnu.org
Reporter: kariya_mitsuru at hotmail dot com
Target Milestone: ---
Please see the sample code below.
=========================== sample code ===========================
#include <iostream>
#include <unordered_set>
template<typename S>
void print(const S& s, typename S::const_iterator& it)
{
std::cout << "size = " << s.size() << '\n';
std::cout << "bucket_count = " << s.bucket_count() << '\n';
std::cout << "load_factor = " << s.load_factor() << '\n';
std::cout << "max_load_factor = " << s.max_load_factor() << '\n';
std::cout << "size limit = " << s.bucket_count() * s.max_load_factor() <<
"\n\n";
for (std::size_t i = 0; it != s.end() && i < s.size() / 2; ++i, ++it) {
std::cout << *it << ' ';
}
std::cout << "\n\n";
}
int main()
{
std::unordered_set<int> s;
const auto max = 10;
s.reserve(max);
for (int i = 0; i < max; ++i) {
s.insert(i);
}
auto it = s.cbegin();
print(s, it);
s.insert(max);
print(s, it);
}
=========================== sample code ===========================
=========================== output ===========================
size = 10
bucket_count = 11
load_factor = 0.909091
max_load_factor = 1
size limit = 11
9 8 7 6 5
size = 11
bucket_count = 23
load_factor = 0.478261
max_load_factor = 1
size limit = 23
4 5 6 7 8
=========================== output ===========================
cf. https://wandbox.org/permlink/QhPfL6787GV8RYXV
The C++17 standard 26.2.7[unord.req]/p.15 says,
The insert and emplace members shall not affect the validity of iterators if
(N+n) <= z * B, where N is the number of elements in the container prior to
the
insert operation, n is the number of elements inserted, B is the container's
bucket count, and z is the container’s maximum load factor.
So, I think that the sample code above should never rehash.
