本文主要是介绍Effective STL 23 Consider replacing associative container with sorted vector,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
If we choose an associative container, we’ll almost certainly be using a balanced binary tree. Such a tree would be made up of tree nodes. each holding not only a Widget, but also a pointer to the node’s left child, a pointer to its right child, and a pointer to its parent.
In contrast, there is no overhead when we store a Widget in a vector. The vector itself has overhead, of course, and there may be empty (reserved) space at the end of vector.
using a sorted vector instead of a set
vector<Widget> vw;// lots of insertions, few lookups
... // multiset, stable_sort
sort(vw.begin(), vw.end()); // object for value to look up
Widget w;
... // lookup via binary_search
if (binary_search(vw.begin(), vw.end(), w)...// lookup via lower_bound
vector<Widget>::iterator i = lower_bound(vw.begin(), vw.end(). w);
if (i != vw.end() && !(w < *i))...// lookup via equal_range
pair<vector<Widget>::iterator, vector<Widget>::iterator> range = equal_range(vw.begin(), vw.end(), w);
if(range.fist != range.second)... // start Recorganize phase
...
using a sorted vector instead of a map
typedef pair<string, int> Data;class DataCompare {
public:bool operator()(const Data& lhs, const Data& rhs) const {return keyLess(lhs.first, lhs.second);}bool operator()(const Data& lhs, const Data::first_type& k) const {return keyLess(lhs.first, k);}bool operator()(const Data::first_type& k, const Data& rhs) const {return keyLess(k, rhs.first);}
private:bool keyLess(const Data::first_type& k1, const Data::second_type& k2) const {return k1 < k2;}
};vector<Data> vd;
...
sort(vd.begin(), vd.end(), DataCompare());string s;
...
if (binary_search(vd,begin(), vd.end(), s, DataCompare())..// lookup via lower_bound
// !DataCompare(lhs, k)
// when it is true, we get i;
vector<Data>::iterator i = lower_bound(vd.begin(), vd.end(), s, DataCompare());
if (i != vd.end() && !DataCompare()(s, *i))...// lookup via equal_range
pair<vector<Data>::iterator, vector<Data>::iterator> range = equal_range(vb.begin(), vb.end(), s, DataCompare());
if (rang.first != rang.second) ...
这篇关于Effective STL 23 Consider replacing associative container with sorted vector的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!