public inbox for gcc-bugs@sourceware.org
help / color / mirror / Atom feed
* [Bug libstdc++/49561] New: gcc does not meet the standard for std::list container
@ 2011-06-28  8:18 yoch.melka at gmail dot com
  2011-06-28  8:48 ` [Bug libstdc++/49561] " redi at gcc dot gnu.org
                   ` (22 more replies)
  0 siblings, 23 replies; 24+ messages in thread
From: yoch.melka at gmail dot com @ 2011-06-28  8:18 UTC (permalink / raw)
  To: gcc-bugs

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]


^ permalink raw reply	[flat|nested] 24+ messages in thread
end of thread, other threads:[~2014-10-10 16:15 UTC | newest]

Thread overview: 24+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2011-06-28  8:18 [Bug libstdc++/49561] New: gcc does not meet the standard for std::list container yoch.melka at gmail dot com
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

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).