【STL编程】【竞赛常用】【part 2】

文章目录

• 【STL编程】【竞赛常用】【part 1】
• 【STL编程】【竞赛常用】【part 2】
• • 6. pair 容器
  • 7. set 集合容器
  • 8. multiset 多重集合容器
  • 9. map 映射容器
  • 10. multimap 多重映射容器
• 【STL编程】【竞赛常用】【part 3】
• • 敬请期待！！！
  • 11. list 双向链表容器
  • 12. stack 堆栈容器
  • 13. queue 队列容器
  • 14. deque 双端队列容器
  • 15. priority_queue 优先队列容器

【STL编程】【竞赛常用】【part 1】

【STL编程】【竞赛常用】【part 1】

【STL编程】【竞赛常用】【part 2】 6. pair 容器

定义	解释
pair p1;	创建一个空的pair对象，它的两个元素分别是T1和T2类型，采用值初始化
pairp1(v1,v2):	创建一个pair对象，其中first成员初始化为v1，而second成员初始化为v2
make_pair(v1.v2)	以v1和v2值创建一个新的pair对象，其元素类型分别是v1和v2的类型
p1	两个 pair 对象之间的小于运算,其定义遵循字典次序：如果p1.first＜p2.first 或者!(p2.first＜p1.first)&&(p1.second＜p2. second)，则返回true
p1==p2	如果两个pair 对象的first和second成员依次相等，则这两个对象相等
p.first	返回p中名为first的（公有）数据成员
p.second	返回p的名为second的（公有）数据成员

#include 
using namespace std;

int main(){
    pair p1; //使用默认构造函数
    p1.first = 10;
    p1.second = 12.5;
    cout << p1.first << ' ' << p1.second << endl;
    return 0;
}

#include 
using namespace std;
typedef pair psd; // typedef简化pair的声明为Record

int main(){
    psd p1 = make_pair("yjr", 100);
    psd p2;
    p2 = p1; //重载运算符"="
    cout << p2.first << ' ' << p2.second << endl;
    return 0;
}

pair 的比较是按照字典序比较的，比较时先按照first 的大小比较，如果相等，再按second 的大小比较：

// pair 的比较
#include 
using namespace std;

int main(){
    pair A(10, 'z');
    pair B(90, 'a');
    if (A == B)
        cout << "相等n";
    if (A != B)
        cout << "不相等n";
    if (A < B)
        cout << "A B)
        cout << "A>Bn";
    if (A <= B)
        cout << "A<=Bn";
    if (A >= B)
        cout << "A>=Bn";
    return 0;
}

7. set 集合容器

set集合容器在头文件中声明，使用类似于树的结构（基于红黑树的平衡二叉检索树），存储数据并自动将数据（无重复值）由小到大排列。构造set集合容器的主要目的是快速检索（时间复杂度为O(logN)），检索效率高于vector、deque及list等容器。

访问set集合容器中的元素，需要通过迭代器进行。迭代器类似于指针，可以通过它指向容器中的某个元素的地址。例如set::iterator ii;定义了一个set类型的迭代器为ii。

方法	解释
s.begin()	返回set容器的第一个元素
s.end()	返回set容器的最后一个元素
s.clear()	删除set容器中的所有的元素
s.empty()	判断set容器是否为空
s.insert()	插入一个元素
s.erase()	删除一个元素
s.size()	返回当前set容器中的元素个数
s.lower_bound()	返回第一个大于或等于给定关键值的元素
s.upper_bound()	返回第一个大于给定关键值的元素
s.equal_range()	返回一对定位器，分别表示 第一个大于或等于给定关键值的元素 和 第一个大于给定关键值的元素，这个返回值是一个pair类型，如果这一对定位器中哪个返回失败，就会等于 s.end()

#include 
using namespace std;

int main(){
    set s;
    for (int i = 10; i > 0; --i) //此处由大到小赋值
        s.insert(i);             //插入元素
    set s2(s);              //拷贝s生成s2
    s.erase(s.begin());          //删除操作
    s.erase(6);
    s.insert(5);                              //不会重复插入
    set::iterator ii;                    // ii为前向迭代器
    for (ii = s.begin(); ii != s.end(); ii++) //遍历
        cout << *ii << ' ';
    cout << "n元素个数为" << s.size(); //统计set中元素个数，时间复杂度O(1)
    ii = s.find(10);                    //查找元素值，并返回指向该元素的迭代器
    if (ii != s.end())                  //如容器中不存在该元素，返回值等于s.end()
        cout << "n查找=" << *ii;
    if (s.count(5)) //返回set中值为5的元素个数，时间复杂度为O(log n)
        cout << "n存在元素5";
    s.clear(); //清空所有元素
    cout << "n元素是否为空:" << s.empty();
    return 0;
}

#include
using namespace std;

int main(){
    set myset;
    for (int i = 1; i < 11; i++){
		myset.insert(i);
	}
	cout << "lower_bound & upper_bound test:" << endl;
	cout << "第一个大于等于3的元素:" << *myset.lower_bound(3) << endl; //函数实际返回地址值
	cout << "第一个大于3的元素:" << *myset.upper_bound(3) << endl;	
	cout << "equal_range test:" << endl;
	cout << "第一个大于或等于2的元素: " << *myset.equal_range(2).first << endl;
	cout << "第一个大于2的元素: " << *myset.equal_range(2).second << endl;
	if (myset.equal_range(20).first == myset.end())
		cout << "不存在大于等于20的元素" << endl;
	myset.clear();
    return 0;
}

使用insert()将元素插入set集合容器的时候，集合容器默认按由小到大的顺序插入元素，然而在很多情况下（例如需要由大到小排序）需要自行编写比较函数。

// set的比较函数
#include 
using namespace std;

struct Comp{
    bool operator()(const int &a, const int &b){
        return a > b; //从大到小排序
        // return a < b;  //从小到大排序
    }
}; //需在结构体内定义比较函数

int main(){
    set s;             // set调用的比较函数为Comp
    for (int i = 1; i <= 10; ++i) //此处是由小到到赋值
        s.insert(i);
    set::iterator ii;
    for (ii = s.begin(); ii != s.end(); ii++) //遍历
        cout << *ii << ' ';
    return 0;
}

重载操作符可以使得自定义类型像基本数据类型一样支持加、减、乘、除、自加、自减等各种操作。operator是C++的关键字，它和操作符（例如“ () ”）一起使用，表示运算符重载函数，在理解时可将operator和运算符（例如“operator()”）视为函数名。

参数定义为const int &a和const int &b这种形式，一是防止a和b被修改，二是通过引用变量的方式减少系统开销。末尾的const也是为了防止被修改。

实际上，很多C++操作符已经被重载了，例如 “*” 用于两个数字之间时，得到的是它们的乘积；用于一个地址之前时，得到的是这个地址上存储的值。cin>>x和cout<>”和“<<”运算符也被重载了。

例如自定义一个结构体Time类型，并想实现两个Time类型相加的操作（即小时与小时相加，分钟与分钟相加，秒与秒相加），其程序可能如下所示。

#include 
using namespace std;

struct Time{
    int H, M, S;                        //时，分，秒
    Time operator+(const Time &b) const //重载运算符"+"
    {
        return Time{H + b.H, M + b.M, S + b.S}; //仅为演示，不考虑进位
    }
} T1 = {3, 2, 4}, T2 = {5, 20, 30}, T3;

int main(){
    T3 = T1 + T2;
    cout << T3.H << ":" << T3.M << ":" << T3.S << endl;
    return 0;
}

C++只能重载已有的操作符。下表列出了可以被重载的操作符。

当元素是结构体时，必须要重载运算符“<”：

// set的结构体排序
#include 
using namespace std;

struct Info{
    string name;
    double score;
    bool operator<(const Info &a) const  {//重载"<"操作符,照抄即可
        return a.score < score; //从大到小排序
     // return a.score >score;  //从小到大排序
    }
} info;

int main(){
    set s;
    info = {"A", 90.0};
    s.insert(info);
    info = {"B", 92.0};
    s.insert(info);
    info = {"C", 96.0};
    s.insert(info);

    set::iterator ii;
    for (ii = s.begin(); ii != s.end(); ii++) //遍历
        cout << (*ii).name << ' ' << (*ii).score << endl;
    return 0;
}

8. multiset 多重集合容器

multiset多重集合容器在头文件中定义，它可以看成序列，序列中可以存在重复的数。multiset能时刻保证序列中的数是有序的（默认从小到大排序），插入一个数或删除一个数都能够在O(logn)的时间内完成。

#include 
using namespace std;

int main(){
    multiset m;
    m.insert(11); //插入数据
    m.insert(21);
    m.insert(10);
    m.insert(12);
    m.insert(12);
    m.insert(11);
    m.insert(11);
    m.insert(11);
    m.insert(9);
    cout << "11的个数有" << m.count(11) << endl; //输出multiset中11的个数
    cout << "第一个大于等于10的元素为：" << *m.lower_bound(10) << endl;
    cout << "第一个大于11的元素为:" << *m.upper_bound(11) << endl;
    multiset::iterator it;
    for (it = m.begin(); it != m.end(); it++)
        cout << *it << endl;                            //从小到大输出
    cout << "删除12,有" << m.erase(12) << "个" << endl; //删除等于12的元素
    cout << "查找9n";
    multiset::iterator i = m.find(9); //查找v,返回该元素的迭代器位置
    if (i != m.end())                      //找到则输出，否则i为end()迭代器位置
        cout << *i << endl;
    pair::iterator, multiset::iterator> p;
    int v = 11;
    // equal_range:有序容器中表示一个值第一次出现与最后一次出现的后一位
    p = m.equal_range(v); //查找所有相同元素
    cout << "大于等于" << v << "的第一个元素为" << *p.first << endl;
    cout << "大于" << v << "的第一个元素为" << *p.second << endl;
    cout << "键值为" << v << "的全部元素为";
    for (it = p.first; it != p.second; it++) //打印重复键值元素11
        cout << *it << " ";
    m.clear(); //清空所有元素
    return 0;
}

11的个数有4
第一个大于等于10的元素为：10
第一个大于11的元素为:12     
9
10
11
11
11
11
12
12
21
删除12,有2个
查找9
9
大于等于11的第一个元素为11
大于11的第一个元素为21
键值为11的全部元素为11 11 11 11

9. map 映射容器

map映照容器在头文件

方法	解释
begin()	返回指向map头部的迭代器
end()	返回指向map末尾的迭代器
rbegin()	返回一个指向map尾部的逆向迭代器
rend()	返回一个指向map头部的逆向迭代器
clear(）	删除所有元素
count()	返回指定元素出现的次数(因为key值不会重复，所以只能是1 or 0)
empty()	如果map为空则返回true
equal_range()	返回特殊条目的迭代器对
erase()	删除一个元素
find()	查找一个元素
insert()	插入元素
size()	返回map中元素的个数
swap()	交换两个map
get_allocator()	返回map的配置器
key_comp()	返回比较元素key的函数
value_comp()	返回比较元素value的函数
lower_bound()	返回键值>=给定元素的第一个位置
upper_bound()	返回键值>给定元素的第一个位置
max_size()	返回可以容纳的最大元素个数
size()	返回map中元素的个数
swap()	交换两个map

#include 
using namespace std;

int main(){
    map ms;
    ms[1] = "student_one";
    ms[1] = "student_two"; // id相同，则覆盖
    ms[2] = "student_three";
    map::iterator iter;
    ms.insert(make_pair(3, "student_four")); //插入新元素
    for (iter = ms.begin(); iter != ms.end(); iter++)
        cout << iter->first << " " << iter->second << endl;
    cout << endl;
    iter = ms.lower_bound(1); //首个大于等于1的元素
    cout << iter->second << endl;
    iter = ms.upper_bound(1); //首个大于1的元素
    cout << iter->second << endl;
    iter = ms.find(1); //查找键值为1的元素位置
    ms.erase(iter);    //删除键值为1的元素
    for (iter = ms.begin(); iter != ms.end(); iter++)
        cout << iter->first << " " << iter->second << endl;
    ms.erase(ms.begin(), ms.end()); //删除全部元素
    cout <<"size: "<< ms.size() << endl;
    cout <<"empty: "<< ms.empty() << endl;// empty()判断map是否为空
    return 0;
}

结果：

1 student_two
2 student_three
3 student_four

student_two
student_three
2 student_three
3 student_four
size: 0
empty: 1

#include 
using namespace std;

struct Info{ //学生信息结构体
    char *xm; //姓名
    int y;    //年份
    char *d;  //地址
};

struct Record {//学生记录结构体
    int id;  //学号作键值
    Info sf; //学生信息作映照数据
};

int main(){
    Record srArray[] ={
            {4, "Li", 21, "beijing"},
            {2, "wang", 29, "shanghai"},
            {3, "zhang", 30, "shengzheng"}};
    map> m; //按键值由大到小排序
    for (int j = 0; j < 3; j++)     //装入三个学生信息
        m[srArray[j].id] = srArray[j].sf;
    Record s1 = {5, "Ling", 23, "XINJIANG"};
    m.insert(make_pair(s1.id, s1.sf)); //插入新生信息
    map::iterator i;
    for (i = m.begin(); i != m.end(); i++) //正向遍历
        cout << (*i).first << ' ' << (*i).second.xm << ' ' << (*i).second.d << 'n';
    i = m.find(2); //查找键值为2的记录并输出
    cout << "Key value 2: " << (*i).second.xm << ' ' << (*i).second.d;
    return 0;
}

结果：

5 Ling XINJIANG
4 Li beijing
3 zhang shengzheng
2 wang shanghai
Key value 2：wang shanghai

10. multimap 多重映射容器

multimap 与 map 的功能基本相同，唯独不同的是multimap 允许插入重复键值的元素，由于允许插入重复键值的元素，因此multimap 的元素插入、删除以及查找与map不同。

#include  //使用万能头文件，无需写#include 

结果：

Kity 200
Memi 500
Not find it!

---

【STL编程】【竞赛常用】【part 3】 敬请期待！！！ 11. list 双向链表容器 12. stack 堆栈容器 13. queue 队列容器 14. deque 双端队列容器 15. priority_queue 优先队列容器