作者aecho (星空下的鮪魚)
看板C_and_CPP
標題[問題] 關於set,multiset
時間Wed Jun 1 10:04:04 2005
看書說這一類的是用二元平衡樹做的
那有沒有方法可以取得這個樹的root (p.s. O(1)的時間)
或left child , right child的operator呢??
還是說 一定要用iterator一個一個存取?
--
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.166.90.153
※ 編輯: aecho 來自: 218.166.90.153 (06/01 10:04)
> -------------------------------------------------------------------------- <
作者: khoguan (Khoguan Phuann) 看板: C_and_CPP
標題: Re: [問題] 關於set,multiset
時間: Wed Jun 1 23:10:09 2005
※ 引述《aecho (星空下的鮪魚)》之銘言:
: 看書說這一類的是用二元平衡樹做的
: 那有沒有方法可以取得這個樹的root (p.s. O(1)的時間)
: 或left child , right child的operator呢??
: 還是說 一定要用iterator一個一個存取?
SGI 系的 STL 是用 RB-tree
包在 map/multimap/set/multiset 中的 rb_tree 是 private member
而 rb_tree 中存取上述東東的是 protected function
參考 侯捷老師的「STL源碼剖析」一書。
另有 hash table 做的 hash_set, hash_map 雖然很多 C++ library
provider 都有提供,但將來才會納入 C++ 標準中(改稱 unordered_set,
unordered_map)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.130.208.168
> -------------------------------------------------------------------------- <
作者: aecho (星空下的鮪魚) 看板: C_and_CPP
標題: Re: [問題] 關於set,multiset
時間: Thu Jun 2 00:10:40 2005
※ 引述《khoguan (Khoguan Phuann)》之銘言:
: SGI 系的 STL 是用 RB-tree
: 包在 map/multimap/set/multiset 中的 rb_tree 是 private member
: 而 rb_tree 中存取上述東東的是 protected function
: 參考 侯捷老師的「STL源碼剖析」一書。
: 另有 hash table 做的 hash_set, hash_map 雖然很多 C++ library
: provider 都有提供,但將來才會納入 C++ 標準中(改稱 unordered_set,
: unordered_map)
@@ 看來要在多買一本書的樣子了 >"<
我現在看的書裏面感覺只有public function
感謝 ^^
--
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.167.215.31
> -------------------------------------------------------------------------- <
作者: aecho (星空下的鮪魚) 看板: C_and_CPP
標題: Re: [問題] 關於set,multiset
時間: Thu Jun 2 10:20:36 2005
※ 引述《khoguan (Khoguan Phuann)》之銘言:
: SGI 系的 STL 是用 RB-tree
: 包在 map/multimap/set/multiset 中的 rb_tree 是 private member
: 而 rb_tree 中存取上述東東的是 protected function
可以再請教一下嗎
map/multimap/set/multiset的protected functions
是不是也都是標準的一部份
還是說 會因為實作時 隨著各家的版本有所不同
有時候書看一看就會冒出 一些實作的細結
會因為各家實作時有所不同
就會害怕codes寫一寫拿到別的地方不能run ....
--
靜待風帆將起之日
乘風隨夢....
到那不知名的未知裡..
探尋....深夜靜謐的想望...
探尋....潛藏心底的自己...
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.166.90.210
> -------------------------------------------------------------------------- <
作者: khoguan (Khoguan Phuann) 看板: C_and_CPP
標題: Re: [問題] 關於set,multiset
時間: Thu Jun 2 13:12:42 2005
※ 引述《aecho (星空下的鮪魚)》之銘言:
: ※ 引述《khoguan (Khoguan Phuann)》之銘言:
: : SGI 系的 STL 是用 RB-tree
: : 包在 map/multimap/set/multiset 中的 rb_tree 是 private member
: : 而 rb_tree 中存取上述東東的是 protected function
: 可以再請教一下嗎
: map/multimap/set/multiset的protected functions
: 是不是也都是標準的一部份
這個我沒有細看 ISO/IEC 14882-2003 標準文件中的說明,
我想若是其中有列的就是可以放心用,其實上述提到的
associative container 中有列的 protected member
很少,我剛才search了一下,只看到
Compare comp;
value_compare(Compare c) : comp(c) {}
若沒列的 protected function但出現在各家版本中的,也許
就不 portable
: 還是說 會因為實作時 隨著各家的版本有所不同
: 有時候書看一看就會冒出 一些實作的細結
: 會因為各家實作時有所不同
: 就會害怕codes寫一寫拿到別的地方不能run ....
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.130.208.168
推 UNARYvvv:C++ Standard 不是 1998 和 2003 嗎? 61.70.137.117 06/02
※ 編輯: khoguan 來自: 220.130.208.168 (06/02 21:53)
推 khoguan:嗚~~心裡想的是2003,怎麼打成2002了。謝謝指正220.130.208.168 06/02
推 aecho:啊 突然發現忘了說謝謝~~ 感恩 ^^ 218.166.91.181 06/04