标准关联容器一定比vector的查找速度快吗？

用户9831583

发布于 2022-12-04 16:21:57

1.8K0

发布于 2022-12-04 16:21:57

vector和string

条款13：尽量使用vector和string来代替动态分配得数组

/** * @brief * 使用 new 进行动态分配，你要时刻注意以下几点 * * 1，确保 new delete成对出现 * 2，分配数组时，必须要使用 delet[] * * 而使用 vector或string销毁时，他的析构函数会自动销毁容器中的元素，回收存放那些元素的内存 * */

//https://blog.csdn.net/qls315/article/details/106759358

//https://www.cnblogs.com/33debug/p/6661774.html

//https://blog.csdn.net/u012501459/article/details/48229399

/*** * 为什么要引用计数？ * * 1，实际上是一种用对象来管理资源的方式，因为普通的栈上的对象在离开作用域时会调用对应的析构函数 * 根据这个特性，可以实现用于对指针进行管理的类，不要显式调用 delete ，就可以释放 new * * 2，引用计数可以使许多等值对象共享同一个值，如果许多对象拥有相同的值，那么存储多次是一种资源浪费 *

class RcString {
public:
    RcString(const char* value = "");
    RcString(const RcString& rhs);
    ~RcString();
    RcString& operator=(const RcString& rhs);
 
    char* get() {
        return _data->_data_ref;
    }
 
private:
    struct StringValue {
        StringValue(const char* value);
        ~StringValue();
        char* _data_ref;
        int _refcount;
    };
    StringValue* _data;
};
 

 RcString::RcString(const char *value) : _data(new StringValue(value)){
 
}
 
RcString::RcString(const RcString &rhs) : _data(rhs._data) {
    ++_data->_refcount;
}
 
RcString & RcString::operator=(const RcString &rhs) {
    if (_data == rhs._data) return *this;
 
    if (--_data->_refcount == 0) delete _data;
    _data = rhs._data;
    ++_data->_refcount;
    return *this;
}
 
RcString::~RcString() {
    if (--_data->_refcount == 0) {
        delete _data;
    }
}
 
RcString::StringValue::StringValue(const char *value) : _refcount(1) {
    _data_ref = new char[strlen(value) + 1];
    strcpy(_data_ref, value);
}
 
RcString::StringValue::~StringValue() {
    delete [] _data_ref;
}

const char& operator[](int index) const {
    return _data->_data_ref[index];
}

char & RcString::operator[](int index) {
if (_data->_refcount > 1) {
    --_data->_refcount;
    _data = new StringValue(_data->_data_ref);
}

return _data->_data_ref[index];

条款14：使用 reserve来避免不必要的重新分配

/** STL容器可以自动增长到足以容纳你放进去的数据，在最大大小范围之内 vector和string利用 realloc等价的思想进行空间增长： 1，分配新的内存块，是容器目前容量的几倍，每次以 2 为因数增长 2，把所有元素从容器的旧内存拷贝到它的新内存 3，销毁旧内存中的对象 4，回收旧内存首先介绍以下四个让人困惑的函数： 1，size() 容器中有多少个元素，并没有告诉你容器为它容纳的元素分配了多少内存 2，capacity() 指出容器在它已经分配的内存中可以容纳多少元素，利用 capacity() - size() 得到有多少没有被占用的内存 3，resize() 强制把容器改为容纳 n 个元素，此时 size()返回 n，如果 n 小于当前大小，容器尾部的元素会被销毁；n 大于当前大小，新默认构造的元素会添加到尾部；n大于当前容量，在元素加入之前会发生重新分配 4，reserve() 强制容器把它的容量改为至少 n，提供的n不小于当前大小，强迫进行一次重新分配，增加容量因此，可以得知 reserve 允许你最小化必须进行的重新分配的次数，避免真分配的开销和迭代器/指针/引用的失效 */

std::vector<int> value;
for(int i =1; i <= 1000; ++i)
{
    value.push_back(i);
    //会导致 2 到 10次重新分配 1000约等于 2^10
}

//如果改为
std::vector<int> value;
value.reserve(1000);
for(int i =1; i <= 1000; ++i)
{
    value.push_back(i);
    //不会重新分配
}

//reserve的使用的两种场合 //1，当你确切或者大约知道有多少元素将最后出现在容器中。那样的话，就像上面的vector代码，你只是提前reserve适当数量的空间。 //2，保留你可能需要的最大的空间，然后，一旦你添加完全部数据，修整掉任何多余的容量

条款15：使用“交换技巧”减小过剩容量

int main()
{   
    //保证减少 vector的大小的同时，也减少它的容量，避免vector持有不再需要的内存
    std::string s = "lyy10";

    std::vector<int> a = {1,2,3};

    std::cout<<"before: "<<s<<std::endl;

    std::vector<int> b = {1,2};

    std::vector<int>(b).swap(a);

    for (auto i:a)
    {
        std::cout<<"i: "<<i<<std::endl;
    }
    
    std::string().swap(s);//清除s并且最小化它的容量

    std::cout<<"after: "<<s<<std::endl;
    //避免使用 std::vector<bool> 这是不存在的
}

关联容器

条款16：了解相等和等价的区别

/** 应用： 1，find查找第一个有特定值的对象的位置：定义的是相等基于 operator== 2，set::insert插入时会判断那个元素的值是否已经在set中了 : 定义是等价基于 operator< */
//1，operator== // 比如 x==y 是 tr，x与y有相等的值，但不意味着所有它们的成员有相等的值，比如 //实现1

//实现1
class Widget{
    public:
        int value;
    private:
        float lastvalue;
};

 bool operator==(const Widget& lhs, const Widget& rhs){
           return lhs.value == rhs.value;
        }

//实现2
class Widget_{
    public:
        int value;
        Widget_(int v)
        {
            this->value = v;
        }
        bool operator==(const Widget_& w)
        {
            return this->value == w.value;
        }
        bool operator< (const Widget_& w) const
        {
            return this->value < w.value;
        }
    private:
        float lastvalue;
};
//因此上面两个 Widget 即使它们的 lastValue不同也可以有相等的值

   //1 operator==
    //实现1
    Widget w1,w2;
    w1.value = 10;
    w2.value = 10;
    if(w1 == w2)
    {
        std::cout<<"w1 == w2"<<std::endl;
    }
    else
    {
        std::cout<<"w1 != w2"<<std::endl;
    }

    //实现2
    Widget_ w1_(9),w2_(20);
    if(w1_ == w2_)
    {
        std::cout<<"w1_ == w2_"<<std::endl;
    }
    else
    {
        std::cout<<"w1_ != w2_"<<std::endl;
    }

//2，operato< //等价一般应用在标准关联容器中，比如 set，multiset，map，multimap，在排序中有意义 //基于在一个有序区间中对象值得相对位置，x和y没有哪个排在另一个之前，则等价

//https://vimsky.com/examples/usage/cpp-set-key_comp-function-01.html

//每个标准关联容器可以通过它得 key_comp成员函数来访问排序判断式，如果以下为真，两个对象 x和y关于一个关联容器c得排序标准有等价得值

 if(!c.key_comp()(x,y) && !c.key_comp()(y,x))

 {

 }

//如果第一个参数根据较窄的弱顺序在第二个参数之前，则返回 true，否则返回 false

  //2 operator< 或者 less
    std::set<Widget_> s;
    s.insert(w1_);
    s.insert(w2_);
    std::cout<<"size: "<<s.size()<<std::endl;

    std::cout<<"key_comp: "<<s.key_comp()(w1_,w2_)<<std::endl;

//3 //实现一个忽略大小写的 set

int ciStringCompare(const std::string& s1, const std::string& s2)
{
    return strcmp(s1.c_str(),s2.c_str());
}
////https://cloud.tencent.com/developer/section/1012725
//binary_function是一个基类，用于创建带有两个参数的函数对象, 没有定义operator()，所以派生类要定义这个
struct CISTringCompare: public std::binary_function<std::string,std::string,bool>{
            bool operator()(const std::string& lhs, const std::string& rhs) const{
                return ciStringCompare(lhs,rhs);
            }
        };

////https://cloud.tencent.com/developer/section/1012725 //binary_function是一个基类，用于创建带有两个参数的函数对象, 没有定义operator()，所以派生类要定义这个

//因此，标准关联容器是基于等价而不是相等，所以每个容器必须有一个定义了怎么保持东西有序的比较函数默认 less

 //3
    std::set<std::string, CISTringCompare> ciss;
    ciss.insert("STL");
    ciss.insert("stl");
    for(auto i:ciss)
    {
        std::cout<<"i: "<<i<<std::endl;
    }
    //此时：使用set的find成员函数搜索 stl 会成功
    if(ciss.find("stl") != ciss.end()) //比较仿函数 CIStringCompare
    {
        std::cout<<"set.find OK"<<std::endl; 
    }
    else
    {
         std::cout<<"set.find failed"<<std::endl; // dui
    }
    //但是，使用非成员的 find算法，就会失败
    //https://blog.csdn.net/fengliezhe/article/details/46399125
    if(std::find(ciss.begin(), ciss.end(),"stl") != ciss.end())//string("stl") != string("STL")
    {
         std::cout<<"std::find OK"<<std::endl; //dui
    }
    else
    {
         std::cout<<"std::find failed"<<std::endl;
    }
    //因此，也可以规定优先选择成员函数，而不是非成员函数

    std::set<std::string> ciss_;
    ciss_.insert("STL");
    ciss_.insert("stl");
    std::cout<<"ciss: "<<ciss.size()<<" ciss_ "<<ciss_.size()<<std::endl;

    for(auto i:ciss_)
    {
        std::cout<<"i: "<<i<<std::endl;
    }
    if(ciss_.find("stl") != ciss_.end())
    {
        std::cout<<"set.find OK"<<std::endl; 
    }
    else
    {
         std::cout<<"set.find failed"<<std::endl;
    }
    if(std::find(ciss_.begin(), ciss_.end(),"stl") != ciss_.end())
    {
         std::cout<<"std::find OK"<<std::endl;
    }
    else
    {
         std::cout<<"std::find failed"<<std::endl;
    }

w1 == w2 w1_ != w2_ size: 2 key_comp: 1 i: stl i: STL set.find failed std::find OK ciss: 2 ciss_ 2 i: STL i: stl set.find OK std::find OK

条款17：为指针的关联容器指定比较类型

    //1：假定 string*的指针set
    std::set<std::string*> ssp;
    ssp.insert(new std::string("aa"));
    ssp.insert(new std::string("bb"));
    //写出如下打印
    for(std::set<std::string*>::const_iterator i = ssp.begin(); i != ssp.end(); ++i)
    {
        std::cout<<"1: "<<*i<<std::endl;//你希望看到 aa bb; 但是出来的却是 十六进制的数
        //因为 set容纳的是指针，*i不是一个string，它是一个string的指针
        //因此，避免自己写循环！！！
    }

//调用 copy 算法，将 ssp中的字符串拷贝到 cout

    std::copy(ssp.begin(),ssp.end(),std::ostream_iterator<std::string>(std::cout,"\n"));

//无法通过编译，因为当你告诉 ostream_iterator一个std::string时，编译器检测到那和ssp中存储的对象类型 string* 之间不匹配，拒绝编译

//将循环中 * 改成 ** 可能输出你想要的结果，也可能不是，因为它是按照指针的值进行排序，而不是 string的值排序

//为什么会出现以上问题？

//开篇第一句话相当于如下

    std::set<std::string*, std::less<std::string*>,std::allocator<std::string*> > ssp_;

//而：如果你想要string* 指针以字符串值确定顺序被存储在 std::set中，不能使用默认比较仿函数 std::lessstd::string*

//必须改为你自己的比较仿函数类，它的对象带有std::string*指针并按照指向的字符串值进行排序，见 2

//2
struct StringPtrLess:public std::binary_function<const std::string*,const std::string*,bool>{
    bool operator()(const std::string *ps1, const std::string *ps2) const{
        return *ps1 < *ps2;
    }
};
//2
typedef std::set<std::string*, StringPtrLess> stringPtrSet;
stringPtrSet sssp;//按照StringPtrLess定义的顺序进行排序
sssp.insert(new std::string("aa"));
sssp.insert(new std::string("bb"));
sssp.insert(new std::string("cc"));
sssp.insert(new std::string("dd"));

//打印1： 如你想要的结果
for(stringPtrSet::const_iterator i = sssp.begin(); i != sssp.end(); ++i)
{
std::cout<<"2: "<<**i<<std::endl;
}

//打印2：需要知道怎么在打印 string* 之前对它们解引用，然后后for_each联用见 3

//3
//解引用，将ps指向的对象打印到cout
void print(const std::string *ps)
{
    std::cout<<*ps<<std::endl;
}
 for_each(sssp.begin(),sssp.end(),print);

//打印3：写出泛型的解引用仿函数类，并与 transform和ostream_iterator联用, 见 4

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

//因此，可以得出

//1，算法替代循环

//2，指针的标准关联容器，容器是以指针的值进行排序的，而不是你想要的，所以你需要建立自己的仿函数类作为比较类型

//或许你有这样的疑问？

//为什么必须创造一个仿函数类而不是简单地为set写一个比较函数，你可能想这样试试见 5

//5
bool stringPtrLessSS(const std::string* ps1, const std::string* ps2)
{
    return *ps1 < *ps2;
}

    //你想这样
  //  std::set<std::string*,stringPtrLessSS> sssssp;//假设使用stringPtrLessSS作为比较函数，这都不能编译！！！！！！
    //因为第二个参数必须是一个类型，不能是一个函数

//因此，无论何时 //建立指针关联容器，需要指定容器地比较类型，做好是一个永远比较地仿函数模板见 6

//6
struct DereferenceLess{
    template <typename PtrType>
    bool operator()(PtrType pT1, PtrType pT2) const{
        //参数是按值传递地，我们希望它们是指针
        return *pT1 < *pT2;
    }
};
   // 6 的模板消除了 使用 2中的类的写法，可以改成如下：
   std::set<std::string*, DereferenceLess> ssssssssp;
   //等价于
   std::set<std::string*,StringPtrLess> sssssssp;

//结论：

//指针的关联容器，或者表现为指针的对象的容器，例如智能指针和迭代器：必须为其指定比较类型！！！

// DereferenceLess 适合作为 T* 的关联容器，也可以作为T对象的迭代器和智能指针的比较类型

条款18：永远让比较函数对相等的值返回false

 //1
    std::set<int, std::less_equal<int> > s; //s以 <= 排序
    s.insert(10);
    //尝试再次插入一个 10
    s.insert(10);

//关联容器对相同的定义是等价，less_equal的意思是 operator<= 所以表述如下 // !(10a <= 10b) && !(10b <= 10a) >> !(true) && !(true) >> false && false >> false
//因此得出结论是：10a与10b不等价，于是将10b插入了容器10a的旁边，set拥有了两个为10的值的拷贝 //less_equal作为比较类型破坏了容器，并且： //任何对相等的值返回true的比较函数都会做同样的事情 //因此，你需要确保你用在关联容器上的比较函数总是对相等的值返回false

struct StringPtrGreater:public std::binary_function<const std::string*,const std::string*,bool>{
    bool operator()(const std::string *ps1, const std::string *ps2) const{
        return !(*ps1 < *ps2); //不可以， >= 将对相等的值返回true，因此需要改正
        //return (*ps2 < *ps1);
    }
};

//对于 multiset这种不要求key唯一的关联容器呢

  std::multiset<int, std::less_equal<int> > ss;

  ss.insert(10);//10a

  ss.insert(10);//10b

//想用 equal_range返回一对包含两个10拷贝的范围迭代器，不可能实现

//因为，equal_range不是指示相等值得范围，而是等价得值得范围，但是10a和10b是不等价得

条款19：避免原地修改set和multiset得键

   //1
    //map<K<V> 和multimap<K,V>类型得对象中元素得类型是pair<const K,V>，因此K不能被改变（当然你使用const_cast除外）
    std::map<int,std::string> m;
    m.insert(std::pair<int,std::string>(10,"liii"));
  //  m.begin()->first = 9;//错误，不能编译

//但是，对于 set或者multiset却是可以得，因为存储得元素类型是T，而不是const T , 好像也不能编译

  std::set<std::string> m_;
    m_.insert("lyy");
    std::set<std::string>::iterator it = m_.begin();
    std::cout<< "*it "<<*it<<std::endl;
    //*it = "lyyy";//错误，不能编译

//2

//为什么 set或者 multiset里得元素不是常数开始假设一个雇员得类见 2

//2
class Employee{
    public:
        const std::string& name() const;//获取雇员得名字
        void setName(const std::string& name);//设置雇员得名字
        const std::string& getTitle() const{

            return title_;
            }//获取雇员得头衔
        void setTitle(std::string& title) const{
            title_ = title;

        }//设置雇员得头衔
        int idNumber() const{

        }//获取雇员得 ID号
    private:
        mutable std::string title_;
};

//假设每个雇员有唯一得ID号，就是idNumber函数返回得数字，建立一个雇员得set，很显然应该只是以 ID号来排序set
struct IDNumberLess:public std::binary_function<Employee,Employee,bool>{
    bool operator()(const Employee& lhs, const Employee& rhs) const{
        return lhs.idNumber() < rhs.idNumber();
    }
};

typedef std::set<Employee,IDNumberLess> EmpIDSet;
EmpIDSet se;//按 ID号排序得雇员得set

//实际上，雇员得ID号是 set中得元素得键，其余得雇员数据只是虚有其表 //在这里，没有理由不能把一个特定雇员得头衔改成某个有趣得东西 //像这样见实现3

  //实现3
    Employee selectedID;//容纳被选择的雇员
    EmpIDSet::iterator i = se.find(selectedID);
    if (i != se.end())
    {   
        std::string str = "ssdd";
        i->setTitle(str);//i 是 const对象，不能调用非const的成员函数，需要调用const的成员函数
    }
    //这里只是改变雇员的一个与set排序的方式无关的方面，一个雇员的非键部分，所以不会破坏set,是合法的

//即使set或multiset是可以改变并且可以编译的，但是要记住 //你改变set或multiset里的元素，必须确保不改变一个键部分——影响容器有序性的元素部分 //用于实现set或moltiset不能被修改： //让用于 set::iterator的operator*返回一个常数 T&, 可以让set的迭代器的解引用的结果是set元素的常量引用 //在这样的实现下，讲没有办法修改set的元素，因为所有访问那些元素的方法都将在让你访问之前加一个const //反之，你总是想要安全地改变set，multiset，map或multimap里地元素，需要按以下步骤来做： /** 1，定位你要改变地容器元素 2，拷贝一份要被修改地元素，对 map或multimap而言，确定不要把副本地第一个元素声明为const，毕竟你要改变它 3，修改副本，使他有你想要在容器里地值 4，从容器里删除元素，通常用 erase 5, 把新值插入容器，如果新元素在容器地排序顺序中地位置正好相同或相邻于删除地元素，使用 insert 看如下例子 */

EmpIDSet se_;//se_是一个以ID号排序地雇员set
   Employee selectedID_; //一个带有需要ID的雇员

   //第一步：找到要改变的元素
   EmpIDSet::iterator i_ = se_.find(selectedID_);
   if(i_ != se_.end())
   {
    //第二步：拷贝这个元素
    Employee e(*i_);
    //第三步：删除这个元素
    se_.erase(i_++);//自增这个迭代器 以保持它有效

    //第四步：修改这个副本
    std::string str_ = "ssssssss";
    e.setTitle(str_);
    //第五步：插入新值，提示它的位置和原先元素的一样
    se_.insert(i_,e);
   }

// 记得关键的事情是对于set和multiset，如果你进行任何容器元素的原地修 // 改，你有责任确保容器保持有序

条款20：考虑有序vector代替关联容器

//快速查找数据结构时，我们立刻会想到标准关联容器：set，multiset，map和multimap //如果查找速度真的很重要，这些也不是最快的，可以考虑非标准的散列容器

//如何实现一个 vector比标准管理容器查找的更快呢？

//但是只有有序的 vector才会比关联容器提供更高的性能，因为关联容器是基于平衡二叉树进行查找的 //而一个平衡二叉查找树是一个对插入，删除和查找的混合操作优化的数据结构，插入，删除和查找混合在一起，没办法预测对树的下一个操作是什么？

//而有序的vector可以使用正确的查找算法：binary_search, lower_bound, equal_range

//函数对象的形式定义查找规则
class myComp{
    public:
        bool operator()(const int& i, const int& j){
            return i > j;
        }
};

//1， binary_search

//http://c.biancheng.net/view/7537.html

//用来查找指定区域内是否包含某个目标元素，返回bool

   //1, binary_search
    std::vector<int> my = {4,5,3,1,2};//所有大于3的元素都在左侧，小于3的元素都在右测，也是可以的
    //查找元素3
    bool haselem =  binary_search(my.begin(),my.end(),3,myComp());
    std::cout<<"1, "<<haselem<<std::endl;

//2， lower_bound

//http://c.biancheng.net/view/7521.html

//在指定区域内查找不小于目标值的第一个元素，返回一个正向迭代器，指向找到的元素，没找到指向last迭代器

    //2， lower_bound
    //从vector中查找第一个违背 myComp规则的元素
    std::vector<int>::iterator iter = lower_bound(my.begin(),my.end(), 3, myComp());
    std::cout<<"2: "<<*iter<<std::endl;

//3，equal_range

//http://c.biancheng.net/view/7531.html

//在指定范围内查找等于目标值的所有元素

//返回一个pair类型值，包含 2个正向迭代器

//查找成功时：第 1 个迭代器指向区域内第一个等于val的元素，第 2个迭代器指向区域中第一个大于 val的元素

//查找失败时：这 2个迭代器要么都指向大于 val的第一个元素，要么都和 last迭代器相同

    //3，equal_range
    std::pair<std::vector<int>::iterator, std::vector<int>::iterator> range_;
    //找到所有的元素 3
    range_ = equal_range(my.begin(),my.end(),3,myComp());
    for(auto it = range_.first; it != range_.second; ++it)
    {
        std::cout<<"3: "<<*it<<std::endl;
    }

//下面看一个具体的案例

//一个 Widget的关联容器和一个有序 vector的PK

//前者注定是一个平衡二叉树，由树节点组成，每个都不仅容纳了一个Widge，而且还保持了一个该节点到左和右孩子的指针 //一个父节点的指针，意味着关联容器中用于存储一个Widge的空间开销至少会是三个指针 //后者并没有开销，当然vector本身有开销，结尾可能是空的，但是可以忽略
//当然，也有缺点 //vector最大的缺点是必须保持有序，这就导致当插入和删除一个元素时，vector必须重新分配它的内存，都必须拷贝，因此，使用 //查找的时候不要和插入和删除混合使用，使用有序 vector代替关联容器才有意义

//具体实现 如2
class Widget__{
    public:
        Widget__(const int v):val(v){}
        bool operator<(const Widget__ &l){
            return this->val < l.val;
        }

      bool operator()(const Widget__ &l,const Widget__ &r){
            return  l.val < r.val;
        }
     
    private:
        int val;
};
//具体查找如 2-1

 //2-1
    std::vector<Widget__> vw;
    Widget__ w1(2);
    Widget__ w2(3);
    vw.push_back(w1);
    vw.push_back(w2);

    std::sort(vw.begin(),vw.end());
    //用于查找的值的对象
    Widget__ find_(3);
    //开始查找 2-1-1
    if(binary_search(vw.begin(),vw.end(),find_, Widget__(1)))
    {
       std::cout<<" 2-1-1 "<<std::endl;
    }
    // //2-1-2
    std::vector<Widget__>::iterator i = lower_bound(vw.begin(),vw.end(),find_);
    if ( i != vw.end() && !( find_ < *i))
    {
         std::cout<<"2-1-2 "<<std::endl;
    }
    
    // //2-1-3
    std::pair<std::vector<Widget__>::iterator, std::vector<Widget__>::iterator> r_ = equal_range(vw.begin(),vw.end(),find_, Widget__(1));
    if(r_.first != r_.second){
         std::cout<<"2-1-3 "<<std::endl;
    }

//当你具体用 vector代替map或multimap，只记住一点 pair设计成 pair<K，V>可变的就行 //必须做的另外一件事是，写一个自定义的比较函数，排序的比较函数，还需要一个比较函数进行查找 //排序的比较函数作用于两个pair对象，查找的比较函数用到key，必须传给用于查找的比较函数一个key类型对象和一个pair对象

//具体实现 如 3
//map容纳的对象
typedef std::pair<std::string,int> Data;
//用于比较的类
class DataComp{
    public:
        //用于排序的比较函数
        bool operator()(const Data &lhs, const Data& rhs) const{
            return keyLess(lhs.first,rhs.first);
        }
        //用于查找的比较函数形式1
        bool operator()(const Data& lhs,const Data::first_type& k) const{
            return keyLess(lhs.first,k);
        }
        //用于查找的比较函数形式2
        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::first_type& k2) const{
            return k1 < k2;
        }
};
//有序的vector模拟map<string,int>，keyless成员函数的存在是用来保证几个不同的operator函数之间的一致性，每个这样的函数只是比较两个key的值

//比较函数的实现如 3-1

//3-1 
    std::vector<Data> vd ;//代替map<string,int>
    vd.push_back(std::pair<std::string ,int>("lyy",10));
    vd.push_back(std::pair<std::string ,int>("lss",11));
    //排序
    std::sort(vd.begin(),vd.end(),DataComp());
    //用于查找的值的对象
    std::string s = "lss";
    //开始查找 3-1-1
    if(binary_search(vd.begin(),vd.end(),s,DataComp()))
    {
       std::cout<<" 3-1-1 "<<std::endl;
    }
    // //2-1-2
    std::vector<Data>::iterator i_ = lower_bound(vd.begin(),vd.end(),s,DataComp());
    if ( i_ != vd.end() && !DataComp()(s,*i_))
    {
         std::cout<<"3-1-2 "<<std::endl;
    }
    
    // // //2-1-3
    std::pair<std::vector<Data>::iterator, std::vector<Data>::iterator> r__ = equal_range(vd.begin(),vd.end(),s,DataComp());
    if(r__.first != r__.second){
         std::cout<<"3-1-3 "<<std::endl;
    }

// 一旦你写了DataCompare，东西都很好的依序排列了。而一旦位置合适了，只要你的程序按照 // 阶段方式使用数据结构，它们往往比相应的使用真的map的设计运行得更快而且使用更少内存。 // 如果你的程序不是按照阶段的方式操作数据结构，那么使用有序vector代替标准关联容器几乎可以确定是在 // 浪费时间
1, 1 2: 3 3: 3 2-1-1 2-1-2 2-1-3 3-1-1 3-1-2 3-1-3

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

//一个支持默认构造函数和一个double构造和赋值的类
class WidgetA{
    public:
        WidgetA(){}
        WidgetA(double weight): w_(weight){}
        WidgetA& operator=(double weight){
            w_ = weight;

            return *this;
        }
    
    private:
        double w_;
};

//建立一个map,初始化有特定值的映射 见 1

    //1
    std::map<int,WidgetA> m;
    WidgetA m1(1.50);
    WidgetA m2(73.6);
    m[1] = m1;
    m[2] = m2;

//map<K,V> m -> m[K] = V; map::operator[] //检查k是否已经在map里，如果不，就添加上，以V作为它的对应值，如果k已经在map里，它的关联值被更新成V /** 原理如下： 1，operator[]返回一个与 k关联的值对象的引用，然后 v赋值给所引用（从 operator[]返回的）的对象 2，当要更新一个已存在的键的关联值时很直接，已经有 operator[] 可以用来返回引用的值对象 3，但是k不再map里，operator[]就没有可以引用的值对象，这样，使用值类型的默认构造函数从头开始建立一个，然后 operator[]返回这个新建立对象的引用所以，下面实现等价于如1-1 */
//1-1 //m[1]是 m.operato的简化，所以这是一个 map::operator[]的调用，必须返回一个WidgetA引用，因为m的映射类型是WidgetA //在这里，m里面还没任何东西，所以键 2 在map里没有入口，因此，operator[]默认构造一个WidgetA来作为关联到1的值，然后返回到那个WidgetA的引用 //最后， WidgetA成为赋值目标：被赋值的值是 m1 //因此，m[1] = m1 等价于如1-2

    //1-2
    typedef std::map<int,WidgetA> IntWidgetMap;
    //用键1建立新的映射入口，和一个默认构造的值对象
    std::pair<IntWidgetMap::iterator, bool> result = m.insert(IntWidgetMap::value_type(1,WidgetA()));
    result.first->second = m1;//赋值给新构造的值类型

//看出来为什么会降低性能了把 /** 1，先默认构造一个WidgetA, 然后我们立即赋值给它心智 2，可以用想要的值构造WidgetA 比默认构造WidgetA然后进行赋值更加高效，这时候想到了 inset，见 1-3 */

   //1-3
    m.insert(IntWidgetMap::value_type(1,m1));
    //它节省了三次函数的调用
    //1，一个建立临时的默认构造WidgetA对象
    //2，一个销毁那个临时对象和一个对WidgetA的赋值操作

//那是不是所有的map都用 insert好了？ //也不是，记住 operator[]立即为添加或更新的意思 //1，当添加时候，insert高效 //2，当一个等价的键，更新时，[]高效 //这是为什么呢？ //看下更新的实现如 2

    //2
    WidgetA m1_(1.111111);
    m[1] = m1_; //已经有了 键 1

    m.insert(IntWidgetMap::value_type(1,m1_)).first->second = m1_;//更新 1 的值为 m1_

//1, 语法本身就应该支持 operator[], 看效率 //1，insert的调用需要IntWidgetMap::value_type类型的实参（pair<int,WIdgetA>）,所以当我们调用inset时 //必须构造和析构一个那种类型的对象，耗时一对构造和析构函数，也会造成一个WidgetA的构造和析构 //2，因为 pair<int,WidgetA>本身包含了一个WidgetA对象，operator[]没有使用pair对象，所以没有构造和析构pair和WidgetA //现在我们知道了两个用处，能不能有个STL提供一个两全其美的函数，在添加或更新时，自动选择调用接口，像这样 2-1 //2-1 //如果键 k不在map m中，高效地把pair(k,v)添加到m中，否则高效地把和k关联地值更新为v，返回一个指向添加或修改pair的迭代器 //iterator affectedPair = efficientAddOrUpdate(m,k,v); //但是 stl没有这样的函数，那就自己写一个如 3

//3
template<typename MapType, typename KeyArgType, typename ValueArgType>
typename MapType::iterator efficientAddOrUpdate(MapType& m, const KeyArgType& k, const ValueArgType& v)
{
    //找到 k在或应该在哪里
    typename MapType::iterator lb = m.lower_bound(k);

    //如果 lb指向一个pair，他的键等价于 k，更新这个pair
    //通过 map::key_comp提供的比较函数
    if( lb != m.end() && !(m.key_comp()(k, lb->first))){
        lb->second = v;
    }
    else
    {
        //把pair(k,v)添加到m并返回指向新 map元素的迭代器
        //更新
        typedef typename MapType::value_type MVT;
        return m.insert(lb,MVT(k,v));
    }
}
//具体调用见 3-1

 //3-1
    efficientAddOrUpdate(m,1,m1_);

// 这个实现的一个有趣方面是KeyArgType和ValueArgType不必是储存在map里的类型。它们只需要可以转换到储存在map里的类型。一个可选的方法是去掉类型参数KeyArgType和ValueArgType，改为使用MapType:: key_type和MapType::mapped_type。 // 假设是一次更新操作，即，m已经包含键是1的元素。那样的话，上面的模板推断出ValueArgType是double，函数体直接把m1_与1相关的那个Widget。那是通过调用Widget::operator(double)完成的。 // 如果我们用了MapType::mapped_type作为efficientAddOrUpdate的第3个参数的类型，在调用时我们得把m_转化成一个Widget，那样的话我们就得花费本来不需要的一次Widget构造（以及随后的析构）

条款22：熟悉非标准散列容器

//熟悉的散列容器： //unordered_set, unordered_multiset, unordered_map, unordered_multimap //今天来看看非标准散列容器：hash_set， hash_multiset, hash_map 和 hash_multimap

//1, hash_set

//https://blog.csdn.net/cumirror/article/details/5596908

//目前还不是C++的标准容器，只是SGI C++ STL的一个扩展容器，使用hash_set必须使用宏语句#include <hash_set>

struct student{
 char* name;
 int age;
 char* city;
 char* phone;
};
//自定义数据的比较函数
class stuequal{
    public:
    bool operator() (const student& a,const student& b){
         return strcmp(a.city,b.city)==0;      //不允许同名，name为键值
    }               //将name换为city测试下
};
//自定义数据的hash函数
//typedef unsigned int size_t;
struct stu_hash{
 size_t operator()(const student& stu) const
 {
    unsigned long res = 0;
    char* s=stu.city;
    for( ; *s; ++s ){
        res=5*res+*s;
    }
    return size_t(res);
 }
};

//针对字符串的比较函数对象
class strequal{
public:
 bool operator () (const char* a,const char* b)const{
  return strcmp(a,b)==0;         
 }
};

int main(){
 using namespace std;

 __gnu_cxx::hash_set<const char*,hash<const char*>,strequal> a;
 a.insert("tongjin");
 a.insert("cumirror");
 a.insert("makelaugh");
 a.insert("feiguodeyun");

// hash<const char*>默认提供的hash函数对象
 __gnu_cxx::hash_set<const char*,hash<const char*>,strequal>::const_iterator b=a.find("tongjin");
 cout<<*b<<" is "<<(b!=a.end()?"present":"not present")<<endl;

// 对于自定义类型数据,使用hash相关容器时应构造hash函数对象、比较函数对象
// 注意区别hash函数对象与比较函数对象各自的作用
 student s[]={
  {"童进",23,"长沙","XXX"},
  {"老大",23,"武汉","XXX"},
  {"饺子",23,"福州","XXX"},
  {"王老虎",23,"地球","XXX"},
  {"周润发",23,"香港","XXX"},
  {"周星星",23,"香港","XXX"},   //city重复
  {"童进",23,"香港","XXX"}   //name重复、city也有重复
 };         

 __gnu_cxx::hash_set<student,stu_hash,stuequal> c;
    c.insert(s[0]);
    c.insert(s[1]);
    c.insert(s[2]);
    c.insert(s[3]);
    c.insert(s[4]);
    c.insert(s[5]);
    c.insert(s[6]);
// 注意hash容器并不能实现排序
 for(__gnu_cxx::hash_set<student,stu_hash,stuequal>::iterator i=c.begin();i!=c.end();i++){
  cout<<i->name<<" "<<i->age<<" "<<i->city<<endl;
 }
}

//2. hash_map

//https://blog.csdn.net/yousss/article/details/79541543

 //2
 typedef __gnu_cxx::hash_map<const char*, string, hash<const char*>, strequal> StrIntMap;
StrIntMap namemap;
namemap["岳不群"]="华山派掌门人，人称君子剑";
namemap["张三丰"]="武当掌门人，太极拳创始人";
namemap["东方不败"]="第一高手，葵花宝典";

#include <hash_map>
#include <string>
#include <iostream>

using namespace std;
//define the class
class ClassA{
        public:
        ClassA(int a):c_a(a){}
        int getvalue()const { return c_a;}
        void setvalue(int a){c_a;}
        private:
        int c_a;
};

//1 define the hash function
struct hash_A{
        size_t operator()(const class ClassA & A)const{
                //  return  hash<int>(classA.getvalue());
                return A.getvalue();
        }
};

//2 define the equal function
struct equal_A{
        bool operator()(const class ClassA & a1, const class ClassA & a2)const{
                return  a1.getvalue() == a2.getvalue();
        }
};

int main()
{
        hash_map<ClassA, string, hash_A, equal_A> hmap;
        ClassA a1(12);
        hmap[a1]="I am 12";
        ClassA a2(198877);
        hmap[a2]="I am 198877";
        
        cout<<hmap[a1]<<endl;
        cout<<hmap[a2]<<endl;
        return 0;
}

//与标准关联容器有什么区别

//(101条消息) C++：map、hash_map、unordered_map_cylianging的博客-CSDN博客_c++ hash_map和unordered_map

//(101条消息) unordered_map, hash_map, map 区别_initMyHeart的博客-CSDN博客_unordered_map和hash_map的区别

本文参与腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2022-11-07，如有侵权请联系 cloudcommunity@tencent.com 删除

容器