是否有一個sorted_vector類，它支持insert（）等？

通常，它是更有效地使用排序的std::vector而不是std::set。有誰知道一個庫類sorted_vector，基本上也有類似的接口std::set，但插入元素融入到有序vector（這樣有沒有重複），採用二進制搜索find元素等？是否有一個sorted_vector類，它支持insert（）等？

我知道這並不難寫，但可能最好不要浪費時間，反正使用現有的實現。

更新：，而不是使用一組排序向量的原因是：如果你有幾十萬只包含10個左右的每個成員的小集合，它是更多的內存效率只使用排序向量代替。

來源

2010-04-25 Frank

你可能會更具體瞭解std :: set的效率不夠高嗎？ – KillianDS 2010-04-25 22:28:54

如果您擁有數十萬個僅包含10個左右成員的小集，那麼只需使用排序向量就可以提高內存效率。 – Frank 2010-04-25 22:31:47

我不認爲這是一個現成的課程。你可以編寫自己的代碼，或者使用'lower_bound（）'來插入，''binary_search（）'用於查找。 – doublep 2010-04-25 22:36:45

我覺得有沒有「排序容器」適配器在STL是因爲已經保持事物的相應關聯容器排序，以在使用幾乎所有的情況下，這將是適當的。說實話，關於排除vector<>容器的問題，我能想到的唯一理由就是可以與需要排序數組的C函數進行交互操作。當然，我可能會錯過一些東西。

如果你覺得一個排序vector<>會更適合您的需求（意識到插入元素向量的缺點），這裏的代碼項目的實施：

An STL compliant sorted vector By Martin Holzherr

我從來沒有使用它，所以我不能擔保它（或其許可證 - 如果有任何指定）。但是快速閱讀這篇文章，看起來作者至少爲容器適配器提供了一個合適的STL接口。

這似乎是值得細看。

來源

2010-04-25 22:45:25

排序後的向量可能會更快，直到該集合相當大（100個元素）。集具有*可怕*緩存局部性。 – 2018-01-10 10:19:52

之所以這樣的容器是不標準庫的一部分是，這將是低效的。使用矢量存儲意味着如果在矢量的中間插入了某些東西，則必須移動對象。在上執行此操作時，每個插入會變得不必要的昂貴。（平均而言，一半的對象將具有移動來進行各插入。這是相當昂貴）

如果你想有一個排序的載體，它很可能更好地插入的所有元素，然後調用std::sort()一次，後插入。

來源

2010-04-25 23:09:07 jalf

因此，更新C++ 0x移動語義的排序向量類。 – 2010-04-26 00:01:03

我看不出如何解決問題。即使只是一個指針交換，所有的對象仍然必須被觸及。你仍然試圖做一些數據結構不適合的東西。 – jalf 2010-04-26 01:41:53

我開始寫這樣的答案，並停下來，因爲它不是真的。對於少數幾個元素來說，這實際上很常見，平均移動一半可能比執行分配和樹重新平衡更便宜。當然，最好一次調用'sort'，我個人不會尋找一個容器來做到這一點，但這是一個風格問題。 – Potatoswatter 2010-04-26 03:06:35

Alexandresu的Loki有一個排序的向量實現，如果你不想通過滾動你自己的相關性瑣碎的努力。

http://loki-lib.sourceforge.net/html/a00025.html

來源

2010-04-25 23:13:04

嗯，這一個：http：//loki-lib.sourceforge.net/html/a00025.html。謝謝！ – Frank 2010-04-26 00:31:41

如果您決定推出自己的，你可能也想看看升壓：uBLAS庫。具體做法是：

#include <boost/numeric/ublas/vector_sparse.hpp>

，並期待在coordinate_vector，它實現值和索引的向量。這個數據結構支持O（1）插入（違反排序），但隨後按需要Omega（n log n）排序。當然，一旦排序，查找就是O（logn）。如果數組的一部分進行了排序，算法會識別這個並僅對新添加的元素進行排序，然後進行就地合併。如果你關心效率，這可能是你能做的最好的。

來源

2010-04-26 02:08:52

Boost.Container flat_set

Boost.Container flat_ [多]地圖/組容器有序向量基於基於Austern的和Alexandrescu的的準則關聯容器。這些有序的矢量容器最近也受益於向C++添加移動語義，大大加速了插入和刪除時間。平關聯容器具有以下屬性：

更快的查找比標準關聯容器比標準關聯容器

快得多迭代。

更少的內存消耗小物體（以及如果使用shrink_to_fit大對象）

改進高速緩存性能（數據存儲在連續的存儲器）

非穩定的迭代器（插入和擦除元素時的迭代器被無效）

不可複製和不可移動的值類型不能被存儲

比標準關聯容器

較慢插入和擦除比（複製/移動的構造可以在移位擦除值和插入時拋出）較弱異常安全標準聯想容器（專門爲不可移動型）

Live demo：

#include <boost/container/flat_set.hpp> 
#include <iostream> 
#include <ostream> 

using namespace std; 

int main() 
{ 
    boost::container::flat_set<int> s; 
    s.insert(1); 
    s.insert(2); 
    s.insert(3); 
    cout << (s.find(1)!=s.end()) << endl; 
    cout << (s.find(4)!=s.end()) << endl; 
}

jalf：如果你想有一個排序的載體，它很可能更好地插入的所有元素，然後在插入後調用std :: sort（）一次。

boost::flat_set可以做到這一點自動：

template<typename InputIterator> 
flat_set(InputIterator first, InputIterator last, 
     const Compare & comp = Compare(), 
     const allocator_type & a = allocator_type());

影響：構造使用指定的比較對象和分配器空集，並從範圍[插入元件第一，最後一個）。

複雜： - 第一線性的N如果範圍[第一，最後一個）是利用補償否則N *日誌（N），其中N是最後已排序。

來源

2012-10-28 00:23:55

Here是我已經在生產代碼中使用了多年的sorted_vector類。它有重載讓你使用自定義謂詞。我已經將它用於指針的容器，這在很多用例中都是非常好的解決方案。

來源

2015-06-18 03:56:38 moodboom

是否有一個sorted_vector類，它支持insert（）等？

回答

相關問題