The current implementation of begin() for unordered associative containers is
linear (a search for the first non-empty bucket is executed each time begin()
is called), yet the C++0x drafts specifiy that this should be constant (23.3.1,
table 93). Boost.Unordered, for instance, caches the first non-empty bucket on
insertion/deletion to meet the O(1) begin() requirement.
--
Summary: Linear performance of begin() in unordered associative
containers
Product: gcc
Version: 4.5.1
Status: UNCONFIRMED
Severity: normal
Priority: P3
Component: libstdc++
AssignedTo: unassigned at gcc dot gnu dot org
ReportedBy: joaquin at tid dot es
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=44480
