紅色的黑色樹與編排

由於大多數人都知道C++中的Set Container通常是以紅黑樹的形式實現的，並且在容器上迭代時條目會按順序出現，這可以被利用。紅色的黑色樹與編排

我卻想去做pagenation在容器的迭代，操作性的例子，如果容器containes：

set<int> set; 
// insert some data 
for(auto s : set) 
    cout << s << " " << endl; 

1, 3, 5, 7, 9, 11, 13, 15

我想杜在容器range(2,5) yealding範圍查詢：矢量3, 5, 7，這似乎不可能做的設置，是否有可能做任何STL容器分頁，或者這是你必須實現它自己的情況？

來源

2013-12-09 Martin Kristiansen

好了，現在我明白你的問題（我認爲），將['STD：next'（HTTP：/ /en.cppreference.com/w/cpp/iterator/next）和/或['std :: advance']（http://en.cppreference.com/w/cpp/iterator/advance）基於'std：：開始（s）'提供給你你正在尋找的東西？我*想*可能。 – WhozCraig

我懷疑你會找到一種方法來做到這一點在標準庫中的線性時間少，但它並不難實現自己。 – Dukeling

索引，只有一個辦法http://www.cplusplus.com/reference/iterator/advance/ 但它具有線性時間複雜度

set<int>::iterator lower = s.begin(); 
std::advance(lower, 2); 
auto upper = lower; 
std::advance(upper, 6-2); 
std::copy(lower, upper, std::ostream_iterator<int>(std::cout, " "));

來源

2013-12-09 04:04:50 weisert

是的，我去了那裏。他正在通過索引位置尋找範圍;不是元素值。 – WhozCraig

是的，我更正了答案 – weisert

然而這在先前的參數中仍然是線性的，這應該在日誌時間內可行，但是可能需要不保存在基礎rb_tree中的信息。 –

紅色的黑色樹與編排

回答

相關問題