c++STL容器（看这一篇就够）

string容器的基本概念

string容器的基本概念：
c风格字符串（以空字符结尾的字符数组 char *str）太过复杂难于掌握，不适合大程序的开发，所以c++标准库定义了一种string类，定义在头文件。
对比：
char * 是一个指针,String 是一个类
string封装了char * ， 管理这个字符串，是一个char型的容器
不用考虑内存释放和越界
string管理char *, 所分配的内存
如果对char * 和 char **, char [] , char *[], 的区别有疑问的话，可以去看这篇文章
点击跳转至文章 ： char *, char **,char a[] ,char *a[]啥啥分不清楚？

string容器常用操作

构造函数和赋值

#include<bits/stdc++.h>
#include<string>
using namespace std ;

void test01(){
    string str1("hello world"); // string(const char* s)
    cout << str1 << endl ;
    string str2(5,'A');//5个A
    cout << str2 <<endl;
    string str3 = str2 ;
    cout << str3 << endl;

    string str4;
    str4 = "xlx";
    cout << str4<< endl;
    str4 = 'h'; //会自动释放掉“xlx”的空间
    cout << str4 <<endl;

    str4.assign("hello world" , 5);//前五个
    cout << str4 << endl;

    str4.assign(str1,2,3);//起点 ， 宽度
    cout << str4 << endl ;
}
int main()
{
    test01();
    char *a = "hello i am *a" ;
    cout << a ;
    return 0 ;
}

存取字符操作

void test02()
{
    string s1 = "hello world";
    cout << s1[1] << " " << s1.at(1) << endl ;
    s1[1] = 'E';
    s1.at(6) = 'H';
    cout << s1 << endl ;

    // []越界不会抛出异常 at越界会抛出异常
    try{
        //s1[1000] = 'A';
        s1.at(1000) = 'A';
    }
    catch(exception &e){
        cout << "捕获到异常：" << e.what() << endl;
    }
}

拼接操作

void test03()
{
    string s1 = "hello";
    s1 += " world" ;
    cout << s1 << endl ;

    string s2 = "hehe";
    s1 += s2 ;
    cout << s1 << endl ;

    string s3 = "hello";
    string s4 = "world";
    cout << s3 + s4 <<endl;

    //append 追加
    string s5 = "hello";
    string s6 = "world";
    s5.append(s6,2,3);//下标2 长度3 rld
    cout << s5 << endl;
    s5.append("xlxniubi666" ,3 ); //前三个
    cout << s5 <<endl;

}

查找和替换

void test04()
{
    string s1 = "http://www.sex.sex.999.com";
    while(1)
    {
        int ret = s1.find("sex");
        if(ret == -1) break;
        s1.replace(ret,3,"&&&");// 可以是&&&& &&& && 多少都行，会自动增多减少
    }
}

比较

void test05()
{
    string s1 = "hehe";
    string s2 = "haha";
    if(s1.compare(s2) > 0) cout << ">" << endl; // >
    else if(s1.compare(s2) == 0) cout << "=" << endl;
    else cout << "<" <<endl;
}

提取子串

void test06()
{
    string s1 = "hehehe:hahaha:xixixi:lalala";
    int pos = 0 ;
    while(1)
    {
        int ret = s1.find(":" , pos);
        if(ret < 0)
        {
            string temp = s1.substr(pos,s1.size() - pos);
            cout << temp << endl;
            break;
        }
        string temp = s1.substr(pos,ret-pos);
        cout << temp << endl ;
        pos = ret + 1 ;
    }


}

插入和删除操作

void test07()
{
    string s1 = "hello world";
    s1.insert(0,3,'x');
    cout << s1 << endl;
    s1.insert(0,"lll");
    cout << s1 << endl;
    s1.erase(0,6);
    cout << s1 << endl ;
}

vector容器

vector的概述

vector是动态空间，随着元素的加入，它的内部机制会自动扩充空间以容纳新元素。（单端动态数组容器）

• push_back 尾部插入元素
• pop_back 尾部删除元素
• front 头元素
• back 尾元素
• begin 容器的其实迭代器
• end 得到的是结束迭代器，尾元素的下一个元素位置

void test01(){
    vector<int> a;
    a.push_back(10);
    a.push_back(20);
    a.push_back(30);
    a.push_back(40);
    a.push_back(50);

    //遍历容器
    //定义一个迭代器 保存首元素的位置
    vector<int>::iterator it = a.begin();
    for(;it!=a.end();it++) //对迭代器取*是<>里的内容
    {
        cout << *it << " ";
    }
}

vector的未雨绸缪机制

所谓的动态增加大小：并不是在原空间之后续接新空间（因为无法保证原空间之后尚有可配置的空间），而是一块更大的内存空间，然后将原数据拷贝新空间，并释放原空间。

void test01(){
    vector<int> a;
    cout << "容量："<< a.capacity() << "大小：" << a.size()<<endl;
    vector<int>::iterator it ;
    int cnt = 0 ;
    for(int i = 1 ; i <= 10;i++)
    {
        a.push_back(1);
        if(it!=a.begin())
        {
            cnt++;
            cout<< "第" << cnt << "次开辟空间，容量为： " << a.capacity() << "大小为： " << a.size() <<endl;
        }
    }
}

vector的API（编程接口）

构建函数

void printVector(vector<int>&v)
{
    vector<int>::iterator it;
    for(it = v.begin();it!= v.end();it++) cout << *it << " " ;
    cout << endl;
}
void test01(){
    vector<int> a(5,100);
    printVector(a);
    vector<int> b = a ;
    printVector(b);
    vector<int>c(a.begin(),a.end());
    printVector(c);
}

赋值操作

void printVector(vector<int>&v)
{
    vector<int>::iterator it;
    for(it = v.begin();it!= v.end();it++) cout << *it << " " ;
    cout << endl;
}
void test01(){
    vector<int> a(5,100);
    printVector(a);
    vector<int> b = a ;
    printVector(b);
    vector<int>c(a.begin(),a.end());
    printVector(c);
    vector<int>d;
    // d = c;
    d.assign(10,10);
    printVector(d);
    //交换  不管vector的大小是否一致，都可以进行交换
    c.swap(d);
    printVector(c);
    printVector(d);
}

大小操作

size 返回容器中元素的个数
empty 判断容器是否为空
reserve 预留一定的空间

void test01(){
    vector<int>e(10,30);
    cout << "大小： " << e.size() << " 容量： "<<e.capacity() << endl;
    printVector(e);
    e.resize(20);//过大补0
    //e.resize(20,50); 过大补50
    printVector(e);
}

插入删除操作

void test01(){
    vector<int>a;
    a.push_back(10);
    a.push_back(20);
    a.push_back(30);
    a.push_back(40);
    a.push_back(50);
    cout << "头元素： " << a.front() << " 尾元素： " << a.back() <<endl;
    cout << a.at(1) << " " << a[1] << endl; // at越界会抛出异常 【】不会
    a.insert(a.begin() + 2 , 3 , 500);// 10 20 500 500 500 30 40 50
    printVector(a);
    a.erase(a.begin()+2,a.begin()+5);
    printVector(a) ;
    a.clear();
    cout << "大小 " << a.size() << " 容量： " << a.capacity() << endl ;
}

巧用swap收缩空间

void test01(){
    vector<int>a;
    a.reserve(1000);
    a.assign(5,100);
    cout << "大小 " << a.size() << " 容量： " << a.capacity() << endl ;
    vector<int>(a).swap(a);
    cout << "大小 " << a.size() << " 容量： " << a.capacity() << endl ;
}

嵌套容器

void test01(){
    vector<int>a(5,10);
    vector<int>b(5,100);
    vector<int>c(5,1000);
    //需求：定义一个容器，存放a,b,c
    vector<vector<int>> v;
    v.push_back(a);
    v.push_back(b);
    v.push_back(c);
    vector<vector<int>>::iterator it;
    for(it = v.begin() ; it != v.end();it++)
    {
        //*it = vector<int>
        vector<int>::iterator mit;
        for(mit = (*it).begin();mit!=(*it).end();mit++)
        {
            //*mit == int
            cout << *mit << " " ;
        }
        cout << endl ;
    }
}

deque容器

概述

deque ：双端动态数组
vector容器是单向开口的连续内存空间，deque则是一种双向开口的连续线性空间。所谓的双向开口，意思就是可以在头尾两部分别做元素的插入和删除操作。

图表解释

deque容器和vector容器最大的差异：

1. deque允许使用常数项时间对头端进行元素的插入和删除工作
2. deque没有容量的概念

如果迭代器能+1，那么该迭代器为随机访问迭代器

void test01(){
    deque<int>a;
    a.push_back(1);
    a.push_back(2);
    a.push_back(3);
    a.push_front(4);
    a.push_front(5);
    a.push_front(6);
    printfDeque(a);//6 5 4 1 2 3
    cout << "大小：" << a.size() << endl; 
    a.pop_front();
    printfDeque(a);//5 4 1 2 3
    a.pop_back();
    printfDeque(a);//5 4 1 2
    a.insert(a.begin()+1,3,100);
    printfDeque(a);//5 100 100 100 4 1 2
    
}

stack容器

stack是一种先进后出的数据结构，它只有一个出口。
有元素推入栈的时候的操作称为：push，将元素推出stack的操作称pop；

栈容器没有迭代器，不支持遍历行为

void test01(){
    stack<int>a;
    a.push(10);
    a.push(20);
    a.push(30);
    a.push(40);
    a.push(50);
    if(!a.empty())
    {
        cout << "栈的大小： " << a.size()<<endl;
        int cnt = 0 ;
        while(!a.empty())
        {
            cout << a.top() << " " ;
            cnt ++ ;
            a.pop();
        }
        cout << endl ;
        cout << "弹出" <<cnt << endl;
    }

}

queue容器

queue是一种先进先出的数据结构

出数据的一方叫对头，入数据的一方叫队尾

void test01(){
    queue<int>a;
    a.push(10);
    a.push(20);
    a.push(30);
    a.push(40);
    a.push(50);
    if(!a.empty())
    {
        cout << "队列的大小： " << a.size()<<endl;
        while(!a.empty())
        {
            cout << a.front() << " " ;
            a.pop();
        }
        cout << endl ;
    }

}

list链表容器（双向循环链表）

void test01(){
    list<int>a;
    a.push_back(10);
    a.push_back(20);
    a.push_back(30);
    a.push_front(40);
    a.push_front(50);
    a.push_front(60);
    printList(a);//60 50 40 10 20 30
    //list容器 是双向迭代器 不支持+2
    //a.insert(a.begin()+2,3,100);
    list<int>::iterator it = a.begin();
    it++;
    it++;
    a.insert(it,3,100);//60 50 100 100 100 40 10 20 30

    //删除所有100
    a.remove(100);
    printList(a);//60 50 40 10 20 30

    //对链表排序
    //sort(a.begin(),a.end());不支持
    //stl提供的算法 只支持 随机访问迭代器 而list是双向迭代器 所以sort不支持list
    a.sort();
    printList(a);//10 20 30 40 50 60
}

set容器

set容器只有键值，在插入数据的时候，自动根据键值排序，不允许有相同键值
不能修改set容器的元素值，会破坏set的数据结构。set容器的迭代器是只读迭代器。

set常用API

void printSet(set<int> &x)
{
    set<int>::iterator it;
    for(it = x.begin() ; it != x.end(); it++)
    {
        cout<< *it << " " ;
    }
    cout << endl ;
}
void test01(){
    set<int>a;
    a.insert(30);
    a.insert(10);
    a.insert(50);
    a.insert(20);
    a.insert(40);
    printSet(a);
}

更改set容器的排序规则（定义set容器时 修改）

set<int，排序规则>a
一般都是通过“仿函数“修改set容器的排序规则

#include<bits/stdc++.h>
using namespace std ;
class MyCompare
{
public:
    bool operator()(int v1, int v2)
    {
        return v1 > v2 ;
    }
};
void printSet(set<int,MyCompare> &x)
{
    set<int,MyCompare>::iterator it;
    for(it = x.begin() ; it != x.end(); it++)
    {
        cout<< *it << " " ;
    }
    cout << endl ;
}
void test01(){
    set<int,MyCompare>a;
    a.insert(30);
    a.insert(10);
    a.insert(50);
    a.insert(20);
    a.insert(40);
    printSet(a);
}

int main()
{
    test01();
    return 0 ;
}

如果set容器存放自定义数据 必须更改排序规则

这里的重载运算符，就是因为是num,name,score都是私有的，所以重载<<让三个元素都能输出出来
如果重载运算符不太懂的话，点进来吧！

#include<bits/stdc++.h>
using namespace std ;
class Person
{
    friend class MyComparePerson;
    friend ostream& operator<<(ostream &out, Person ob);
private:
    int num ;
    string name;
    float score;
public:
    Person(){}
    Person(int num ,string name, float score)
    {
        this->num=num;
        this->name=name;
        this->score=score;
    }
};
ostream& operator<<(ostream &out, Person ob)
{
    out << ob.num << " " << ob.name << " " << ob.score << endl;
    return out;
}
class MyComparePerson
{
public:
    bool operator()(Person ob1 , Person ob2)
    {
        return ob1.num < ob2.num ;

    }
};
void printSet(set<Person,MyComparePerson> &x)
{
    set<Person,MyComparePerson> ::iterator it;
    for(it = x.begin() ; it != x.end(); it++)
    {
        cout<< (*it) << " " ;
    }
    cout << endl ;
}
void test02()
{
    set<Person,MyComparePerson> s1;
    s1.insert(Person(100,"lucy",88.8f));
    s1.insert(Person(104,"bob",99.9f));
    s1.insert(Person(103,"tom",77.8f));
    s1.insert(Person(102,"xlx",66.8f));
    printSet(s1);
}

int main()
{
    test02();
    return 0 ;
}

查找操作

• find(key) 查找键key是否存在，若存在，返回该键的元素的迭代器；若不存在，返回set.end();
• count(key); 查找键值key的元素个数
• lower_bound(keyElem) 返回第一个key>=keyElem元素的迭代器
• upper_bound(keyElem) 返回第一个key>keyElem元素的迭代器
• equal_bound(keyElem) 返回容器中key与keyElem相等的上下限的两个迭代器

void test03()
{
    set<int>a;
    a.insert(10);
    a.insert(20);
    a.insert(30);
    a.insert(40);
    a.insert(50);
    set<int>::const_iterator it ;
    it = a.find(50);
    if(it != a.end()) cout << "找到了是：" << *it << endl;
    cout << a.count(10) << endl;
    set<int>::const_iterator it1 ;
    it1 = a.lower_bound(30);
    cout << "it1返回的是： " << *it1 <<endl;
    set<int>::const_iterator it2 ;
    it2 = a.upper_bound(30);
    cout << "it2返回的是： " << *it2 <<endl;
    pair<set<int>::const_iterator,set<int>::const_iterator> it3 ; //返回值是pair 队组
    it3 = a.equal_range(30);
    cout << "it1返回的是： " << *(it3.first)  << " " << *(it3.second)<<endl;
}

multiset

void print(multiset<int> &x)
{
    multiset<int>::iterator it;
    for(it = x.begin();it!=x.end();it++)
    {
        cout << *it << " " ;
    }
    cout << endl ;
}
void test()
{
    multiset<int>a;
    a.insert(10);
    a.insert(10);
    a.insert(10);
    a.insert(20);
    a.insert(30);
    print(a);
    cout << a.count(10) <<endl;
}

pair队组

对组将一对数值合成一个值，这一对值可以具有不同的数据类型，两个值可以分别用pair的两个共有属性first和second访问。

void test()
{
    //方式一
    pair<int,string> p1(10086,"移动");
    pair<int,string> p2(10010,"联通");
    pair<int,string> p3(10000,"电信");
    //方式二
    pair<int,string> p4 = make_pair(9527,"星爷");
    cout << p4.first << " " << p4.second << endl;
}

map容器

#include<bits/stdc++.h>
using namespace std ;
void test()
{

}
int main()
{
    map<int,string> person;
    //赋值
    person[0] = "xlx01";

    person.insert(pair<int,string>(1,"xlx02"));
    person.insert(pair<int,string>(1,"xlx03"));
    //读取
    //1
    map<int,string>::iterator it ;
    //key值重复是插不进去的
    for(it = person.begin(); it != person.end();it++)
    {
        //cout << (*it).first << " " << (*it).second <<endl;
        cout << it->first << " " << it->second << endl;
    }
    //2
    for(auto it = person.begin(); it!=person.end();it++)
    {
         cout << it->first << " " << it->second << endl;
    }
    //3
    for(auto x : person)
    {
        cout << x.first << " " << x.second<<endl;
    }
    //获取map中的元素
    map<int,string>::iterator it1;
    it1 = person.find(1);//返回的是迭代器
    if(it1 != person.end())
    {
        cout << it1->second<<endl;
    }
    else cout << "not find" << endl ;

    //删除元素的方法
    map<int,string>::iterator it2;
    it2 = person.find(1);
    person.erase(it2);
    cout << person[1] <<endl;//空的
    
    
    return 0 ;
}

unordered_map

map是基于红黑树实现的
unordered_map则是哈希表
所以map会对键值自动排序，而对于unordered_map则查找效率更高
map和unordered_map在insert的时候，如果键值重复，就会保留最初的键值的键值，而数组形式操作的时候将会覆盖掉

#include<bits/stdc++.h>
using namespace std;
int main()
{
    map<int,string>a;
    unordered_map<int,string>b;
    a.insert({1,"xlx1"});
    a.insert({2,"xlx2"});
    a.insert({2,"xlx3"});
    b.insert({1,"hyy1"});
    b.insert({2,"hyy2"});
    b.insert({2,"hyy3"});
    for(auto x : a)
    {
        cout << x.first << " " << x.second << endl;
    }
    for(auto x : b)
    {
        cout << x.first << " " << x.second << endl;
    }
    return 0 ;
}