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: unassig...@gcc.gnu.org
ReportedBy: yoch.me...@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]
