]> git.ipfire.org Git - thirdparty/gcc.git/commit
libstdc++: Do not over-size hashtable buckets on range insertion
authorFrançois Dumont <fdumont@gcc.gnu.org>
Mon, 20 Jan 2020 18:01:18 +0000 (19:01 +0100)
committerFrançois Dumont <fdumont@gcc.gnu.org>
Tue, 28 Jul 2020 12:37:16 +0000 (14:37 +0200)
commit6dcf042368012e2d7ce1626ee5d378bf3ad0ccfc
tree890eb6dcaf21e33ce399cd90b97b8c3691f80502
parentf40888fff7c4dab6d654ae4f7598f23bc472d2d1
libstdc++: Do not over-size hashtable buckets on range insertion

We used to consider range size on insertion but on unique keys container
not all range values might be inserted resulting in over-sizing. In this
case we just consider user reservation and if none then the container will
adapt to actually inserted elements.

libstdc++-v3/ChangeLog:

* include/bits/hashtable.h
(_Hashtable<>(_InputIterator, _InputIterator, size_t, const _H1&,
const _H2&, const _Hash&, const _Equal&, const _ExtractKey&,
const allocator_type&, true_type)): New.
(_Hashtable<>(_InputIterator, _InputIterator, size_t, const _H1&,
const _H2&, const _Hash&, const _Equal&, const _ExtractKey&,
const allocator_type&, false_type)): New.
(_Hashtable<>(_InputIterator, _InputIterator, size_t, const _H1&,
const _H2&, const _Hash&, const _Equal&, const _ExtractKey&,
const allocator_type&)): Delegate to latters.
(operator=(initializer_list<value_type>)): Rehash if too small.
(_M_insert(_Arg&&, const _NodeGenerator&, true_type)): Remove
size_t len parameter.
* include/bits/hashtable_policy.h (_Insert_base<>::_M_insert_range):
Do not try to get input range distance.
* testsuite/23_containers/unordered_set/cons/bucket_hint.cc: New test.
* testsuite/23_containers/unordered_set/modifiers/insert.cc: New test.
libstdc++-v3/include/bits/hashtable.h
libstdc++-v3/include/bits/hashtable_policy.h
libstdc++-v3/testsuite/23_containers/unordered_set/cons/bucket_hint.cc [new file with mode: 0644]
libstdc++-v3/testsuite/23_containers/unordered_set/modifiers/insert.cc [new file with mode: 0644]