如何有效地將一系列連續整數插入到std :: set中？

在C++中，我有一個std :: set，我想插入一系列連續的整數。我怎麼能有效地做到這一點，希望在O（n）時間，其中n是範圍的長度？如何有效地將一系列連續整數插入到std :: set中？

我想我會使用inputIterator版本的std :: insert，但我不清楚如何構建輸入迭代器。

std::set<int> mySet; 

// Insert [34 - 75): 
mySet.insert(inputIteratorTo34, inputIteratorTo75);

如何創建輸入迭代器，並將這是範圍大小的O（n）？

來源

2013-08-18 WilliamKF

如果這是問題的唯一部分，那麼我建議實施一個鏈表...'O（1）推''N'推='O（n）'。 –

以優化PROGRAMM由aksham提供的線索，我看到的答案是：

#include <boost/iterator/counting_iterator.hpp> 

std::set<int> mySet; 

// Insert [34 - 75): 
mySet.insert(boost::counting_iterator<int>(34), 
      boost::counting_iterator<int>(75));

來源

2013-08-18 05:09:15 WilliamKF

將已經排序的元素插入到一個集合中的有效方式是提示庫以確定下一個元素將在哪裏。對於您要使用的insert的版本，它使用一個迭代：

std::set<int>::iterator it = mySet.end(); 
for (int x : input) { 
    it = mySet.insert(it, x); 
}

在另一方面，你可能要考慮其他容器。只要有可能，請使用std::vector。如果與查找相比插入量較小，或者如果所有插入事件都是預先發生的，那麼您可以構建一個向量，對其進行排序並使用lower_bound進行查找。在這種情況下，由於輸入已經排序，所以可以跳過排序。

如果插入（或移除）發生在整個地方，您可能需要考慮使用std::unordered_set<int>，其中插入（每個元素）的平均值爲O(1)，並且查找成本。

對於一組，所有這些都是小的（34〜75小號碼），也可以考慮使用位集或bool甚至一個普通數組跟蹤小數目的特定情況下，在其中設置的元件，以true插入時。或者將有O(n)插入（所有元素）和O(1)查找（每個查找），這比該集合更好。

來源

2013-08-18 03:22:11

我以爲我看到一些關聯容器verbage，如果數據已經排序，它將是線性的。但是，這可能在'set'構造函數中，而不是'insert'中。 – Yakk

目前還不清楚爲什麼你特別想使用迭代器來插入來指定範圍。

但是，我相信你可以使用一個簡單的for循環來插入所需的O（n）複雜性。

從cppreference的頁面上的std ::集引用，複雜度是：

如果N個元素被插入，NLOG在大小（size + N）一般，但線性+ N，如果內容已經按照容器使用的相同排序標準進行排序。

所以，用一個for循環：

std::set<int> mySet; 
for(int i = 34; i < 75; ++i) 
    mySet.insert(i);

來源

2013-08-18 03:25:50 maditya

升壓方式可以是：

std::set<int> numbers(
boost::counting_iterator<int>(0), 
boost::counting_iterator<int>(10));

一個偉大的LINK其他的答案，特別@摩尼的答案

來源

2013-08-18 03:26:11 Saksham

std :: set是二叉搜索樹的一種，這意味着平均插入成本O（lgn），

C++ 98：如果N個元素被插入，NLOG（大小+ N）一般，但在大小線性 + N如果元件根據由容器所使用的相同排序準則已排序。

C++ 11：如果插入了N個元素，則Nlog（size + N）。如果範圍已經排序，則實現可能會優化。

我認爲C++ 98實現將跟蹤當前的插入節點，並檢查下一個要插入的值是否大於當前值，在這種情況下，不需要再次從根啓動。

在C++ 11

，這是一個可選的優化，因此可能實現skiplist結構中，並在使用該範圍內嵌feture實現，或者可以根據你的場景

來源

2013-08-18 03:27:27

如何有效地將一系列連續整數插入到std :: set中？

回答

相關問題