Trong GCC, phương thức size() của std :: list là O (n). Tại sao?

Question

Trong GCC, phương thức size() của std :: list là O (n). Tại sao?

cho C++ 11 trong Tiêu chuẩn nói size() của danh sách nên O (1) http://en.cppreference.com/w/cpp/container/list/size

Tuy nhiên trong glibc, chúng tôi đã điều sau đây:

/usr/include/c++/4.6.3/bits/stl_list.h 

template<typename _Tp, typename _Alloc = std::allocator<_Tp> > 
class list : protected _List_base<_Tp, _Alloc> 
{ 
... 
size_type 
    size() const 
    { return std::distance(begin(), end()); } 

Câu hỏi đặt ra là: Làm thế nào có phải là yêu cầu 3 năm chưa được thực hiện trong GCC?

EDIT: gcc 5 thay đổi điều này: mặc dù với chi phí thay đổi ABI; điều này có nghĩa là mã C++ được biên dịch với gcc 5.0 sẽ không hoạt động với các phiên bản cũ hơn của thư viện thời gian chạy C++.

từ https://gcc.gnu.org/gcc-5/changes.html "Một thực hiện mới của std :: danh sách được kích hoạt theo mặc định, với O (1) kích thước() chức năng"

Answer 1

Trong C++ 98/03 nó là không xác định là liệu std::list::size() là O (1) hoặc O (N). Có sự cân bằng cho cả hai quyết định.

Trong C++ 11, ủy ban đã chỉ định rằng std::list::size() là O (1). Đây là một thay đổi ABI phá vỡ cho việc triển khai có O (N) std::list::size() và gcc là một triển khai như vậy. Phá vỡ ABI là một vấn đề lớn đối với người triển khai. Nó gây ra rất nhiều đau đớn cho khách hàng của mình. Vì vậy, nó được thực hiện chỉ một lần trong một thời gian dài, và với sự phô trương tương đối lớn.