在GCC中，std :: list的size（）方法是O（n）。爲什麼？

在GCC中，std :: list的size（）方法是O（n）。爲什麼？在GCC中，std :: list的size（）方法是O（n）。爲什麼？

在標準C++ 11說大小（名單）應該是O（1） http://en.cppreference.com/w/cpp/container/list/size

然而，在我們的glibc有以下：

/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()); }

的問題是：如何GCC中尚未實施三年前的要求嗎？

編輯：海灣合作委員會5改變了這一點：雖然在ABI變化的代價;這意味着使用gcc 5.0編譯的C++代碼將不適用於舊版本的C++運行時庫。

從 https://gcc.gnu.org/gcc-5/changes.html

「的std ::列表的新的實現是默認啓用，用O（1）尺寸（）函數」

來源

2014-10-27 MichaelMoser

g ++ 4.5 is from 2010.獲取最新版本！ – 2014-10-27 03:31:50

很不錯，在4.6.3中它也是一樣的東西 – MichaelMoser 2014-10-27 03:39:41

在4.8.3中也是一樣的！ – Galik 2014-10-27 04:00:45

在C++ 98/03是未具體說明以是否std::list::size()是O（1）或O（N）。任何決定都有權衡。

在C++ 11中，委員會指定std::list::size()是O（1）。對於具有O（N）std::list::size()的實現，這是一個ABI突破性更改，而gcc就是這樣的實現。打破ABI對於實現者來說是一件大事。它給客戶帶來了很大的痛苦。所以它只會在一段時間內完成一次，並且會有相當大的誇誇其談。

來源

2014-10-27 03:39:54

那他們怎麼經常更改名稱修改算法呢？您無法將新的二進制文件鏈接到使用舊的名稱修改算法編譯的二進制文件。 https://gcc.gnu.org/onlinedocs/gcc/C_002b_002b-Dialect-Options.html – MichaelMoser 2014-10-27 03:48:37

@MichaelMoser這個名字是* *不是由標準規定的。它依賴於實現。 – 2014-10-27 04:05:01

@MarkRansom仍然能夠鏈接到使用舊版本編譯器編譯的二進制文件，它就像ABI更改一樣突破。 – MichaelMoser 2014-10-27 04:06:41

在GCC中，std :: list的size（）方法是O（n）。爲什麼？

回答

相關問題