This is the mail archive of the
gcc-bugs@gcc.gnu.org
mailing list for the GCC project.
[Bug libstdc++/67922] std::unordered_map::clear should take time linear in the number of elements
- From: "yegor.derevenets at gmail dot com" <gcc-bugzilla at gcc dot gnu dot org>
- To: gcc-bugs at gcc dot gnu dot org
- Date: Mon, 12 Oct 2015 09:06:49 +0000
- Subject: [Bug libstdc++/67922] std::unordered_map::clear should take time linear in the number of elements
- Auto-submitted: auto-generated
- References: <bug-67922-4 at http dot gcc dot gnu dot org/bugzilla/>
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=67922
--- Comment #2 from Yegor Derevenets <yegor.derevenets at gmail dot com> ---
> But then the issue is that clear () doesn't shrink the map.
No, the issue is that clear() touches all the buckets, instead of touching only
those containing the elements. libc++'s implementation does not shrink the map
(does not decrease the number of buckets), and is still fast. Actually, if in
libstdc++ you do m.erase(m.begin(), m.end()) instead of m.clear(), it will be
fast too.
#include <iostream>
#include <unordered_map>
int main() {
std::unordered_map<int, int> m;
for (int i = 0; i < 1000000; ++i) {
m[i] = i;
}
std::cout << "Before clear(): " << m.bucket_count() << std::endl;
m.clear();
std::cout << "After clear(): " << m.bucket_count() << std::endl;
}
$ clang++-3.7 -stdlib=libstdc++ -O2 -std=c++11 test.cpp && time ./a.out
Before clear(): 1056323
After clear(): 1056323
real 0m0.074s
user 0m0.076s
sys 0m0.000s
$ clang++-3.7 -stdlib=libc++ -O2 -std=c++11 test.cpp && time ./a.out
Before clear(): 1646237
After clear(): 1646237
real 0m0.102s
user 0m0.080s
sys 0m0.016s