public inbox for gcc-bugs@sourceware.org help / color / mirror / Atom feed
From: "yoch.melka at gmail dot com" <gcc-bugzilla@gcc.gnu.org> To: gcc-bugs@gcc.gnu.org Subject: [Bug libstdc++/49561] New: gcc does not meet the standard for std::list container Date: Tue, 28 Jun 2011 08:18:00 -0000 [thread overview] Message-ID: <bug-49561-4@http.gcc.gnu.org/bugzilla/> (raw) http://gcc.gnu.org/bugzilla/show_bug.cgi?id=49561 Summary: gcc does not meet the standard for std::list container Product: gcc Version: 4.5.2 Status: UNCONFIRMED Severity: major Priority: P3 Component: libstdc++ AssignedTo: unassigned@gcc.gnu.org ReportedBy: yoch.melka@gmail.com I realized that the complexity of std::list::size() is O(n), not O(1). This does not conform to standard. The standard states that size() function is in constant time for alls containers. So, the behavior of gcc is not as expected. This also affects parts of std::list::splice() function, as mentioned in the last drat (n3242 - 23.3.5.5): [quote] 1 Since lists allow fast insertion and erasing from the middle of a list, certain operations are provided specifically for them. 2 list provides three splice operations that destructively move elements from one list to another.[...] void splice(const_iterator position, list<T,Allocator>& x) noexcept; void splice(const_iterator position, list<T,Allocator>&& x) noexcept; [...] 4 Effects: Inserts the contents of x before position and x becomes empty. Pointers and references to the moved elements of x now refer to those same elements but as members of *this. Iterators referring to the moved elements will continue to refer to their elements, but they now behave as iterators into *this, not into x. 5 Complexity: Constant time. void splice(const_iterator position, list<T,Allocator>& x, const_iterator i) noexcept; void splice(const_iterator position, list<T,Allocator>&& x, const_iterator i) noexcept; 6 Effects: Inserts an element pointed to by i from list x before position and removes the element from x. The result is unchanged if position == i or position == ++i. Pointers and references to *i continue to refer to this same element but as a member of *this. Iterators to *i (including i itself) continue to refer to the same element, but now behave as iterators into *this, not into x. [...] 8 Complexity: Constant time. void splice(const_iterator position, list<T,Allocator>& x, const_iterator first, const_iterator last) noexcept; void splice(const_iterator position, list<T,Allocator>&& x, const_iterator first, const_iterator last) noexcept; 9 Effects: Inserts elements in the range [first,last) before position and removes the elements from x. [...] 11 Complexity: Constant time if &x == this; otherwise, linear time. [/quote]
next reply other threads:[~2011-06-28 8:18 UTC|newest] Thread overview: 24+ messages / expand[flat|nested] mbox.gz Atom feed top 2011-06-28 8:18 yoch.melka at gmail dot com [this message] 2011-06-28 8:48 ` [Bug libstdc++/49561] " redi at gcc dot gnu.org 2011-06-28 10:09 ` [Bug libstdc++/49561] [C++0x] std::list::size complexity paolo.carlini at oracle dot com 2011-09-20 0:59 ` blelbach at cct dot lsu.edu 2011-09-20 1:05 ` paolo.carlini at oracle dot com 2011-09-21 11:56 ` paolo.carlini at oracle dot com 2011-10-04 22:20 ` paolo at gcc dot gnu.org 2011-10-04 22:23 ` paolo.carlini at oracle dot com 2011-10-04 23:06 ` blelbach at cct dot lsu.edu 2011-10-07 1:26 ` foom at fuhm dot net 2011-10-07 1:37 ` redi at gcc dot gnu.org 2011-10-07 1:38 ` paolo.carlini at oracle dot com 2012-07-03 0:48 ` paolo at gcc dot gnu.org 2012-07-03 1:38 ` paolo at gcc dot gnu.org 2012-07-03 1:40 ` paolo.carlini at oracle dot com 2012-07-03 3:36 ` blelbach at cct dot lsu.edu 2012-07-03 3:39 ` blelbach at cct dot lsu.edu 2012-07-03 8:32 ` redi at gcc dot gnu.org 2012-07-03 8:35 ` redi at gcc dot gnu.org 2012-08-22 19:47 ` redi at gcc dot gnu.org 2012-09-15 6:06 ` pinskia at gcc dot gnu.org 2014-10-10 15:34 ` redi at gcc dot gnu.org 2014-10-10 16:00 ` redi at gcc dot gnu.org 2014-10-10 16:15 ` redi at gcc dot gnu.org
Reply instructions: You may reply publicly to this message via plain-text email using any one of the following methods: * Save the following mbox file, import it into your mail client, and reply-to-all from there: mbox Avoid top-posting and favor interleaved quoting: https://en.wikipedia.org/wiki/Posting_style#Interleaved_style * Reply using the --to, --cc, and --in-reply-to switches of git-send-email(1): git send-email \ --in-reply-to=bug-49561-4@http.gcc.gnu.org/bugzilla/ \ --to=gcc-bugzilla@gcc.gnu.org \ --cc=gcc-bugs@gcc.gnu.org \ /path/to/YOUR_REPLY https://kernel.org/pub/software/scm/git/docs/git-send-email.html * If your mail client supports setting the In-Reply-To header via mailto: links, try the mailto: linkBe sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).