來自C++背景我錯過了一個很好的排序容器，它只是基於比較而不需要散列。基於比較的python中的排序容器

有沒有人知道平衡樹的良好實現？或者，（標準）庫中是否有另外一個已排序的容器，它同樣易於使用？

這是我現在嘗試解決的用例： A有一個描述帶有三角形表面的文件。每個三角形有三個節點，並且許多節點將相同。我需要重建這個表面，並且需要知道哪些節點是相同的。 不幸的是，在ASCII輸入中，即使它們屬於同一個節點，打印的浮點數之間有時也會有小的差異。所以我不能使用簡單的文本比較來查看它們是否相等。

在C++中，我的解決方案是使std :: map存儲具有'softcompare'的節點，如果它們之間的距離很小，則將節點視爲相等。然後，我可以在解析文件時添加節點並使用索引來構建曲面。

但是在Python中，我正努力以一種直截了當的方式高效地完成它。

感謝， 盧克

感謝所有爲你的貢獻！

對於goncalopp： 排序不是一個好的選擇，因爲它是每個插入的最壞情況O（n log（n））。 同樣適用於對分。它在搜索上很好，但不適用於插入。它在最壞的情況下維護一個不平衡的樹，它是O（n），然後在列表中的下一個插入是O（n）。

To Aaron： 我完全同意你的觀點，即編寫優雅的代碼。對我來說，選擇合適的容器（數據結構）往往是實現這一目標的第一步。 你的解決方案是O（n），它比平衡樹更快，非常好，我喜歡用round（）的技巧。我沒有想到，現在我意識到它可以在python中工作，因爲int的無限精度。所以我會和你一起去建設。

給MrE： 感謝鏈接到bintree，它看起來像我的問題（平衡樹）的解決方案。 我之前發現了blist，但是它使用內部字典和哈希值進行查找，所以這沒有奏效，但bintree看起來好多了。

來源

2013-09-27 Luke

https：// pypi。python.org/pypi/bintrees/也許 – YXD

你可以'排序'和['bisect']（http://docs.python.org/2/library/bisect.html） – goncalopp