stl中的map、set、multimap、multiset,兼谈OceanBase造*
程序员文章站
2024-01-06 15:07:58
...
终于有机会有动力有能力看jjhou的《STL源码解析》了。采取快速翻阅模式,有望看完整本。 map和set的底层机制都是RB-Tree(红黑树),插入和查找都是O(lgN)的复杂度。map、set以前听说过,但从来不用,因为不了解,不知道背后是什么。通过读这本书了解到了其
终于有机会有动力有能力看jjhou的《STL源码解析》了。采取快速翻阅模式,有望看完整本。
map和set的底层机制都是RB-Tree(红黑树),插入和查找都是O(lgN)的复杂度。map、set以前听说过,但从来不用,因为不了解,不知道背后是什么。通过读这本书了解到了其背后的机制,也许在将来会用一用。
multimap和multiset没什么,只是对map和set的小修改而已。
除了这些,还有hash_map、hash_set,其底层机制不是RB-Tree,而是hash table。
了解到这些之后,map、set这些,都不神秘,都可控了。
目前还有一点需要再动手捉摸下:内存管理。STL的simple_allocator可定制行到底如何,得看看。
关于stl使用,最好的参考书莫过于cplusplus.com了
再扯一句OceanBase与STL。
OceanBase中几乎没有使用任何stl提供的功能,基本是在重复“发明*”,不过这种发明某种程度上我觉得看上去是合理的,比如:返回码、错误码的定制,这一点就具有很大的灵活性;内存使用方面可定制性也大很多;另外,也轻量很多;再另外,STL的接口也用得蛮头疼,一大段代码,全围着接口转了,也有办法不围着,多用用typedef就会看上去好很多。为什么OceanBase不用STL呢?我想,本质原因还是我们有一群很牛逼的工程师,有能力写出经得起考验的底层代码。