C++的STL总结（2）

2023-08-11 18:35:10

紧接着上篇博客，把没总结全的继续补充。

（13）set容器

set是用红黑树的平衡二叉索引树的数据结构来实现的，插入时，它会自动调节二叉树排列，把元素放到适合的位置，确保每个子树根节点的键值大于左子树所有的值、小于右子树所有的值，插入重复数据时会忽略。set迭代器采用中序遍历，检索效率高于vector、deque、list，并且会将元素按照升序的序列遍历。set容器中的数值，一经更改，set会根据新值旋转二叉树，以保证平衡，构建set就是为了快速检索（python中的set一旦建立就是一个常量，不能改的）。

　multiset，与set不同之处就是它允许有重复的键值。

set和map的区别如下

set是一种关联式容器，其特性如下：

set以RBTree作为底层容器
所得元素的只有key没有value，value就是key
不允许出现键值重复
所有的元素都会被自动排序
不能通过迭代器来改变set的值，因为set的值就是键

map和set一样是关联式容器，它们的底层容器都是红黑树，区别就在于map的值不作为键，键和值是分开的。它的特性如下：

map以RBTree作为底层容器
所有元素都是键+值存在
不允许键重复
所有元素是通过键进行自动排序的
map的键是不能修改的，但是其键对应的值是可以修改的
2.set中常用的方法

begin() 　　 ,返回set容器的第一个元素

end() 　　　　 ,返回set容器的最后一个元素

clear() 　　 ,删除set容器中的所有的元素

empty() 　　　,判断set容器是否为空

max_size() 　 ,返回set容器可能包含的元素最大个数

size() 　　　　 ,返回当前set容器中的元素个数

rbegin　　　　 ,返回的值和end()相同

rend()　　　　 ,返回的值和rbegin()相同

  #include <iostream>

  #include <set>

  using namespace std;

  int main()

  {

      set<int> s;

      s.insert();

     s.insert();

     s.insert();

     s.insert();

     cout<<"set 的 size 值为 ："<<s.size()<<endl;

     cout<<"set 的 maxsize的值为 ："<<s.max_size()<<endl;

     cout<<"set 中的第一个元素是 ："<<*s.begin()<<endl;

     cout<<"set 中的最后一个元素是:"<<*s.end()<<endl;

     s.clear();

     if(s.empty())

     {

         cout<<"set 为空 ！！！"<<endl;

     }

     cout<<"set 的 size 值为 ："<<s.size()<<endl;

     cout<<"set 的 maxsize的值为 ："<<s.max_size()<<endl;

     return ;

 }

小结：插入3之后虽然插入了一个1，但是我们发现set中最后一个值仍然是3哈，这就是set 。还要注意begin() 和 end()函数是不检查set是否为空的，使用前最好使用empty()检验一下set是否为空
count() 用来查找set中某个某个键值出现的次数。这个函数在set并不是很实用，因为一个键值在set只可能出现0或1次，这样就变成了判断某一键值是否在set出现过了。

  #include <iostream>

  #include <set>

  using namespace std;

  int main()

  {

      set<int> s;

      set<int>::const_iterator iter;

     set<int>::iterator first;

     set<int>::iterator second;

     for(int i =  ; i <=  ; ++i)

     {

         s.insert(i);

     }

     //第一种删除

     s.erase(s.begin());

     //第二种删除

     first = s.begin();

     second = s.begin();

     second++;

     second++;

     s.erase(first,second);

     //第三种删除

     s.erase();

     cout<<"删除后 set 中元素是 ：";

     for(iter = s.begin() ; iter != s.end() ; ++iter)

     {

         cout<<*iter<<" ";

     }

     cout<<endl;

     return ;

  #include <iostream>

  #include <set>

  using namespace std;

  int main()

  {

      set<int> s;

      s.insert();

     s.insert();

     s.insert();

     s.insert();

     cout<<"set 中 1 出现的次数是 ："<<s.count()<<endl;

     cout<<"set 中 4 出现的次数是 ："<<s.count()<<endl;

     return ;

 }

  #include <iostream>

  #include <set>

  using namespace std;

  int main()

  {

      set<int> s;

      set<int>::const_iterator iter;

     set<int>::iterator first;

     set<int>::iterator second;

     for(int i =  ; i <=  ; ++i)

     {

         s.insert(i);

     }

     //第一种删除

     s.erase(s.begin());

     //第二种删除

     first = s.begin();

     second = s.begin();

     second++;

     second++;

     s.erase(first,second);

     //第三种删除

     s.erase();

     cout<<"删除后 set 中元素是 ：";

     for(iter = s.begin() ; iter != s.end() ; ++iter)

     {

         cout<<*iter<<" ";

     }

     cout<<endl;

     return ;

　　（14）正反遍历，迭代器iterator、reverse_iterator

#include<iostream>

#include<set>

using namespace std;

int main()

{

    set<int> v;

    v.insert();

    v.insert();

    v.insert();

    v.insert();

    v.insert();

    v.insert();

    //中序遍历 升序遍历

    for(set<int>::iterator it = v.begin(); it != v.end(); ++it)

    {

        cout << *it << " ";

    }

    cout << endl;

    for(set<int>::reverse_iterator rit = v.rbegin(); rit != v.rend(); ++rit)

    {

        cout << *rit << " ";

    }

    cout << endl;

    return ;

}

（15）自定义比较函数，insert的时候，set会使用默认的比较函数（升序），很多情况下需要自己编写比较函数。

　　1、如果元素不是结构体，可以编写比较函数，下面这个例子是用降序排列的（和上例插入数据相同）：

#include<iostream>

#include<set>

using namespace std;

struct Comp

{

    //重载()

    bool operator()(const int &a, const int &b)

    {

        return a > b;

    }

};

int main()

{

    set<int,Comp> v;

    v.insert();

    v.insert();

    v.insert();

    v.insert();

    v.insert();

    v.insert();

    for(set<int,Comp>::iterator it = v.begin(); it != v.end(); ++it)

    {

        cout << *it << " ";

    }

    cout << endl;

    for(set<int,Comp>::reverse_iterator rit = v.rbegin(); rit != v.rend(); ++rit)

    {

        cout << *rit << " ";

    }

    cout << endl;

    return ;

}

　　2、元素本身就是结构体，直接把比较函数写在结构体内部，下面的例子依然降序：

#include<iostream>

#include<set>

#include<string>

using namespace std;

struct Info

{

    string name;

    double score;

    //重载 <

    bool operator < (const Info &a) const

    {

        return a.score < score;

    }

};

int main()

{

    set<Info> s;

    Info info;

    info.name = "abc";

    info.score = 123.3;

    s.insert(info);

    info.name = "EDF";

    info.score = -23.53;

    s.insert(info);

    info.name = "xyz";

    info.score = 73.3;

    s.insert(info);

    for(set<Info>::iterator it = s.begin(); it != s.end(); ++it)

    {

        cout << (*it).name << ":" << (*it).score << endl;

    }

    cout << endl;

    for(set<Info>::reverse_iterator rit = s.rbegin(); rit != s.rend(); ++rit)

    {

        cout << (*rit).name << ":" << (*rit).score << endl;

    }

    cout << endl;

    return ;

}

（16）map的用法

#include<iostream>

#include<map>

#include<string>

using namespace std;

int main()

{

    map<string,double> m;

    //声明即插入

    m["li"] = 123.4;

    m["wang"] = 23.1;

    m["zhang"] = -21.9;

    m["abc"] = 12.1;

    for(map<string,double>::iterator it = m.begin(); it != m.end(); ++it)

    {

        //first --> key second --> value

        cout << (*it).first << ":" << (*it).second << endl;

    }

    cout << endl;

    return ;

}

用map实现数字分离

　　string --> number

　　之前用string进行过数字分离，现在使用map

#include<iostream>

#include<map>

#include<string>

using namespace std;

int main()

{

    map<char,int> m;

    m[''] = ;

    m[''] = ;

    m[''] = ;

    m[''] = ;

    m[''] = ;

    m[''] = ;

    m[''] = ;

    m[''] = ;

    m[''] = ;

    m[''] = ;

    /*

        等价于

        for(int i = 0; i < 10; ++i)

        {

            m['0' + i] = i;

        }

    */

    string sa;

    sa = "";

    int sum = ;

    for( int i = ; i < sa.length(); ++i)

    {

        sum += m[sa[i]];

    }

    cout << sum << endl;

    return ;

}

number --> string

#include <iostream>

#include <map>

#include <string>

using namespace std;

int main()

{

    map<int,char> m;

    for(int i = ; i < ; ++i)

    {

        m[i] = '' + i;

    }

    int n = ;

    string out = "the number is :";

    cout << out + m[n] << endl;

    return ;

}

（17）multimap

　　multimap由于允许有重复的元素，所以元素插入、删除、查找都与map不同。

　　插入insert（pair<a,b>(value1,value2)）

#include <iostream>

#include <map>

#include <string>

using namespace std;

int main()

{

    multimap<string,double> m;

    m.insert(pair<string,double>("Abc",123.2));

    m.insert(pair<string,double>("Abc",123.2));

    m.insert(pair<string,double>("xyz",-43.2));

    m.insert(pair<string,double>("dew",43.2));

    for(multimap<string,double>::iterator it = m.begin(); it != m.end(); ++it )

    {

        cout << (*it).first << ":" << (*it).second << endl;

    }

    cout << endl;

    return ;

}

（18）deque

　　deque和vector一样,采用线性表，与vector唯一不同的是，deque采用的分块的线性存储结构，每块大小一般为512字节，称为一个deque块，所有的deque块使用一个Map块进行管理，每个map数据项记录各个deque块的首地址，这样以来，deque块在头部和尾部都可已插入和删除元素，而不需要移动其它元素。使用push_back()方法在尾部插入元素，使用push_front()方法在首部插入元素，使用insert()方法在中间插入元素。一般来说，当考虑容器元素的内存分配策略和操作的性能时，deque相对vectore更有优势。(下面这个图，我感觉Map块就是一个list< map<deque名字，deque地址> >)

 #include <iostream>

 #include <deque>

 using namespace std;

 int main()

 {

     deque<int> d;

     //尾部插入

     d.push_back();

     d.push_back();

     d.push_back();

     for(deque<int>::iterator it = d.begin(); it != d.end(); ++it )

     {

         cout << (*it) << " ";

     }

     cout << endl << endl;

     //头部插入

     d.push_front();

     d.push_front(-);

     for(deque<int>::iterator it = d.begin(); it != d.end(); ++it )

     {

         cout << (*it) << " ";

     }

     cout << endl << endl;

     d.insert(d.begin() + ,);

     for(deque<int>::iterator it = d.begin(); it != d.end(); ++it )

     {

         cout << (*it) << " ";

     }

     cout << endl << endl;

     //反方向遍历

     for(deque<int>::reverse_iterator rit = d.rbegin(); rit != d.rend(); ++rit )

     {

         cout << (*rit) << " ";

     }

     cout << endl << endl;

     //删除元素pop pop_front从头部删除元素 pop_back从尾部删除元素 erase中间删除 clear全删

     d.clear();

     d.push_back();

     d.push_back();

     d.push_back();

     d.push_back();

     d.push_back();

     d.push_back();

     d.push_back();

     d.push_back();

     for(deque<int>::iterator it = d.begin(); it != d.end(); ++it )

     {

         cout << (*it) << " ";

     }

     cout << endl;

     d.pop_front();

     d.pop_front();

     for(deque<int>::iterator it = d.begin(); it != d.end(); ++it )

     {

         cout << (*it) << " ";

     }

     cout << endl;

     d.pop_back();

     d.pop_back();

     for(deque<int>::iterator it = d.begin(); it != d.end(); ++it )

     {

         cout << (*it) << " ";

     }

     cout << endl;

     d.erase(d.begin() + );

     for(deque<int>::iterator it = d.begin(); it != d.end(); ++it )

     {

         cout << (*it) << " ";

     }

     cout << endl;

     return ;

 }

（19）list

　　list<int> l

　　插入：push_back尾部，push_front头部，insert方法前往迭代器位置处插入元素，链表自动扩张，迭代器只能使用++--操作，不能用+n -n，因为元素不是物理相连的。

　　遍历：iterator和reverse_iterator正反遍历

　　删除：pop_front删除链表首元素；pop_back()删除链表尾部元素；erase（迭代器）删除迭代器位置的元素，注意只能使用++--到达想删除的位置；remove（key）删除链表中所有key的元素，clear（）清空链表。

　　查找：it = find(l.begin(),l.end(),key)

　　排序：l.sort()

　　删除连续重复元素:l.unique() 【2 8 1 1 1 5 1】 --> 【 2 8 1 5 1】

（20）bitset

（21）stack（后进先出）

　　这个印象深刻，学数据结构的时候做表达式求值的就是用的栈。

 #include <iostream>

 #include <stack>

 using namespace std;

 int main()

 {

     stack<int> s;

     s.push();

     s.push();

     s.push();

     s.push();

     cout << s.size() << endl;

     while(s.empty() != true)

     {

         cout << s.top() << endl;

         s.pop();

     }

     return ;

 }

（22）queue（先进先出）

　　queue有入队push（插入）、出队pop（删除）、读取队首元素front、读取队尾元素back、empty，size这几种方法

（23）priority_queue(最大元素先出)

 #include <iostream>

 #include <queue>

 using namespace std;

 int main()

 {

     priority_queue<int> pq;

     pq.push();

     pq.push();

     pq.push();

     pq.push();

     pq.push();

     pq.push();

     cout << "size: " << pq.size() << endl;

     while(pq.empty() != true)

     {

         cout << pq.top() << endl;

         pq.pop();

     }

     return ;

 }

重载操作符同set重载操作符。

参考：https://www.cnblogs.com/CnZyy/p/3317999.html

码农公寓

相关文章