C++ std::set 的實現中對於iterator的這個強制轉換是如何進行的？

01-06

看STL源碼時產生的一個問題。在stackoverflow上問了Cast of const_iterator to iterator in definition of std::set 暫時沒人理我，來貴乎碰碰運氣。
std::set 底層使用一個紅黑樹來存儲數據，所有set的數據操作（insert，erase等）都轉成紅黑樹的操作。為了禁止用戶通過set的iterator編輯set的內容，set::iterator實際上是紅黑樹的const_iterator:

typedef _Rb_tree&, key_compare, _Alloc&> _Rep_type; typedef typename _Rep_type::const_iterator iterator;
但是紅黑樹進行erase，insert等操作時需要的是non-const的iterator,於是set為了實現這些操作就必須進行一個cast：
void erase(iterator __position) { typedef typename _Rep_type::iterator _Rep_iterator; _M_t.erase((_Rep_iterator)__position); }
這裡用一個c-style cast把 set::iterator,（也就是_Rep_type::const_iterator）轉換成了_Rep_type::iterator. 我的問題是：
1. 這個cast為什麼是合法的？儘管STL中紅黑樹的const_iterator 和 iterator 實際上只差了個兩個typedef，數據成員是一樣的，但畢竟是兩個不同的類。
2. 如果要把這個cast寫成C++的幾種cast之一，該怎麼寫?const_cast和dynamic_cast顯然不行， static_cast編譯不過，reinterpret_cast倒是能編譯，但我不確定實際效果對不對。

首先要糾正幾個概念錯誤。對於初學者來說，這尤為重要。

1. 「看STL源碼時產生的一個問題。」

不，不會有STL源碼，只會有某個實現的STL源碼。STL是個標準，不是個實現。而且，問這種問題的時候，你一定要提及你所說的是哪個實現。不要讓回答者猜。你在stackoverflow上的問題也有同樣的毛病。

2. 「std::set 底層使用一個紅黑樹來存儲數據，所有set的數據操作（insert，erase等）都轉成紅黑樹的操作。」

仍然是同一個問題。你只能說某個實現的STL這麼做了，而不能說std::set這麼做了。

3. 什麼是cast？類型系統其實只是編譯器層面的東西，底層根本無所謂你的類型。所以只要內存布局一致，沒什麼不能cast的。反正解釋權在你。

static_cast需要經過編譯器檢查，只有互相能cast的，才不會在編譯的時候出錯。reinterpret_cast的行為標準沒定義，取決於編譯器。這裡用的其實是一個類型的指針到另一個類型的指針之間強轉。那都是合法的。

如果我的理解正確的話（或者說他有什麼特別的姿勢技巧我不知道），我認為這種寫法是不具有可移植性的，我也不清楚SGI STL是否在現在的編譯器下可以正常的工作，尤其是開啟O3這樣的高優化級別，他這樣強轉，我表示懷疑。這也不是標準C++應該有的做法，const_iterator是不能隱式轉為iterator的。除了SGI，GNU libstdc++, LLVM libc++都不是這樣實現的。libstdc++是取出const_iterator裡面的const pointer節點，然後用const_cast去除const，再做接下來的一系列操作，如：

template& void _Rb_tree&<_Key, _Val, _KeyOfValue, _Compare, _Alloc&>:: _M_erase_aux(const_iterator __position) { _Link_type __y = static_cast&<_Link_type&>(_Rb_tree_rebalance_for_erase (const_cast&<_Base_ptr&>(__position._M_node), this-&>_M_impl._M_header)); _M_drop_node(__y); --_M_impl._M_node_count; }

const_iterator也不能使用const_cast，這是丟不掉的，除非你告訴我這個const_iterator本身是const T*, 而iterator是T*，但是，_Rb_tree不是。

Meyers早年寫過一篇文章談過這個問題，他曾經提出過一個解法是使用advance來做，我記得應該是2000年左右，具體的文章我也已經找不到了，但是核心思想大概是這樣的：

iterator it(container.begin()); advance(it, distance&(it, ci));

也就是創建一個iterator，然後移動到const_iterator的位置。

SGI的實現已經不能代表現代的STL了，這個地方，如果你閱讀過MSVC的STL源碼，就會發現他會調用一個叫做checked/unchecked的函數，函數接受一個iterator/const_iterator，拿出裡面的指針，cast上/掉const specifier，然後返回一個新構造的const_iteratror/iterator

這是正確的做法，反正這層調用最後也會優化掉的

看到這個問題想起來我自己輪 set 時候遇到的問題 , 在這說說吧

實現 erase(const_iterator) 的問題 ...

在C++11之前還是 erase(iterator) , 自然是沒什麼困擾

C++11之後要 const_iterator ! 持有的是const指針 ...

不想用 reinterpret_cast 和 const_cast 怎麼辦呢 ???

困擾了一陣子之後 , 推翻重構 ...

抽象出來 標準節點(left + right + parent + color)

數據節點 繼承之(增加 value 欄位) ...

根節點 繼承標準節點 + 比較器 + 內存適配器(數據節點bind版) ...

容器本身持有的是個"包含根節點指針 , 同時繼承自內存適配器(根節點bind版)"的玩意

這樣 , iterator 和 const_iterator 持有的都是非 const 的指針 ...

over

這個C式的強制轉換...我也不知道是不是任何情況下都沒有問題。反正我實現的時候我也用了reinterpret_cast，功能是可以達到，這個暫時沒問題，通不通用還不知道。

static_cast肯定不行，這兩個struct不能隱式轉換。const_cast也不行，因為他們確實實例化出兩個不同的struct，而不是像 T* 和 const T* 的關係。那dynamic_cast更不行了，沒有繼承關係。

只能用reinterpret，相當於重新解釋一下，而且是用在引用（或指針），效果是可以達到的。具體跟C-style 強制轉換的不同細節之處，靜候其他大神回答(`●__●ˊ)/

大概看過sgi的實現。感覺上是行的。

雖然是不同的類型，但是兩個類型的內存排布是完全一致的，強轉後調用該類型的函數(主要就幾個操作符重載)也能夠成功。