地圖中的字符串如何存儲？

Question

當我保存一個字符串對象轉換成一個std ::地圖

std::map<std::string, SomeOtherData> map; 

如何字符串將被存儲在哪裏？我瞭解到std :: map經常以紅黑樹的形式實現，但是如何將字符串存儲在那裏呢？作爲trie？

Answer 1

如果你的意思是每個節點有一個字符的實現 - 答案是否定的，那麼每個節點都存儲std :: string，因此如果你打算使用std :: strings作爲鍵，你可以看看Ternary Trie （據我記憶，由Sedgewick提議）

Answer 2

你可以弄明白這一點。 *map.begin()爲您提供參考到第一個鍵值對。只要密鑰存在，該引用就不會失效，這意味着密鑰對象必須存在於內存中。特別是，這意味着你不能有一個（純的）特里實現，因爲特里沒有顯式地存儲關鍵對象。相反，一個trie存儲前綴。

（從理論上說，你可以有一個線索，仍然重複鍵存儲在每個節點這就是我所說的不純的線索。）