红色的黑色树与编排

由于大多数人都知道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中的信息。 –

红色的黑色树与编排

回答

相关问题