std::lower_bound()如果我将一对红黑树迭代器(set::iterator或map::iterator)传递给它,我总是假设以对数时间运行.std::lower_bound()在这种情况下,至少在libstdc ++实现中,我必须自己两次燃烧以注意在O(n)时间运行.据我所知,该标准没有红黑树迭代器的概念; std::lower_bound()将它们视为双向迭代器,advance并将它们视为线性时间.我仍然没有看到任何理由为什么实现无法为红黑树迭代器创建特定于实现的迭代器标记, 并且lower_bound()如果传入的迭代器恰好是红黑树迭代器则调用专用.
是否有任何技术原因std::lower_bound()不专门用于红黑树迭代器？
更新:是的,我知道查找成员函数,但它不是重点.(在模板化代码中,我可能无法访问容器或仅在容器的一部分上工作.)
赏金到期后:我发现Mehrdad和Yakk的答案最有说服力.我也无法决定; 我正在给予Mehrdad赏金并接受Yakk的回答.
我需要一个标准GCC STL地图容器的订单统计树.
我查了一下,有一些叫做PBDS的东西.基于策略的数据结构.这种用法对我来说也不清楚.
任何人都可以告诉我如何使用STL地图容器的订单统计树？即使它只在GNU G ++上足够吗？
给定一个空数组,我需要进行两种类型的查询
在数组中插入元素
找到一些元素k的索引(显然数组必须保持排序)
这可以使用set容器来完成
set<int> st;
set.insert(t);
这将插入我的元素O(log(n)).
并为第二个查询
set<int>::iterator it;
it = st.find(k);
idx = distance(st.begin(), it);
这需要O(n)时间.(O(n)[为distance()[+ O(log(n)[for set::find()]).
有没有办法在O(log(n))使用预定义的C++容器时进行这两个查询？
我们需要ADT具有搜索和排名功能.也就是说,除了STL map的接口外,还需要一个函数'int get_rank(key)'.
这种功能的标准实现需要在自平衡搜索树的每个节点中支持和更新额外的整数字段(例如,在黑红树中,在STL映射/集合中使用).但似乎,STL map/set不这样做.
我们正在寻找一种基于标准容器(STL,Boost)的解决方案,它具有最佳的时间复杂度:查找/添加/删除元素需要O(log n)(如在STL map/set中),通过a计算排名key也需要O(log n).
通过元素的等级,我们指的是元素在地图/集合的所有元素的排序序列中的位置.
例.set = {0,4,6,7,8} rank(0)= 1,rank(4)= 2,rank(6)= 3,rank(7)= 4,rank(8)= 5.
在我们看来,在上述时间复杂性约束下,问题不能通过两个映射的组合来解决,一个按键排序,另一个按排序排序.
谢谢.
我想在stl集合中查找元素的等级。我能够从头开始遍历该元素并找出其排名，但是这需要O（n）。有什么方法可以找到O（logn）中的排名。
如果我构建我自己的二叉树,那么我可以找到每个节点的深度.示例代码如下
template<class datatype>
void binary_node<datatype>::printNodeWithDepth(int currentNodeDepth)
{
if ( left )
left->printNodeWithDepth(currentNodeDepth+1);
std::cout << value << " and the depth is " << currentNodeDepth << std::endl;
if ( right)
right->printNodeWithDepth(currentNodeDepth+1);
}
但是想知道,因为map是b-tree,是否有可能为此写一些类似的东西std::map？