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]
(In reply to comment #0) > 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. No, the current standard does not. The C++0x draft does, but it's not yet a standard, and parts of it are not yet implemented.
(In reply to comment #1) > (In reply to comment #0) > > 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. > > No, the current standard does not. > > The C++0x draft does, but it's not yet a standard, and parts of it are not yet > implemented. The current standard is now C++11. 23.2.1, Table 96 explicitly states that the size() method of Containers must execute in constant time. Can this bug please be changed to confirmed? As of today (r178989), std::list<>::size() is still O(N).
It's already confirmed, NEW means confirmed.
Maybe I can do this in time for 4.7, I don't make promises however, the changes are conceptually simple but quite a few throughout the class. Of course then it will definitely impossible to mix C++98 and C++11 std::lists, a data member must be added in c++0x mode in order to implement this.
Author: paolo Date: Tue Oct 4 22:19:44 2011 New Revision: 179528 URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=179528 Log: 2011-10-04 Paolo Carlini <paolo.carlini@oracle.com> PR libstdc++/49561 * include/bits/stl_list.h (_List_base<>::_List_impl::_M_size): Add in C++0x mode. (_List_base<>::_List_impl, _List_base<>::_M_get_node, _List_base<>::_M_put_node, _List_base<>::_List_base(_List_base&&), list<>::size, list<>::swap, list<>::splice): Use it. (operator==(const list<>&, const list<>&)): Rewrite in C++0x mode. * include/bits/list.tcc (list<>::erase): Likewise. (list<>::merge): Adjust in C++0x mode. * testsuite/23_containers/list/requirements/dr438/assign_neg.cc: Adjust dg-error line number. * testsuite/23_containers/list/requirements/dr438/insert_neg.cc: Likewise. * testsuite/23_containers/list/requirements/dr438/ constructor_1_neg.cc: Likewise. * testsuite/23_containers/list/requirements/dr438/ constructor_2_neg.cc: Likewise. Modified: trunk/libstdc++-v3/ChangeLog trunk/libstdc++-v3/include/bits/list.tcc trunk/libstdc++-v3/include/bits/stl_list.h trunk/libstdc++-v3/testsuite/23_containers/list/requirements/dr438/assign_neg.cc trunk/libstdc++-v3/testsuite/23_containers/list/requirements/dr438/constructor_1_neg.cc trunk/libstdc++-v3/testsuite/23_containers/list/requirements/dr438/constructor_2_neg.cc trunk/libstdc++-v3/testsuite/23_containers/list/requirements/dr438/insert_neg.cc
Done. If you can, please stress std::list in C++0x mode in order to shake possible bugs related to the O(1) size in time for the 4.7.0 release.
Thanks - I'll give it a whirl!
This change seems like it might be the first major incompatibility added to gcc's c++0x mode (at least, things appeared to work before, maybe that was just luck). I guess it will now be dangerous to even load a shared lib compiled with --std=c++0x into the same executable as C++ code compiled in the default c++03 mode, because of the potential for the exported weak symbols from out-of-line std::list functions compiled for one layout to be used on a structure defined with the other layout in the other shared object. Even when no c++ objects are ever passed from one shared lib to the other. This seems like a particularly bad failure mode to have, especially considering also bug 36022 (invalid), since it's by design difficult to *not* export the symbols even if you try. I understand that the versioned namespaces feature is supposed to help with this sort of issue; is there any plan to use it to give the c++0x std::list object a different mangled name than the c++03 std::list object?
(In reply to comment #8) > I guess it will now be dangerous to even load a shared lib compiled with > --std=c++0x into the same executable as C++ code compiled in the default c++03 > mode, It was already an ODR violation for some code, see PR 45093 There are no promises of interoperability between -std=c++98 and -std=c++0x
I can confirm it was just luck, really.
Author: paolo Date: Tue Jul 3 00:47:17 2012 New Revision: 189185 URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=189185 Log: 2012-07-02 Paolo Carlini <paolo.carlini@oracle.com> Revert: 2011-10-04 Paolo Carlini <paolo.carlini@oracle.com> PR libstdc++/49561 * include/bits/stl_list.h (_List_base<>::_List_impl::_M_size): Add in C++0x mode. (_List_base<>::_List_impl, _List_base<>::_M_get_node, _List_base<>::_M_put_node, _List_base<>::_List_base(_List_base&&), list<>::size, list<>::swap, list<>::splice): Use it. (operator==(const list<>&, const list<>&)): Rewrite in C++0x mode. * include/bits/list.tcc (list<>::erase): Likewise. (list<>::merge): Adjust in C++0x mode. * testsuite/23_containers/list/requirements/dr438/assign_neg.cc: Adjust dg-error line number. * testsuite/23_containers/list/requirements/dr438/insert_neg.cc: Likewise. * testsuite/23_containers/list/requirements/dr438/ constructor_1_neg.cc: Likewise. * testsuite/23_containers/list/requirements/dr438/ constructor_2_neg.cc: Likewise. Modified: trunk/libstdc++-v3/ChangeLog trunk/libstdc++-v3/include/bits/list.tcc trunk/libstdc++-v3/include/bits/stl_list.h trunk/libstdc++-v3/testsuite/23_containers/list/requirements/dr438/assign_neg.cc trunk/libstdc++-v3/testsuite/23_containers/list/requirements/dr438/constructor_1_neg.cc trunk/libstdc++-v3/testsuite/23_containers/list/requirements/dr438/constructor_2_neg.cc trunk/libstdc++-v3/testsuite/23_containers/list/requirements/dr438/insert_neg.cc
Author: paolo Date: Tue Jul 3 01:37:48 2012 New Revision: 189186 URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=189186 Log: 2012-07-02 Paolo Carlini <paolo.carlini@oracle.com> Revert: 2011-10-04 Paolo Carlini <paolo.carlini@oracle.com> PR libstdc++/49561 * include/bits/stl_list.h (_List_base<>::_List_impl::_M_size): Add in C++0x mode. (_List_base<>::_List_impl, _List_base<>::_M_get_node, _List_base<>::_M_put_node, _List_base<>::_List_base(_List_base&&), list<>::size, list<>::swap, list<>::splice): Use it. (operator==(const list<>&, const list<>&)): Rewrite in C++0x mode. * include/bits/list.tcc (list<>::erase): Likewise. (list<>::merge): Adjust in C++0x mode. * testsuite/23_containers/list/requirements/dr438/assign_neg.cc: Adjust dg-error line number. * testsuite/23_containers/list/requirements/dr438/insert_neg.cc: Likewise. * testsuite/23_containers/list/requirements/dr438/ constructor_1_neg.cc: Likewise. * testsuite/23_containers/list/requirements/dr438/ constructor_2_neg.cc: Likewise. Modified: branches/gcc-4_7-branch/libstdc++-v3/ChangeLog branches/gcc-4_7-branch/libstdc++-v3/include/bits/list.tcc branches/gcc-4_7-branch/libstdc++-v3/include/bits/stl_list.h branches/gcc-4_7-branch/libstdc++-v3/testsuite/23_containers/list/requirements/dr438/assign_neg.cc branches/gcc-4_7-branch/libstdc++-v3/testsuite/23_containers/list/requirements/dr438/constructor_1_neg.cc branches/gcc-4_7-branch/libstdc++-v3/testsuite/23_containers/list/requirements/dr438/constructor_2_neg.cc branches/gcc-4_7-branch/libstdc++-v3/testsuite/23_containers/list/requirements/dr438/insert_neg.cc
Patch reverted, thus in C++11 mode size() is back to O(n) but std::list can interoperate with the C++98 version of it.
(In reply to comment #13) > Patch reverted, thus in C++11 mode size() is back to O(n) but std::list can > interoperate with the C++98 version of it. Why has this been reverted? If std::list<>::size() is not O(1), then GCC's C++11 standard library is not compliant with the C++11 international standard. I have personally spoken with multiple members of the standard body and confirmed that this behavior is REQUIRED by the C++11 standard. Please re-apply this patch for C++11 mode, or state somewhere in the GCC docs that GCC is not compliant with the C++11 standard. In the C++03 and C++98 standards, it was highly suggested that compiler vendors implement std::list<>::size() as O(1). I understand this is a breaking change, but honestly, the C++ standard has been suggesting the O(1) implementation for over a decade, and the GCC standard library developers have chosen to implement different behavior. You've had many years of warning about this. (In reply to comment #10) > I can confirm it was just luck, really. ^ Paolo, this is correct. I think it's a really, really bad idea for any particular vendor to cherrypick elements of an ISO standard to implement. If you feel that the C++11 standard is wrong to require an O(1) implementation, please file a standard defect (I'm afraid you can expect me to fight it). Otherwise, I'd like to ask that you please reconsider applying this patch.
Also, didn't this already make it into the 4.7 release? Wouldn't reverting it now just cause incompatibilities with 4.7 and both older and newer releases?
(In reply to comment #14) > (In reply to comment #13) > > Patch reverted, thus in C++11 mode size() is back to O(n) but std::list can > > interoperate with the C++98 version of it. > > Why has this been reverted? If std::list<>::size() is not O(1), then GCC's > C++11 standard library is not compliant with the C++11 international standard. > I have personally spoken with multiple members of the standard body and > confirmed that this behavior is REQUIRED by the C++11 standard. Yes, we're well aware of that, thanks. This patch made c++98 and c++11 code incompatible and is causing serious problems for distros. You've lived with O(n) size for 15 years, you can live with it for a while longer until libstdc++'s ABI changes. > Please re-apply this patch for C++11 mode, or state somewhere in the GCC docs > that GCC is not compliant with the C++11 standard. In the C++03 and C++98 > standards, it was highly suggested that compiler vendors implement > std::list<>::size() as O(1). > > I understand this is a breaking change, but honestly, the C++ standard has been > suggesting the O(1) implementation for over a decade, and the GCC standard > library developers have chosen to implement different behavior. You've had many > years of warning about this. You seem to think we were taken by surprise, that has nothing to do with it. GCC has maintained ABI compatibility since version 3.4, including between c++98 and c++11 mode in most cases. This change broke that and caused a lot of problems in real systems (not just "you don't implement the standard!") and has been reverted until the entire library ABI gets updated at a later date. > (In reply to comment #10) > > I can confirm it was just luck, really. > > ^ Paolo, this is correct. I think it's a really, really bad idea for any > particular vendor to cherrypick elements of an ISO standard to implement. If > you feel that the C++11 standard is wrong to require an O(1) implementation, > please file a standard defect (I'm afraid you can expect me to fight it). > Otherwise, I'd like to ask that you please reconsider applying this patch. Calm down. Noone thinks it's wrong, but maintaining ABI compatibility has been decided to be more important for the current releases. See the mailing lists for more information.
(In reply to comment #15) > Also, didn't this already make it into the 4.7 release? Wouldn't reverting it > now just cause incompatibilities with 4.7 and both older and newer releases? Yes. But 4.7.0 and 4.7.1 are already incompatible with older releases. The maintainers have taken the decision to restore compatibility with older releases. We plan to try and reimplement the change in a cleaner way asap.
setting ABI keyword as this can't be properly fixed without an incompatible change
Author: redi Date: Fri Oct 10 15:33:57 2014 New Revision: 216094 URL: https://gcc.gnu.org/viewcvs?rev=216094&root=gcc&view=rev Log: PR libstdc++/49561 * acinclude.m4 (GLIBCXX_ENABLE_LIBSTDCXX_CXX11_ABI): Define. * configure.ac: Use GLIBCXX_ENABLE_LIBSTDCXX_CXX11_ABI. * configure: Regenerate. * include/Makefile.am (stamp-cxx11-abi): New target. (c++config.h): Set _GLIBCXX_USE_CXX11_ABI macro. * include/Makefile.in: Regenerate. * include/bits/c++config: Add _GLIBCXX_USE_CXX11_ABI placeholder and define _GLIBCXX_DEFAULT_ABI_TAG. * include/bits/list.tcc (list::emplace(const_iterator, _Args&...)): Increment size. (list::emplace(const_iterator, const value_type&)): Likewise. (list::merge(list&), list::merge(list&, _StrictWeakOrdering)): Adjust list sizes. * include/bits/stl_list.h (_List_base, list): Add ABI tag macro. (_List_base::_M_size): New data member in cxx11 ABI mode. (_List_base::_S_distance(_List_node_base*, _List_node_base*)): New function. (_List_base::_M_get_size(), _List_base::_M_set_size(size_t), _List_base::_M_inc_size(size_t), _List_base::_M_dec_size(size_t), _List_base::_M_distance, _List_base::_M_node_count): New functions for accessing list size correctly for the ABI mode. (_List_base::_List_base(_List_base&&)): Copy size and reset source. (_List_base::_M_init()): Initialize size member. (list::size()): Use _List_base::_M_node_count. (list::swap(list&)): Swap sizes. (list::splice(iterator, list&)): Update sizes. (list::splice(iterator, list&, iterator)): Likewise. (list::insert(iterator, const value_type&)): Update size. (list::insert(iterator, _Args&&...)): Likewise. (list::_M_erase(iterator)): Likewise. * testsuite/23_containers/list/requirements/dr438/assign_neg.cc: Adjust. * testsuite/23_containers/list/requirements/dr438/constructor_1_neg.cc: Adjust. * testsuite/23_containers/list/requirements/dr438/constructor_2_neg.cc: Adjust. * testsuite/23_containers/list/requirements/dr438/insert_neg.cc: Adjust. * testsuite/ext/profile/mutex_extensions_neg.cc: Adjust. Modified: trunk/libstdc++-v3/ChangeLog trunk/libstdc++-v3/acinclude.m4 trunk/libstdc++-v3/configure trunk/libstdc++-v3/configure.ac trunk/libstdc++-v3/include/Makefile.am trunk/libstdc++-v3/include/Makefile.in trunk/libstdc++-v3/include/bits/c++config trunk/libstdc++-v3/include/bits/list.tcc trunk/libstdc++-v3/include/bits/stl_list.h trunk/libstdc++-v3/testsuite/23_containers/list/requirements/dr438/assign_neg.cc trunk/libstdc++-v3/testsuite/23_containers/list/requirements/dr438/constructor_1_neg.cc trunk/libstdc++-v3/testsuite/23_containers/list/requirements/dr438/constructor_2_neg.cc trunk/libstdc++-v3/testsuite/23_containers/list/requirements/dr438/insert_neg.cc trunk/libstdc++-v3/testsuite/ext/profile/mutex_extensions_neg.cc
Fixed for 5.0
Author: redi Date: Fri Oct 10 16:14:52 2014 New Revision: 216097 URL: https://gcc.gnu.org/viewcvs?rev=216097&root=gcc&view=rev Log: PR libstdc++/49561 * acinclude.m4 (GLIBCXX_ENABLE_LIBSTDCXX_CXX11_ABI): Define. * configure.ac: Use GLIBCXX_ENABLE_LIBSTDCXX_CXX11_ABI. * configure: Regenerate. * include/Makefile.am (stamp-cxx11-abi): New target. (c++config.h): Set _GLIBCXX_USE_CXX11_ABI macro. * include/Makefile.in: Regenerate. * include/bits/c++config: Add _GLIBCXX_USE_CXX11_ABI placeholder and define _GLIBCXX_DEFAULT_ABI_TAG. * include/bits/list.tcc (list::emplace(const_iterator, _Args&...)): Increment size. (list::emplace(const_iterator, const value_type&)): Likewise. (list::merge(list&), list::merge(list&, _StrictWeakOrdering)): Adjust list sizes. * include/bits/stl_list.h (_List_base, list): Add ABI tag macro. (_List_base::_M_size): New data member in cxx11 ABI mode. (_List_base::_S_distance(_List_node_base*, _List_node_base*)): New function. (_List_base::_M_get_size(), _List_base::_M_set_size(size_t), _List_base::_M_inc_size(size_t), _List_base::_M_dec_size(size_t), _List_base::_M_distance, _List_base::_M_node_count): New functions for accessing list size correctly for the ABI mode. (_List_base::_List_base(_List_base&&)): Copy size and reset source. (_List_base::_M_init()): Initialize size member. (list::size()): Use _List_base::_M_node_count. (list::swap(list&)): Swap sizes. (list::splice(iterator, list&)): Update sizes. (list::splice(iterator, list&, iterator)): Likewise. (list::insert(iterator, const value_type&)): Update size. (list::insert(iterator, _Args&&...)): Likewise. (list::_M_erase(iterator)): Likewise. * testsuite/23_containers/list/requirements/dr438/assign_neg.cc: Adjust. * testsuite/23_containers/list/requirements/dr438/constructor_1_neg.cc: Adjust. * testsuite/23_containers/list/requirements/dr438/constructor_2_neg.cc: Adjust. * testsuite/23_containers/list/requirements/dr438/insert_neg.cc: Adjust. * testsuite/ext/profile/mutex_extensions_neg.cc: Adjust. # End of auto-generated commit message Fix date and whitespace in libstdc++-v3/ChangeLog Modified: trunk/libstdc++-v3/ChangeLog