[Bug libstdc++/44480] New: Linear performance of begin() in unordered associative containers

[joaquin at tid dot es]

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