一、顺序容器
 1.1、vector
1.2、dequeue
1.3、list
二、关联性容器
 2.3、set
2.3、map
三、算法
 3.1、遍历算法(for_each)
3.2、查找算法(find，find_if)
3.3、统计算法(count，count_if)
3.4、排序算法(sort)
简单应用
 字符串切割
 字符串替换

顺序容器

1.vector容器

底层结构：数组

数据特性：

	· 随机访问

	· 随机插入和删除

	· 动态扩充容量(效率不高)

		1. 新建一片新的更大的空间

		2. 将原数据拷贝至新空间(通过插入扩容时，会多申请预留空间)

		3. 回收原空间

简单案例

void myPring(int val) {

    cout << val << '\t';

}

void test01() {

    vector<int> v;

    v.push_back(10);

    v.push_back(12);

    v.push_back(13);

    v.push_back(20);

    v.push_back(22);

    v.push_back(25);

    cout << "test01：\n";

    //访问迭代器

    //起始迭代器，指向第一个元素  v.end()结束迭代器，指向最后一个元素的下一个元素

//    vector<int>::iterator itBegin = v.begin();

    //vector<int>::iterator itEnd = v.end();

    //第一种遍历

//    while (itBegin != v.end()) {

//        cout << *itBegin << '\t';

//        itBegin++;

//    }

//    //第二种遍历

//    for (vector<int>::iterator b = v.begin(); b != v.end(); ++b) {

//        cout << *b << '\t';

//    }

    //第三种遍历

    //       头          尾       打印函数

    for_each(v.begin(), v.end(), myPring);//需要包含标准算法头文件

    v.at(1) = 5;

    //find(v.begin(), v.end(), 5);

    vector<int> *p = new vector<int>;

    (*p).push_back(1);

    delete p;

}

void test02() {

    vector<int> v;

    int *p = NULL;

    int num = 0;

    //去掉这一行，申请次数明显增加

    v.reserve(1000);//通过预留空间可以减少动态申请空间的次数

    for (int i = 0; i < 1000000; ++i) {

        v.push_back(i);

        if (p != &v.front()) {

            ++num;

            p = &v.front();

        }

    }

    cout << "动态申请了" << num << "次\n";

}

resize策略： 通常来说，如果resize的大小大于原有的size，则会申请一块更大的空间，并且将原有的元素按顺序移动到新的空间上；如果小于原有的size，则不会移动，capacity也不会变，只是可访问空间受限
resize(n)的逻辑是将capacity扩大至max( n，capacity * 2)
shrink_to_fit： 释放多余的容量，使得size=capacity，同样也会移动位置

2.dequeue容器

底层结构：一个中央控制器和多个缓冲区

数据特性：

	· 随机访问

	· 快速头尾访问

图片来源(https://www.bilibili.com/read/cv10715996)

3.list容器

底层结构：双向循环链表

数据特性：

	随机快速增加删除

	扩容速度快

简单案例

//排序规则

inline bool Compare(int &v1, int &v2) {

    return v1 > v2;  //要求v1 > v2,即降序

}

void testList() {

    list<int> L1;

    L1.push_back(10);

    L1.push_back(8);

    L1.push_back(9);

    L1.push_back(15);

    L1.push_back(7);

    L1.push_back(20);

    L1.push_back(13);

    L1.push_back(5);

    L1.push_back(6);

    for (int &x: L1) {

        cout << x << '\t';

    }

    L1.reverse();//翻转函数

    cout << "\n反转后：";

    for (int &x: L1) {

        cout << x << '\t';

    }

    cout << "\n排序：";

    //不支持随机访问的容器无法用标准算法

    L1.sort();//默认升序排列

    //L1.sort(Compare);//降序  括号内包含的是排序规则

    for (int &x: L1) {

        cout << x << '\t';

    }

}

关联性容器

4.set

底层结构：二叉树

数据特性：

	不可重复

	查找速度快

	根据键值自动排序

与multiset区别：

	multiset键值不唯一

案例：

void testSet() {//集合

    set<int> S1;

    S1.insert(1);

    S1.insert(5);//set没有push_back

    S1.insert(3);

    S1.insert(1);

    for (const int &x: S1) {

        cout << x << '\t';

    }//不允许重复且会自动排序

    //返回值第一个是迭代器，指向插入的位置，第二个是布尔

    pair<set<int>::iterator, bool> ret = S1.insert(10);

    if (ret.second) {

        cout << "插入成功\n";

    }

    S1.erase(1);//删除1

    multiset<int> S2;//允许重复

    //只返回迭代器，指向插入的位置，不返回布尔

    multiset<int>::iterator it = S2.insert(100);

    S2.insert(5);

    cout << "mul:\t";

    for (const int &x: S2) {

        cout << x << '\t';

    }

    set<int, MyCompare> S3;

    S3.insert(1);

    S3.insert(5);//set没有push_back

    S3.insert(3);

    S3.insert(1);

    for (set<int, MyCompare>::iterator it = S3.begin(); it != S3.end(); ++it) {

        cout << *it << '\t';

    }

}

class Person {

public:

    string name;

    int age;

    float height;

    friend ostream &operator<<(ostream &os, const Person &p) {

        os << p.name << '\t' << p.age << '\t' << p.height;

        return os;

    }

    Person(string n, int a, float h) : name(std::move(n)), age(a), height(h) {

    }

};

class comparePerson {

public:

    bool operator()(const Person &p1, const Person &p2) const {

        return p1.age > p2.age;

    }

};

void testSet1() {

    set <Person, comparePerson> *p = new set<Person, comparePerson>;//利用仿函数自定义排序方式

    Person P1("张飞", 50, 1.85);

    Person P2("曹操", 65, 1.70);

    Person P3("关羽", 50, 1.82);

    Person P4("刘备", 55, 1.75);

    Person P5("曹丕", 40, 1.73);

    Person P6("赵云", 44, 1.78);

    Person P7("孙权", 46, 1.81);

    Person P8("小乔", 40, 1.65);

    Person P9("周瑜", 40, 1.76);

    //在插入自定义的数据类型时，需要指定规则

    p->insert(P1);

    p->insert(P2);

    p->insert(P3);

    p->insert(P4);

    p->insert(P5);

    p->insert(P6);

    p->insert(P7);

    p->insert(P8);

    p->insert(P9);

    for (const Person & it : *p) {

        cout << it << '\n';

    }

delete p;

}

5.map

底层结构：红黑树

数据特性：

	查找速度快

	所有的元素都是pair

	根据键值自动排序

与multimap区别：

	multimap键值不唯一

案例：

void testMap() {

    //会根据key值自动排序，如果要修改排序规则，和set一样用仿函数

    map<int, int> M;

    M.insert(pair<int, int>(1, 10));//map中的成员为pair

    M.insert(pair<int, int>(5, 50));//map中的成员为pair

    M.insert(pair<int, int>(6, 60));//map中的成员为pair

    M.insert(pair<int, int>(3, 30));//map中的成员为pair

    M.insert(pair<int, int>(2, 20));//map中的成员为pair

    //M.insert(2, 20);

    printMap(M);

    map<int, int> M1(M);//拷贝构造

    cout << "M1:\n";

    //printMap(M1);

    cout << "size:" << M1.size() << '\n';

    //删除,删除后size不会变

    M.erase(M.begin());//用迭代器删除

    M.erase(3);//用Key删除

    printMap(M);

    cout << "size:" << M1.size() << '\n';

    //M.erase(M.begin(), M.end());//与之前容器一样，区间删除

    //查找

    map<int, int>::iterator pos = M.find(3);

    if (pos != M.end()) {

        cout << "key=" << pos->first << "\tvalue=" << pos->second << '\n';

    } else {

        cout << "查找失败!!!\n";

    }

    //统计

    int count;//统计key=5的条数

    count = M.count(5);

}

void TestMultimap(){			//可重复键值对

    multimap<char,int>M;

    M.emplace('a',10);

    M.emplace('b',20);

    M.emplace('c',30);

    M.emplace('a',50);

    M.emplace('e',60);

    for(auto pos = M.equal_range('a'); pos.first != pos.second; ++pos.first)//查找所有键值为'a'的元素

        cout << pos.first->second << endl;

}

标准算法

1.遍历算法

for_each函数

包含头文件#include<algorithm>
for_each(src.begin() ,src.end() ,Print)

使用案例

#include <vector>

#include <algorithm>

using namespace std;

void PrintInt(int value) {

    cout << value << '\t';

}

class PrintInt1 {

public:

    void operator()(int value) {

        cout << value << '\t';

    }

};

void testFor_each() {

    vector<int> vector1;

    for (int i = 1; i < 11; ++i) {

        vector1.push_back(i);

    }

    //使用函数作为输出

    for_each(vector1.begin(), vector1.end(), PrintInt);

    cout << '\n';

    //使用仿函数输出

    for_each(vector1.begin(), vector1.end(), PrintInt1());

}

2.查找算法

find函数

包含头文件#include<algorithm>
find(src.begin() ,src.end() ,target)
查找的目标为一个区间，左闭右包
返回目标位置的迭代器，查找失败则返回src.end()

使用案例

void testFind() {

    vector<int> vector1;

    for (int i = 1; i < 11; ++i) {

        vector1.push_back(i);

    }

    vector<int>::iterator it = find(vector1.begin(), vector1.end(), 5);//查找

    if (it != vector1.end()) {

        cout << "查找成功\n";

    } else {

        cout << "查找失败\n";

    }

    auto it2 = find(vector1.begin(), vector1.end(), 50);

    if (it2 != vector1.end()) {

        cout << "查找成功\n";

    } else {

        cout << "查找失败\n";

    }

}

//查找自定义数据类型

class Person {

public:

    Person(string name, int age) {

        this->Name = move(name);

        this->Age = age;

    }

    string Name;

    int Age;

    friend ostream &operator<<(ostream &os, const Person &person) {

        os << "Name:" << person.Name << "\tAge:" << person.Age << endl;

        return os;

    }

    bool operator==(const Person &p) const {		//需要重载==符号才能进行查找

        if (p.Age == this->Age && p.Name == this->Name) {

            return true;

        }

        return false;

    }

};

vector<Person> vector2;

Person person1("aaa", 50);

Person person2("bbb", 35);

Person person3("ccc", 45);

Person person4("ddd", 38);

vector2.push_back(person1);

vector2.push_back(person2);

vector2.push_back(person3);

vector2.push_back(person4);

auto personIt = find(vector2.begin(), vector2.end(), Person("aaa", 50));

if (personIt != vector2.end()) {

     cout << "找到了person2\n";

     cout << *personIt;

 } else {

     cout << "未找到\n";

 }

find_if 函数按条件查询

包含头文件#include<algorithm>
for_each(src.begin() ,src.end() ,Func)
查找的目标为一个区间，左闭右包
符合判定条件的第一个的迭代器，查找失败则返回src.end()

使用案例

bool GreaterFive(int value) {

    return value > 100;

}

bool GreaterAge20(Person &p1) {

    return p1.Age > 20;

}

void testFind_if() {

    vector<int> vector1;

    for (int i = 1; i < 11; ++i) {

        vector1.push_back(i);

    }

    //同理，仿函数也行

    auto it10 = find_if(vector1.begin(), vector1.end(), GreaterFive);//查找大于5的数

    if (it10 != vector1.end()) {

        cout << "找到了" << endl;

    } else {

        cout << "没找到" << endl;

    }

	//自定义数据类型

    vector<Person> vector2;

    Person person5("eee", 19);

    Person person6("fff", 20);

    Person person7("ggg", 22);

    Person person8("hhh", 28);

    vector2.push_back(person5);

    vector2.push_back(person6);

    vector2.push_back(person7);

    vector2.push_back(person8);

    auto it11 = std::find_if(vector2.begin(), vector2.end(), GreaterAge20);

    if (it11 != vector2.end()) {

        cout << "找到了age>20" << endl;

    } else {

        cout << "没找到" << endl;

    }

}

3.统计算法

count函数

包含头文件#include<algorithm>
count(src.begin() ,src.end() ,target)
统计的目标为一个区间，左闭右包
返回统计的元素个数

使用案例

//内置数据类型

void testCount(){

    vector<int> V1;

    V1.push_back(3);

    V1.push_back(5);

    V1.push_back(3);

    V1.push_back(7);

    V1.push_back(8);

    V1.push_back(3);

    V1.push_back(6);

    auto num=count(V1.begin(), V1.end(), 3);

    cout<<"3的个数为:"<<num;

}

//自定义数据类型用法与find用法差不多，注意要重载 == 符号

count_if函数

包含头文件#include<algorithm>
count(src.begin() ,src.end() , Func)
统计的目标为一个区间，左闭右包
返回符合条件的元素个数

使用案例

bool Greater3(const int &p1) {

    return p1 > 3;

}

void testCount_if() {

    vector<int> V1;

    V1.push_back(3);

    V1.push_back(5);

    V1.push_back(3);

    V1.push_back(7);

    V1.push_back(8);

    V1.push_back(3);

    V1.push_back(6);

    auto num1 = count_if(V1.begin(), V1.end(), Greater3);

    cout << "大于3的元素个数：" << num1 << endl;

}

//同理，使用自定义数据类型时也和find_if相似

4.排序算法

sort函数

包含头文件#include<algorithm>
sort(src.begin() ,src.end() ,args)
排序的目标为一个区间，左闭右包，默认升序排列
无返回值

使用案例

void PrintInt(int value) {

    cout << value << '\t';

}

void testSort() {

    srand((unsigned int) time(NULL));

    vector<int> V1;

    V1.reserve(10);

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

        V1.push_back(rand() % 20 + 1);//插入随机数

    }

    sort(V1.begin(), V1.end());

    for_each(V1.begin(), V1.end(), PrintInt);

	//降序排列，使用内建的函数对象，需包含头文件  #include <functional>

	sort(V1.begin(), V1.end(), greater<int>());

    for_each(V1.begin(), V1.end(), PrintInt);

	//如果想对自定义数据类型排列，参考之前的set容器的笔记

}

radom_shuffle函数

包含头文件#include<algorithm>
radom_shuffle(src.begin() ,src.end())
洗牌算法，将区间内元素打乱
目标为一个区间，左闭右包
无返回值

使用案例

void testSort() {

    srand((unsigned int) time(NULL));//随机数种子，保证每次打乱都不一样

    vector<int> V2;

    V2.reserve(10);

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

        V2.push_back(i);

    }

    std::random_shuffle(V2.begin(), V2.end());

    std::for_each(V2.begin(), V2.end(), PrintInt);

    cout << '\n';

}

简单应用

字符串切割

/*

 * 功能: 分割字符串将字符串存入容器

 * 参数一: 待分割的字符串

 * 参数二: 分割符

 * 参数三: 容器，放置分割结果

*/

void SubStr(string &target, string pattern, vector<string> &V1) {

    size_t pos = 0;

    string buf;

    if (target.find(pattern) == target.npos) {//没有找到分隔符

        V1.push_back(target);

        return;

    }

       for (int i = 0; i < target.size(); ++i) {

           pos = target.find(pattern, i);

           if (pos < target.size()) {

               buf.assign(target.substr(i, pos - i));

               if(buf.empty()){			//如果第一个字符就为分隔符或者连续两个分隔符。跳过

                   continue;

               }

               V1.push_back(buf);

               i = pos + pattern.size() - 1;

           } else if (pos == target.npos) {//获取最后一个串

               V1.push_back(target.substr(i));

               break;

            }

    }

    for (const auto &j: V1) {

        cout << j << '\t';

    }

}

int main(){

	string target="1-2-3-4-5-6-7-8-9-10-";//尾部有分隔符

	vector<string> V1, V2, V3, V4;

	SubStr(target,"-",V1);

	cout<<'\n';

	string str1="1-2-3-4-5-6-7-8-9-10";//一般情况

	SubStr(str1,"-",V2);

	cout<<'\n';

	string str2="-1-2-3-4-5-6-7-8-9-10";//头部有分隔符

	SubStr(str2,"-",V3);

	cout<<'\n';

	string str="1-2-3-4-5--6-7-8-9-10-";//连续遇到两个分隔符

	SubStr(str,"-",V4);

}

输出结果： 1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10

字符切割重写一个船新版本

void Split(string s, const string &pat, vector<string> &V) {

  auto pos = s.find(pat);

  if (pos == string::npos) {

    V.push_back(s);

    return;

  }

  while (pos != string::npos) {

    string tmp(s.begin(), s.begin() + pos);

    if (tmp.length() != 0) {

      V.push_back(tmp);

    }

    s = s.substr(pos + pat.length());//去掉切出来的字符串

    pos = s.find(pat);

  }

  V.push_back(s);

}

字符串替换

/*

 * 功能: 替换字符串中的指定子串

 * 参数一: 目标字符串

 * 参数二: 要替换字符

 * 参数三: 目标字符

*/

void ReplaceStr(string &S, const char *src, const char *dst) {

    size_t pos = 0;

    while (true) {

        pos = S.find(src, pos);

        if (pos != std::string::npos) {

        	/*string.replace函数

        	* 1、起始替换位置; 2、需要替换的长度; 3、替换为...

        	*/

            S.replace(pos, strlen(src),dst);

        } else {

            break;

        }

    }

}

int main(){

    string S="1111212121212";

    ReplaceStr(S,"1","");

    cout<<S<<endl;

    S.assign("吃葡萄不吐葡萄皮儿");

    ReplaceStr(S, "葡萄", "橘子");

    cout << S << endl;

}

输出结果： 22222
吃橘子不吐橘子皮儿

巴特西

C++编程笔记(STL学习)