爲什麼STL集大小複雜度是O（1），它是如何計算的？

一組內部維護爲平衡二叉樹。計算集合的大小的複雜度是O（1）。尺寸是如何計算的，它是否保存任何變量來存儲尺寸。爲什麼STL集大小複雜度是O（1），它是如何計算的？

2016-02-06 kiran

該標準從未定義應該如何完成某件事情。它定義了像'O（1）'這樣的需求，然後把如何實現這個功能的細節留給庫實現者。但保持一個變量與元素的數量似乎是一個簡單的方法來做到這一點。注意：標準並沒有說一個集合需要是一個平衡的二叉樹。它指定了一些訪問特性（可以使用平衡二叉樹實現，因此它可能是實現std :: set的一種方式）。 –

當你RTFS - 你可以看到是 - 成員變量計數RB-Tree中的節點，這是stl-set的基礎。

E.g.看到https://www.sgi.com/tech/stl/stl_tree.h：

size_type _M_node_count; // keeps track of size of tree 

size_type size() const { return _M_node_count; } 

template <class _Key, class _Value, class _KeyOfValue, 
      class _Compare, class _Alloc> 
typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::iterator 
_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc> 
    ::_M_insert(_Base_ptr __x_, _Base_ptr __y_, const _Value& __v) 
{ 
    // ... 
    ++_M_node_count; 
    return iterator(__z); 
}

來源

2016-02-06 12:21:36 PiotrNycz

我相信這對於所有可能的實現都是最新的。 – Puppy

該規範規定只是說，所有set S（實際上，所有容器）有size()成員函數，它一定的時間。除此之外，標準庫的特定版本的實現者可能已經完成了它，只要它是O(1)即可。

實際上，大小可能存儲在一個成員變量中，該成員變量在插入或刪除項目時被更新; PiotrNycz的實施者已經做到了。

來源

2016-02-06 13:53:01 alcedine

爲什麼STL集大小複雜度是O（1），它是如何計算的？

回答

相關問題