std :: set begin（）和std :: set O（logn）中的迭代器之間的距離

我需要在std :: set中找到一個元素的索引。這個索引可以被視爲迭代器從頭開始的距離。單程可以是：std :: set begin（）和std :: set O（logn）中的迭代器之間的距離

for(int i = 0, set<int>::iterator it = s.begin(); it != iteratorToBeFound; ++it, ++i);

這顯然需要O（n）時間。但是我們知道在O（log n）時間內可以找到由內部集合實現的二叉搜索樹中根的距離。

是他們的任何方式來實現相同的查找索引在O（log n）時間在C++集？

來源

2012-09-21 divanshu

爲什麼你需要的索引？ – paulm

您確定可以在二叉搜索樹中的'O（log n）'時間中找到距離嗎？ 'set'通常是一棵紅黑樹，在每個節點上沒有很多關於左右子樹分別有多少元素的信息。請記住，您不是直接從根目錄查找距離，而是在查找葉子左側的葉子總數。 –

@SteveJessop：哦，所以他們沒有辦法計算R-B樹中O（logn）的索引嗎？ – divanshu

您可以使用排序std::vector<int> 。如果它已排序，則可以在O(log n)中查找元素。你可以在固定時間內找到距離O(1)。

排序向量我的意思是每次插入後（或多個插入後）你做std::sort(v.begin(), v.end());

如果裏面std::set<T>你的類型是不是像int光 - 你可以保留兩個 - std::set<T>和分類迭代std::vector<std::set<T>::iterator>的矢量。但是要讓這些結構保持同步並不是微不足道的。也許你可以添加一些像位置到T？或者保留std::set<std::pair<T,int>, comp_first_of_pair<T>>其中comp_first_of_pair只是有set排序只有T和第二個int是爲了保持位置？

只是一些想法 - 有甚至O(1)距離時間...

來源

2012-09-21 15:50:53 PiotrNycz

但是，在每次插入std :: vector後進行排序會花費我O（nlogn）。優勢在哪裏？ – divanshu

1）只能在一系列連續插入後排序。 2）在'std :: set <>中插入的代價是'O（log n）' - n個插入：'O（n Log n）'。 3）也許你'插入'一次 - 但測試距離多次.... – PiotrNycz

謝謝@PiotrNycz :) – divanshu

您可以使用函數std::set<>::find來搜索元素x並計算distance爲該集合的第一個迭代器。

std::distance(s.begin(), s.find(x))

但是，由於註釋表明距離的運行時間取決於所用迭代器的類型。在集合的情況下，這是一個雙向迭代器，距離爲O（n）。

來源

2012-09-21 12:02:37 Danvil

雖然這是'O（log n + m）'。但是，你可以做的最好的，AFAIK。 – Xeo

但是[std :: distance]（http://en.cppreference.com/w/cpp/iterator/distance）在這裏是O（N）。 – juanchopanza

我知道關於std :: distance，但是它的實現方式與寫在問題中的方式相同，並且絕對是O（n）。 – divanshu

你不能使用具有雙向迭代器的基質。所以唯一可以接受的方法就是自己來算（多少個int小於你插入到的set中）。

但是，如果你已經清楚分開的「數據採集」和「數據使用」階段 - 也許這是值得更換的std ::與排序的std ::矢量設置。它難以維持，但有自己的優勢，其中包括迭代matematics（這樣你就可以得到O（log n）的與的std :: binary_search和帶O的距離搜索（1））

來源

2012-09-21 12:12:45 PSIAlt

如果計算索引是真的您的瓶頸，然後我看到2個選項：

存儲索引。無論是在節點本身還是在單獨的std::map。當然這意味着你必須保持這個緩存更新。
使用std::vector。這並不像它看起來那麼糟糕。如果你保持向量總是排序，你可以使用它像set。性能將類似於set。最大的缺點是：節點可能會被複制很多。（這可以通過使用指針來補償，boost:shared_ptr或std::unique_ptr [C++ 11只]）
要查找使用std::lower_bound的元件。
而不是插入/ push_back你：insert(lower_bound(b,e,x), x)

來源

2012-09-25 07:37:22 rtlgrmpf

std :: set begin（）和std :: set O（logn）中的迭代器之間的距離

回答

相關問題