随笔二

在C++ STL容器中的关系容器比较特殊,map,set,multimap,multiset等,他们有自己的排序算法, 并且只要向这些关系容器插入元素, 就好默认使用升序的排序算法.

示例

假设有作家: A, B, C, D每位作家各自拥有与其他作家不同数量的作品: it1, it2, t3, it4......

编写一段程序用来删除某个作家的所有作品.

现使用multimap容器将他们存储,假设作家,作品都是用string类型

#include<iostream>
#include<map>
using namespace std;

int main(){
    multimap<string,string>data;
    //为了方便,此处用pair数组初始化 A B C 三位作家
    pair arrA[]={{"A","it1"},{"A","it2"},{"A","it3"},{"A","it4"}};
    pair arrB[]={{"B","it1"},{"B","it2"},{"B","it3"},{"B","it4"}};
    pair arrC[]={{"C","it1"},{"C","it2"},{"C","it3"},{"C","it4"}};
    //...
    while(data.find("A")!=data.end()){
        data.erase(data.find("A"));
    }
    return 0;
}

multimap::find()函数每次只能查到第一个给定关键字的元素,这个程序做的是,查到一次删一次,长度不大还好,若是在庞大的数据量下,这个程序的性能就太慢了.

为此,我们可以使用multimap::equal_range(),该成员函数返回的是一个范围,要知道STL里的范围都是左闭右开的 : [ first_value, last_of_the_end_value)左边界是指该范围的第一个元素,右边界是指闭合区间右边界的下一个元素.

这个范围STL使用了 lower_bound 和upper_bound 表示,这两个变量是一个pair值,pair由equal_range返回,而且lower_bound单独也是一个pair值,本质是一个指向左边界的迭代器,其first成员为该迭代器指向元素的键值,而second成员为键值关联的值. 同理,upper_bound是指向闭合区间右边界元素的后一个元素. 当lower_bound 与 upper_bound 相等时,表示为空区间. 既没有该键值所关联的值.

知道了这些,我们可以先找到与给定键值相等的键值区域,然后使用 erase ( )的迭代器版本,一次性删除该键值相关联的值.

所以比较高效率的程序可以改写为:

#include<iostream>
#include<map>
using namespace std;

void remove_author(multimap<string,string>&books,const string &author){
    auto pos = books.equal_range(author);
	if(pos.first==pos.second)
        cout<<"没有 "<<author<<" 该键值关联的值"<<endl;
    else
        books.erase(pos.first,pos.second);
}

int main(){
    multimap<string,string>data;
    //为了方便,此处用pair数组初始化 A B C 三位作家
    pair arrA[]={{"A","it1"},{"A","it2"},{"A","it3"},{"A","it4"}};
    pair arrB[]={{"B","it1"},{"B","it2"},{"B","it3"},{"B","it4"}};
    pair arrC[]={{"C","it1"},{"C","it2"},{"C","it3"},{"C","it4"}};
    //...
  
    return 0;
}