[求助]stl 使用过程中的问题 - 编程论坛

#2

aipb20072007-07-02 18:25

应该不是吧
因为关联容器的迭代器是不允许算术运算的。

要2分，就要满足能够快速定位。

但是也不一定，我的想法是建立在以迭代器操作的基础上。

#3

lb5212002002007-07-02 20:34

回复：（aipb2007）应该不是吧因为关联容器的迭代器是...

很多论坛上都说map和set实现了二分查找啊

#4

leeco2007-07-05 01:33

二分查找是一个逻辑上的算法，并不是一个具体实现。
（在大多STL的实现中）map和set使用了红黑树作为存储结构，find之所以能有logn的高效不在于它的算法多么巧妙，而在于map和set的存储结构使得逻辑上的二分查找很自然的容易实现。

PS：红黑树是一种特殊的BST,BST（二分搜索树）顾名思义的实现的二分搜索。

#5

HJin2007-07-05 04:46

以下是引用leeco在2007-7-5 1:33:12的发言：
二分查找是一个逻辑上的算法，并不是一个具体实现。
（在大多STL的实现中）map和set使用了红黑树作为存储结构，find之所以能有logn的高效不在于它的算法多么巧妙，而在于map和set的存储结构使得逻辑上的二分查找很自然的容易实现。

PS：红黑树是一种特殊的BST,BST（二分搜索树）顾名思义的实现的二分搜索。

very good answer. There is an internal tree data structure used by map and set --- for a tree, look-up is guarantteed to be O(h), where h is the height of tree.

RB tree and other kinds of tree make the tree balanced so that the height h = n lgn.