Effective STL

【Effective STL（3）】关联容器

2018-03-05  本文已影响25人  downdemo

19 了解相等和等价的区别

!c.key_comp()(x, y) && !c.key_comp()(y, x) // 为true则xy等价

struct CIStringCompare : public binary_function<string, string, bool>
{ // 这个基类信息见item40
    bool operator()(const string& lhs, const string& rhs) const
    {
        return ciStringCompare(lhs, rhs);
    }
}

set<string, CIStringCompare> ciss; // case-insensitive string set
ciss.insert("Persephone"); // 添加到set中
ciss.insert("persephone"); // 未添加到set中

if (ciss.find("persephone") != ciss.end())... // true
if (find(ciss.begin(), ciss.end(), "persephone") != ciss.end())... // false

20 为指针的关联容器指定比较类型

set<string*> ssp; // set of string ptrs
ssp.insert(new string("Anteater"));
ssp.insert(new string("Wombat"));
ssp.insert(new string("Lemur"));
ssp.insert(new string("Penguin"));

// 希望看到“Anteater”，“Lemur”，“Penguin”，"Wombat"
for (set<string*>::const_iterator i = ssp.begin(); i != ssp.end(); ++i)
    cout << *i << endl;

set<string*, less<string*>, allocator<string*>> ssp;

struct StringPtrLess : public binary_function<const string*, const string*, bool>
{ // 这个基类信息见item40
    bool operator()(const string *ps1, const string *ps2) const
    {
        return *ps1 < *ps2;
    }
};

typedef set<string*, StringPtrLess> StringPtrSet;
StringPtrSet ssp;
for (StringPtrSet::const_iterator i = ssp.begin(); i != ssp.end(); ++i)
    cout << **i << endl;

void print(const string *ps)
{
    cout << *ps << endl;
}
for_each(ssp.begin(), ssp.end(), print); // 对ssp的每个元素上调用print

struct Dereference {
    template <typename T>
    const T& operator()(const T *ptr) const
    {
        return *ptr;
    }
};
// 通过解引用“转换”ssp中的每个元素，把结果写入cout
transform(ssp.begin(), ssp.end(), ostream_iterator<string>(cout, "\n"), Dereference());

struct DereferenceLess {
    template <typename PtrType>
    bool operator()(PtrType pT1, PtrType pT2) const
    {
        return *pT1 < *pT2;
    }
};

set<string*, DereferenceLess> ssp; // 行为就像set<string*, StringPtrLess>

21 永远让比较函数对相等的值返回false

set<int, less_equal<int> > s; // s以“<=”排序
s.insert(10);
s.insert(10);

!(10A <= 10B) && !(10B <= 10A)

// 对item20的StringPtrLess中的operator()结果取反实现StringPtrGreater
struct StringPtrGreater : public binary_function<const string*, const string*, bool> {
    bool operator()(const string *ps1, const string *ps2) const
    {
        return !(*ps1 < *ps2);
    }
};
// 这里取反返回的是>=而不是>，因此这是一个无效的比较函数
// 需要改为 return *ps2 < *ps1;

multiset<int, less_equal<int>> s; // s仍然以“<=”排序
s.insert(10);
s.insert(10);

22 避免原地修改set和multiset的键

// 一个雇员类
class Employee {
public:
    ...
    const string& name() const; // 获取雇员名
    void setName(const string& name); // 设置雇员名
    const string& getTitle() const; // 获取雇员头衔
    void setTitle(string& title); // 设置雇员头衔
    int idNumber() const; // 获取雇员ID号
    ...
};
// 以ID号来排序
struct IDNumberLess : public binary_function<Employee, Employee, bool> {
    bool operator()(const Employees lhs, const Employee& rhs) const
    {
        return lhs.idNumber() < rhs.idNumber();
    }
};
// 建立雇员类的set
typedef set<Employee, IDNumberLess> EmpIDSet;
EmpIDSet se; // se按ID号排序
// ID是主键不能修改，但对雇员的头衔做修改是合法的
// 而这种行为的合法则决定了set元素不能是const
Employee selectedID; // 容纳被选择雇员的ID号
...
EmpIDSet::iterator i = se.find(selectedID);
if (i != se.end())
{
    i->setTitle("Corporate Deity"); // 给雇员新头衔
}

EmpIDSet::iterator i = se.find(selectedID);
if (i != se.end()) {
    i->setTitle("Corporate Deity"); // 有些编译器不能通过，因为*i是const
}
// 为了编译通过使用const_cast
if (i != se.end()) {
   const_cast<Employee&>(*i).setTitle("Corporate Deity");
}
// static_cast不可行，因为修改的只是临时对象
if (i != se.end()) {
    static_cast<Employee>(*i).setTitle("Corporate Deity");
}
// 等价于
if (i != se.end()){
    Employee tempCopy(*i); // 把*i拷贝到tempCopy
    tempCopy.setTitle("Corporate Deity"); // 修改tempCopy
}

typedef set<Employee, IDNumberLess> EmpIDSet;
EmpIDSet se;
Employee selectedID;
...
EmpIDSet::iterator i = se.find(selectedID); // 第一步：找到要改变的元素
if (i!=se.end())
{
    Employee e(*i); // 第二步：拷贝元素
    se.erase(i++); // 第三步：删除元素，自增保持迭代器有效
    e.setTitle("Corporate Deity"); // 第四步：修改副本
    se.insert(i, e); // 第五步：插入新值，提示它的位置和原先元素的一样
}

23 考虑用有序vector代替关联容器

vector<Widget> vw;
... // 建立阶段
sort(vw.begin(), vw.end()); // 结束建立阶段，模拟multiset时用stable_sort，见item31
Widget w; // 用于查找的值的对象
... // 开始查找阶段
if (binary_search(vw.begin(), vw.end(), w))... // 通过binary_search查找
vector<Widget>::iterator i = lower_bound(vw.begin(), vw.end(), w); // 通过lower_bound查找
if (i != vw.end() && !(w < *i))...
pair<vector<Widget>::iterator, vector<Widget>::iterator> range =
    equal_range(vw.begin(), vw.end(), w); // 通过equal_range查找
if (range.first != range.second)...
... // 结束查找阶段，开始重组阶段
sort(vw.begin(), vw.end()); // 开始新的查找阶段...

typedef pair<string, int> Data;
class DataCompare { // 用于比较的类
public:
    bool operator()(const Data& lhs, const Data& rhs) const // 用于排序的比较函数
    {
        return keyLess(lhs.first, rhs.first);
    }
    bool operator()(const Data& Ihs, const Data::first_type& k) const // 用于查找的比较函数（形式1）
    {
        return keyLess(lhs.first, k);
    }
    bool operator()(const Data::first_type& k, const Data& rhs) const // 用于查找的比较函数（形式2）
    {
        return keyLessfk, rhs.first);
    }
private:
    bool keyLess(const Data::first_type& k1, const Data::first_type& k2) const // 真正的比较函数
    {
        return k1 < k2;
    }
};

vector<Data> vd; // 代替map<string, int>
... // 建立阶段
sort(vd.begin(), vd.end(), DataCompare()); // 结束建立阶段，模拟multimap时用stable_sort
string s; // 用于查找的值的对象
... // 开始查找阶段
if (binary_search(vd.begin(), vd.end(), s, DataCompare()))... // 通过binary_search查找
vector<Data>::iterator i = lower_bound(vd.begin(), vd.end(), s, DataCompare()); // 通过lower_bound查找
if (i != vd.end() && !DataCompare()(s, *i))...
pair<vector<Data>::iterator, vector<Data>::iterator> range =
    equal_range(vd.begin(), vd.end(), s, DataCompare()); // 通过equal_range查找
if (range.first != range.second)...
... // 结束查找阶段，开始重组阶段
sort(vd.begin(), vd.end(), DataCompare()); // 开始新的查找阶段...

24 当关乎效率时应该在map::operator[]和map-insert之间仔细选择

map<int, Widget> m;
m[1] = 1.50;
// 等价于
typedef map<int, Widget> IntWidgetMap;
pair<IntWidgetMap::iterator, bool> result = m.insert(IntWidgetMap::value_type(1, Widget())); 
result.first->second = 1.50;

m.insert(IntWidgetMap::value_type(1, 1.50));

m[k] = v; // 使用operator[]
m.insert(IntWidgetMap::value_type(k, v)).first->second = v; // 使用insert

template<typename MapType, typename KeyArgType, typename ValueArgtype>
typename MapType::iterator efficientAddOrUpdate
    (MapType& m, const KeyArgType& k, const ValueArgtype& v)
{
    typename MapType::iterator Ib = m.lower_bound(k);
    if(Ib != m.end() && !(m.key_comp()(k, Ib->first)))
    {
        Ib->second = v;
        return Ib;
    }
    else
    {
        typedef typename MapType::value_type MVT;
        return m.insert(Ib, MVT(k, v)); // 把pair(k, v)添加到m并返回指向新map元素的迭代器
    }
}

efficientAddOrUpdate(m, 10, 1.5);
// 如果m已经包含键是10的元素，推断出ValueArgType是double
// 函数体直接把1.5作为double赋给与10相关的那个Widget

25 熟悉非标准散列容器

上一篇 下一篇

猜你喜欢

热点阅读