Effective STL 23 Consider replacing associative container with sorted vector

本文主要是介绍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) ...