From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 25222 invoked by alias); 14 Aug 2013 10:35:06 -0000 Mailing-List: contact gcc-bugs-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-bugs-owner@gcc.gnu.org Received: (qmail 25180 invoked by uid 48); 14 Aug 2013 10:35:04 -0000 From: "redi at gcc dot gnu.org" To: gcc-bugs@gcc.gnu.org Subject: [Bug libstdc++/58153] unordered_multimap::erase(iterator) is not constant-time when many entries have the same key Date: Wed, 14 Aug 2013 10:35:00 -0000 X-Bugzilla-Reason: CC X-Bugzilla-Type: changed X-Bugzilla-Watch-Reason: None X-Bugzilla-Product: gcc X-Bugzilla-Component: libstdc++ X-Bugzilla-Version: 4.8.1 X-Bugzilla-Keywords: X-Bugzilla-Severity: normal X-Bugzilla-Who: redi at gcc dot gnu.org X-Bugzilla-Status: UNCONFIRMED X-Bugzilla-Priority: P3 X-Bugzilla-Assigned-To: unassigned at gcc dot gnu.org X-Bugzilla-Target-Milestone: --- X-Bugzilla-Flags: X-Bugzilla-Changed-Fields: Message-ID: In-Reply-To: References: Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: 7bit X-Bugzilla-URL: http://gcc.gnu.org/bugzilla/ Auto-Submitted: auto-generated MIME-Version: 1.0 X-SW-Source: 2013-08/txt/msg00733.txt.bz2 http://gcc.gnu.org/bugzilla/show_bug.cgi?id=58153 --- Comment #1 from Jonathan Wakely --- (In reply to Kenton Varda from comment #0) > I do not know exactly what the standard requires here, but all of the > references I can find claim that erase(iter) should be average-time O(1), > and none of them suggest that having a large number of entries with the same > key should cause trouble. The standard says average case O(1), worst case O(a.size()), so if every element in the container has the same key then it's O(n). > FWIW, it looks like libc++ has the same behavior. Maybe my expectations > were wrong, and unordered_multimap was never meant to contain more than a > couple entries per key? It supports any number of entries with the same key, you just can't expect O(1) erase operations in that case. If you have very many collisions maybe your choice of key or your choice of container isn't ideal.