1. STL概论

长久以来,软件界一直希望建立一种可重复利用的东西,以及一种得以制造出”可重复运用的东西”的方法,让程序员的心血不止于随时间的迁移,人事异动而烟消云散,从函数(functions),类别(classes),函数库(function libraries),类别库(class libraries)、各种组件,从模块化设计,到面向对象(object oriented ),到模式(pattern)的归纳整理,为的就是复用性的提升。

复用性必须建立在某种标准之上。但是在许多环境下,就连软件开发最基本的数据结构(data structures) 和算法(algorithm)都未能有一套标准。大量程序员被迫从事大量重复的工作,竟然是为了完成前人已经完成而自己手上并未拥有的程序代码,这不仅是人力资源的浪费,也是挫折与痛苦的来源。

为了建立数据结构和算法的一套标准,并且降低他们之间的耦合关系,以提升各自的独立性、弹性、交互操作性(相互合作性,interoperability),诞生了STL。

1.1 STL基本概念

STL(Standard Template Library,标准模板库),是惠普实验室开发的一系列软件的统
称。现在主要出现在 c++中,但是在引入 c++之前该技术已经存在很长时间了。

STL 从广义上分为: 容器(container) 算法(algorithm) 迭代器(iterator),容器和算法之间通过迭代器进行无缝连接。STL 几乎所有的代码都采用了模板类或者模板函数,这相比传统的由函数和类组成的库来说提供了更好的代码重用机会。STL(Standard Template Library)标准模板库,在我们 c++标准程序库中隶属于 STL 的占到了 80%以上。

1.2 STL六大组件简介

STL提供了六大组件,彼此之间可以组合套用,这六大组件分别是:容器、算法、迭代器、仿函数、适配器、空间配置器。

容器:各种数据结构,如vector、list、deque、set、map等,用来存放数据,从实现角度来看,STL容器是一种class template。

算法:各种常用的算法,如sort、find、copy、for_each。从实现的角度来看,STL算法是一种function tempalte.

迭代器:扮演了容器与算法之间的胶合剂,共有五种类型,从实现角度来看,迭代器是一种将operator* , operator-> , operator++,operator--等指针相关操作予以重载的class template. 所有STL容器都附带有自己专属的迭代器,只有容器的设计者才知道如何遍历自己的元素。原生指针(native pointer)也是一种迭代器。

仿函数:行为类似函数,可作为算法的某种策略。从实现角度来看,仿函数是一种重载了operator()的class 或者class template

适配器:一种用来修饰容器或者仿函数或迭代器接口的东西。

空间配置器:负责空间的配置与管理。从实现角度看,配置器是一个实现了动态空间配置、空间管理、空间释放的class tempalte.

STL六大组件的交互关系,容器通过空间配置器取得数据存储空间,算法通过迭代器存储容器中的内容,仿函数可以协助算法完成不同的策略的变化,适配器可以修饰仿函数。

1.3 STL优点

  • STL 是 C++的一部分,因此不用额外安装什么,它被内建在你的编译器之内。
  • STL 的一个重要特点是数据结构和算法的分离。尽管这是个简单的概念,但是这种分离使得 STL 变得非常通用。例如:在 STL 的 vector 容器中,可以放入元素、基础数据类型变量、元素的地址;STL 的 sort() 排序函数可以用来操作 vector,list 等容器。
  • 程序员可以不用思考 STL 具体的实现过程,只要能够熟练使用 STL 就 OK 了。这样他们就可以把精力放在程序开发的别的方面。
  • STL 具有高可重用性,高性能,高移植性,跨平台的优点。
  • 高可重用性:STL 中几乎所有的代码都采用了模板类和模版函数的方式实现,这相比于传统的由函数和类组成的库来说提供了更好的代码重用机会。关于模板的知识,已经给大家介绍了。
  • 高性能:如 map 可以高效地从十万条记录里面查找出指定的记录,因为 map 是采用红黑树的变体实现的。(红黑树是平横二叉树的一种)
  • 高移植性:如在项目 A 上用 STL 编写的模块,可以直接移植到项目 B 上。

01 STL三大组件

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;


void myPrint(int v) {
    cout << v << endl;
}


//迭代器 遍历功能 用指针理解
//普通指针也算一种迭代器
void test01() {
    int array[5] = { 1,3,5,6,8 };
    int* p = array;
    
    for (int i = 0; i < 5; i++) {
        cout << *(p++) << endl;
    }
}

void test02() {
    //声明容器 
    vector<int> v; //声明一个容器 这个容器中存放int类型数据 对象名为v
    v.push_back(10);
    v.push_back(20);
    v.push_back(30);
    v.push_back(40);

    //遍历容器中的数据
    //利用迭代器

    vector<int>::iterator it = v.begin(); //指向v容器中的起始位置
    vector<int>::iterator itend = v.end();//只想v容器中的最后一个位置的下一个位置

    /*while (it != itend) {
        cout << *it << endl;
        it++;
    }
    cout << *it;*/

    //第二种遍历方式
    /*for (vector<int>::iterator it = v.begin(); it != v.end(); it++) {
        cout << *it << endl;
    }*/


    //第三种方式 利用算法
    for_each(v.begin(), v.end(), myPrint);


}


//操作自定义数据类型
class Person {
public:
    Person(string name, int age) {
        this->m_Name = name;
        this->m_Age = age;
    }

    string m_Name;
    int m_Age;
};

void test03() {
    vector<Person *> v;
    Person p1("大头儿子", 10);
    Person p2("小头爸爸", 20);
    Person p3("王叔叔", 30);
    Person p4("围裙妈妈", 140);

    v.push_back(&p1);
    v.push_back(&p2);
    v.push_back(&p3);
    v.push_back(&p4);

    for (vector<Person *>::iterator it = v.begin(); it != v.end(); it++) {
        cout << "姓名:" << (*it)->m_Name << ",年龄:" << (*it)->m_Age << endl;
    }

}

void test05() {
    vector<vector<int>> v;
    vector<int> v1;
    vector<int> v2;
    vector<int> v3;

    for (int i = 0; i < 5; i++) {
        v1.push_back(i);
        v2.push_back(i + 10);
        v3.push_back(i + 100);
    }
    
    //将小容器放入到大容器中
    v.push_back(v1);
    v.push_back(v2);
    v.push_back(v3);

    //遍历所有数据
    for (vector<vector<int>>::iterator it = v.begin(); it != v.end(); it++) {
        for (vector<int>::iterator vit = it->begin(); vit != it->end(); vit++) {
            cout << *vit << " ";
        }
    }
}

//存放自定义数据类型的指针

int main() {
    //test02();
    //test03();
    test05();
    system("pause");
}

02 string容器

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
/*
string();//创建一个空的字符串 例如: string str;      
string(conststring& str);//使用一个string对象初始化另一个string对象
string(constchar* s);//使用字符串s初始化
string(int n, char c);//使用n个字符c初始化 
string& operator=(constchar* s);//char*类型字符串 赋值给当前的字符串
string& operator=(conststring& s);//把字符串s赋给当前的字符串
string& operator=(char c);//字符赋值给当前的字符串
string& assign(constchar* s);//把字符串s赋给当前的字符串
string& assign(constchar* s, int n);//把字符串s的前n个字符赋给当前的字符串
string& assign(conststring& s);//把字符串s赋给当前字符串
string& assign(int n, char c);//用n个字符c赋给当前字符串
string& assign(conststring& s, int start, int n);//将s从start开始n个字符赋值给字符串,如s=hello,那么n=3,start=1,那么是hel中从e开始赋值3-1个字符
char& operator[](int n);//通过[]方式取字符
char& at(int n);//通过at方法获取字符
string& operator+=(conststring& str);//重载+=操作符
string& operator+=(constchar* str);//重载+=操作符
string& operator+=(constchar c);//重载+=操作符
string& append(constchar* s);//把字符串s连接到当前字符串结尾
string& append(constchar* s, int n);//把字符串s的前n个字符连接到当前字符串结尾
string& append(conststring& s);//同operator+=()
string& append(conststring& s, int pos, int n);//把字符串s中从pos开始的n个字符连接到当前字符串结尾
string& append(int n, char c);//在当前字符串结尾添加n个字符c
int find(conststring& str, int pos = 0) const; //查找str第一次出现位置,从pos开始查找
int find(constchar* s, int pos = 0) const;  //查找s第一次出现位置,从pos开始查找
int find(constchar* s, int pos, int n) const;  //从pos位置查找s的前n个字符第一次位置
int find(constchar c, int pos = 0) const;  //查找字符c第一次出现位置
int rfind(conststring& str, int pos = npos) const;//查找str最后一次位置,从pos开始查找
int rfind(constchar* s, int pos = npos) const;//查找s最后一次出现位置,从pos开始查找
int rfind(constchar* s, int pos, int n) const;//从pos查找s的前n个字符最后一次位置
int rfind(constchar c, int pos = 0) const; //查找字符c最后一次出现位置
string& replace(int pos, int n, conststring& str); //替换从pos开始n个字符为字符串str
string& replace(int pos, int n, constchar* s); //替换从pos开始的n个字符为字符串s

compare函数在>时返回 1,<时返回 -1,==时返回 0。
比较区分大小写,比较时参考字典顺序,排越前面的越小。
大写的A比小写的a小。

int compare(conststring& s) const;//与字符串s比较
int compare(constchar* s) const;//与字符串s比较
string substr(int pos = 0, int n = npos) const;//返回由pos开始的n个字符组成的字符串
string& insert(int pos, constchar* s); //插入字符串
string& insert(int pos, conststring& str); //插入字符串
string& insert(int pos, int n, char c);//在指定位置插入n个字符c
string& erase(int pos, int n = npos);//删除从Pos开始的n个字符 
//string 转 char*
string str = "itcast";
constchar* cstr = str.c_str();
//char* 转 string 
char* s = "itcast";
string sstr(s);
*/
void test01() {
    string str;//默认构造
    string str2(str);//拷贝构造
    string str3 = str;
    string str4 = "abcd";
    string str5(10, 'a');
    cout << str4 << endl;
    cout << str5 << endl;

    //string& assign(constchar * s, int n);//把字符串s的前n个字符赋给当前的字符串
    str3.assign("abcdef", 2);
    cout << str3 << endl;

    //string& append(conststring& s, int pos, int n);//把字符串s中从pos开始的n个字符连接到当前字符串结尾
    string str6;
    str = "hello";
    str6.assign(str, 1, 3);
    cout << str6;
}

void test02() {
    string s = "hello world";
    for (int i = 0; i < s.size(); i++) {
        cout << s.at(i) << endl;
    }
    //at抛异常 []直接挂掉
    try {
        cout << s.at(100) << endl;
    }
    catch (out_of_range& e) {
        cout << e.what() << endl;
    }

}

void test03() {
    //拼接
    string s1 = "我";
    string s2 = "爱北京";
    s1 += s2;
    
    s1.append("天安门");
    cout << s1 << endl;

    //find查找
    string s = "abcdefg";
    int pos = s.find("bc"); //找不到是-1
    cout << "pos = " << pos << endl;
    int pos2 = s.rfind("bc"); //rfind和find结果是一样的
    cout << "pos = " << pos;

    //替换
    string s3 = "hello";
    //string& replace(int pos, int n, conststring & str); //替换从pos开始n个字符为字符串str
    s3.replace(1, 3, "diaoren");
    cout << s3 << endl;

}

void test04() {
    string s1 = "bbbbbc";
    string s2 = "abc";
    if (s1.compare(s2) == 0) {
        cout << "相等" << endl;
    }
    else if (s1.compare(s2) == 1) {
        cout << "s1 大于 s2" << endl;
    }

    else {
        cout << "s1 小于 s2 " << endl;
    }
}


void test05() {
    string s1 = "abcde";
    string s2 = s1.substr(1, 3);
    cout << s2;

    //需求 查找一个邮件的用户名
    string email = "zhangtao@sina.com";
    int pos = email.find("@"); //
    cout << "pos = " << pos << endl;
    string userName = email.substr(0, pos);
    cout << "用户名为:" <<  userName;
}


void test06() {
    //插入
    string s1 = "hello";
    s1.insert(1, "111");
    cout << s1 << endl;

    //删除
    s1.erase(1, 3);
    cout << s1 << endl;
}

void func(string s) {
    cout << s << endl;
}


void func2(const char* s) {
    cout << s << endl;
}

//string 和 c-style 字符串转换
void test07() {
    string s = "abc";
    char a[100];
    //char* p = s.c_str();
    const char* p = s.c_str();
    cout << p;
    func(p); //const char * 可以直接转化为string
    string s2 = p;
    cout << s2;
    //func2(s2); 不可

}


void test08() {
    string s = "abcdefg";
    char& a = s[2];
    char& b = s[3];

    a = '1';
    b = '2';

    s = "ajsdlkfjlkasjdokfjlkasjdikasdfasdfasdfasdfasdfadsff";

    /*a = '1';  
    b = '2';*/ //不可如此操作因为重新分配了内存 原来a和b的内存不存在了 
    

    cout << s << endl;
    cout << (int*)s.c_str() << endl;
}


int main() {
    //test01();
    //test02();
    //test04();
    test08();
}

03 vector容器

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <list>
using namespace std;

void test01() {//观看容量的增长方式
    vector<int> v;
    for (int i = 0; i < 10; i++) {
        v.push_back(i);
        cout << v.capacity() << endl;
    }
}


void printVector(vector <int>& v) {
    for (vector<int>::iterator it = v.begin(); it != v.end(); it++) {
        cout << *it << " ";
    }
}
void test02() {
    vector<int> v;
    int arr[] = { 2,3,4,1,9 };
    vector<int> v1(arr, arr + sizeof(arr) / sizeof(int));
    vector<int> v2(v1.begin(), v1.end());
    printVector(v1);
    printVector(v2);
    vector<int> v3(10, 100);
    printVector(v3);


    //赋值使用 
    vector<int> v4;
    v4.assign(v3.begin(), v3.end());
    printVector(v4);

    v4.swap(v2);
    cout << "交换后的内容为:" << endl;
    printVector(v4);

    cout << "v4容器的大小" << v4.size() << endl;

    if (v4.empty()) {
        cout << "为空" << endl;
    }

    v4.resize(10, -1);
    printVector(v4);
    cout << "size:" << v4.size() << endl;

    v4.resize(3);
    printVector(v4);
    cout << "size:" << v4.size() << endl;
}

//巧用swap收缩空间
void test03() {
    vector<int> v;
    for (int i = 0; i < 100000; i++) {
        v.push_back(i);
    }

    cout << "size:" << v.size() << endl;
    cout << "capacity:" << v.capacity() << endl;
    //vector<int>(v).swap(v);

    v.resize(3);
    cout << "size:" << v.size() << endl;
    cout << "capacity:" << v.capacity() << endl;
    vector<int>(v).swap(v);

    cout << "size:" << v.size() << endl;
    cout << "capacity:" << v.capacity() << endl;


}
//reserve(int len) //容器预留len个元素长度,预留位置不初始化,元素不可访问。
void test04() {
    vector<int> v;
    v.reserve(100000); //预留100000空间
    int* p = NULL;
    int num = 0;
    for (int i = 0; i < 100000; i++) {
        v.push_back(i);
        if (p != &v[0]) {
            p = &v[0];
            num++;
        }
    }

    cout << num << endl;
    //开辟100000数据用了多少次
    
}


void test05() {
    vector<int> v;
    v.push_back(10);
    v.push_back(20);
    v.push_back(30);
    v.push_back(50);
    
    cout << "v.front() :" << v.front() << endl;
    cout << "v.back() : " << v.back() << endl;

    v.insert(v.begin(), 2, 100); //参数1 迭代器  参数2 插入个数 参数3 插入值
    printVector(v);

    v.pop_back();
    printVector(v);

    //v.erase(v.begin(), v.end());
    //v.clear();
    if (v.empty()) {
        cout << "为空" << endl;
    }
}

void test06() {
    //逆序遍历
    vector<int> v;
    for (int i = 0; i < 10; i++) {
        v.push_back(i);
    }


    for (vector<int>::reverse_iterator it = v.rbegin(); it != v.rend(); it++) {
        cout << *it << endl;
    }

    //vector支持跳跃式访问 其迭代器是随机访问的迭代器
    vector<int>::iterator itBegin = v.begin();
    itBegin += 3;
    //如果上述写法不报错,这个迭代器是随机访问迭代器

    list<int> l;
    for (int i = 0; i < 10; i++) {
        l.push_back(i);
    }

    //list<int>::iterator it = l.begin();
    //it = it + 1; //报错

}

int main() {
    test04();
    system("pause");
}

04 deque容器

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <deque>
using namespace std;
/*
deque<T> deqT;//默认构造形式
deque(beg, end);//构造函数将[beg, end)区间中的元素拷贝给本身。
deque(n, elem);//构造函数将n个elem拷贝给本身。
deque(const deque& deq);//拷贝构造函数。
assign(beg, end);//将[beg, end)区间中的数据拷贝赋值给本身。
assign(n, elem);//将n个elem拷贝赋值给本身。
deque& operator=(const deque& deq); //重载等号操作符 
swap(deq);// 将deq与本身的元素互换
deque.size();//返回容器中元素的个数
deque.empty();//判断容器是否为空
deque.resize(num);//重新指定容器的长度为num,若容器变长,则以默认值填充新位置。如果容器变短,则末尾超出容器长度的元素被删除。
deque.resize(num, elem); //重新指定容器的长度为num,若容器变长,则以elem值填充新位置,如果容器变短,则末尾超出容器长度的元素被删除。
push_back(elem);//在容器尾部添加一个数据
push_front(elem);//在容器头部插入一个数据
pop_back();//删除容器最后一个数据
pop_front();//删除容器第一个数据


at(idx);//返回索引idx所指的数据,如果idx越界,抛出out_of_range。
operator[];//返回索引idx所指的数据,如果idx越界,不抛出异常,直接出错。
front();//返回第一个数据。
back();//返回最后一个数据
insert(pos, elem);//在pos位置插入一个elem元素的拷贝,返回新数据的位置。
insert(pos, n, elem);//在pos位置插入n个elem数据,无返回值。
insert(pos, beg, end);//在pos位置插入[beg,end)区间的数据,无返回值。
clear();//移除容器的所有数据
erase(beg, end);//删除[beg,end)区间的数据,返回下一个数据的位置。
erase(pos);//删除pos位置的数据,返回下一个数据的位置。

*/

void printDeque(const deque<int>& d) {
    for (deque<int>::const_iterator it = d.begin(); it != d.end(); it++) {
        cout << *it << endl;
    }
}

void test01() {
    deque<int> d;
    d.push_back(10);
    d.push_back(40);
    d.push_back(20);
    d.push_back(30);
    printDeque(d);
    deque<int> d2(d.begin(), d.end());
    d2.push_back(10000);

    d.swap(d2);
    cout << endl;
    printDeque(d);

    if (d2.empty()) {
        cout << "为空" << endl;
    }

    else {
        cout << "不为空 大小为:" << d.size() << endl;
    }
}

void test02() {
    deque<int> d;
    d.push_back(10);
    d.push_back(20);
    d.push_back(30);
    d.push_back(100);
    d.push_back(50);
    printDeque(d);

    d.pop_back();
    d.pop_front();
    printDeque(d);

    cout << "d.front() :" << d.front() << endl;
    cout << "d.back() :" << d.back() << endl;

    //插入
    deque<int> d2;
    d2.push_back(50);
    d2.push_back(60);
    d2.insert(d2.begin(), d.begin(), d.end());
    printDeque(d2);
}

void test03() {
    deque<int> d;
    d.push_back(10);
    d.push_back(20);
    d.push_back(30);
    d.push_back(100);
    d.push_back(50);
    printDeque(d);
    
    deque<int>::iterator it= d.erase(d.begin());
    cout << *it << endl;
}

int main() {
    test03();
    system("pause");
}

05 评委打分案例

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <deque>


using namespace std;

class Person {
public:
    Person(string name, int score) {
        this->m_name = name;
        this->m_score = score;
    }
    string m_name;
    int m_score;

    
};


void setScore(vector<Person>& v) {
    for (vector<Person>::iterator it = v.begin(); it != v.end(); it++) {
        //对5个人进行打分
        deque<int> d;
        for (int i = 0; i < 10; i++) {
            int score = rand() % 41 + 60;
            d.push_back(score);
        }

        //先看下打分
        /*for (deque<int>::iterator dit = d.begin(); dit != d.end(); dit++) {
            cout << *dit << " ";
        }*/
        sort(d.begin(), d.end()); //从小到大
        d.pop_back();
        d.pop_front();

        int sum = 0;
        for (deque<int>::iterator dit = d.begin(); dit != d.end(); dit++) {
            sum += *dit;
        }

        //平均分
        int avg = sum / d.size();
        it->m_score = avg;
    }
}
void createPerson(vector<Person>& v) {
    string nameSeed = "ABCDE";
    for (int i = 0; i < 5; i++) {
        string name = "选手";
        name += nameSeed[i];
        int score = 0;
        Person p(name, score);
        v.push_back(p);
    }
}

void showScore(vector<Person>& v) {
    for (vector<Person>::iterator it = v.begin(); it != v.end(); it++) {
        cout << "姓名:" << it->m_name << ",最终平均分:" << it->m_score << endl;
    }
}

int main() {
    //srand((unsigned int)time(NULL));
    //创建容器
    vector<Person> v;
    createPerson(v);
    setScore(v);
    showScore(v);
    int i;
    for (i = 0; i < 10; i++) printf("%d ", rand() % 100 + 1);
    system("pause");

    
}

06 stack容器

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <deque>
#include <stack>
using namespace std;

void test01() {
    stack<int> s;
    s.push(10);
    s.push(20);
    s.push(30);
    s.push(40);
    while (s.size()) {
        cout << "栈顶为:" << s.top() << endl;
        s.pop();
    }

    cout << "size = " << s.size() << endl;
}

int main() {
    test01();
}

07 queue容器

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <deque>
#include <queue>
using namespace std;

void test01() {
    queue<int> q; //先进先出
    q.push(10);
    q.push(20);
    q.push(30);
    q.push(40);
    while (!q.empty()) {
        cout << "q.front():" << q.front() << endl;
        cout << "q.back():" << q.back() << endl;
        q.pop();
    }




}


int main() {
    test01();
}

08 list容器

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<list>
using namespace std;


/*
list<T> lstT;//list采用采用模板类实现,对象的默认构造形式:
list(beg,end);//构造函数将[beg, end)区间中的元素拷贝给本身。
list(n,elem);//构造函数将n个elem拷贝给本身。
list(const list &lst);//拷贝构造函数。
3.6.4.2 list数据元素插入和删除操作
push_back(elem);//在容器尾部加入一个元素
pop_back();//删除容器中最后一个元素
push_front(elem);//在容器开头插入一个元素
pop_front();//从容器开头移除第一个元素
insert(pos,elem);//在pos位置插elem元素的拷贝,返回新数据的位置。
insert(pos,n,elem);//在pos位置插入n个elem数据,无返回值。
insert(pos,beg,end);//在pos位置插入[beg,end)区间的数据,无返回值。
clear();//移除容器的所有数据
erase(beg,end);//删除[beg,end)区间的数据,返回下一个数据的位置。
erase(pos);//删除pos位置的数据,返回下一个数据的位置。
remove(elem);//删除容器中所有与elem值匹配的元素。


3.6.4.3 list大小操作
size();//返回容器中元素的个数
empty();//判断容器是否为空
resize(num);//重新指定容器的长度为num,
若容器变长,则以默认值填充新位置。
如果容器变短,则末尾超出容器长度的元素被删除。
resize(num, elem);//重新指定容器的长度为num,
若容器变长,则以elem值填充新位置。
如果容器变短,则末尾超出容器长度的元素被删除。

3.6.4.4 list赋值操作
assign(beg, end);//将[beg, end)区间中的数据拷贝赋值给本身。
assign(n, elem);//将n个elem拷贝赋值给本身。
list&operator=(const list &lst);//重载等号操作符
swap(lst);//将lst与本身的元素互换。
3.6.4.5 list数据的存取
front();//返回第一个元素。
back();//返回最后一个元素。
3.6.4.6 list反转排序
reverse();//反转链表,比如lst包含1,3,5元素,运行此方法后,lst就包含5,3,1元素。
sort(); //list排序
*/
void printList(list<int>& L) {
    for (list<int>::iterator it = L.begin(); it != L.end(); it++) {
        cout << *it << " ";
    }
    cout << endl;
}

void test01() {
    list<int> L(10, 10);
    printList(L);
    cout << endl;
    list<int> L2(L.begin(), L.end());
    printList(L2);

    L2.push_back(100);
    for (list<int>::reverse_iterator it = L2.rbegin(); it != L2.rend(); it++) {
        cout << *it << " ";
    }
    cout << endl;

    //list容器不支持随机访问
    /*list<int>::iterator it = L2.begin();
    it += 1;*/

    list<int> L3;
    L3.push_back(10);
    L3.push_back(20);
    L3.push_back(30);
    L3.push_back(100);
    L3.push_back(200);
    L3.push_back(300);
    printList(L3);
    L3.pop_back();
    L3.pop_front();
    printList(L3);

    L3.insert(L3.begin(), 100);
    L3.remove(100); //remove 放值 erase放迭代器
    printList(L3);

}

void test03() {
    list<int> L3;
    L3.push_back(10);
    L3.push_back(20);
    L3.push_back(30);
    L3.push_back(100);
    L3.push_back(200);
    L3.push_back(300);
    cout << "大小:" << L3.size() << endl;
    if (L3.empty()) {
        cout << "13为空" << endl;
    }

    else {
        cout << "不为空" << endl;

    }
    L3.resize(10);
    printList(L3);
    L3.resize(5);
    printList(L3);
    cout << L3.size() << endl;
    cout << "l3.front()" << L3.front() << endl;
    cout << "l3.back()" << L3.back() << endl;
    
}

bool myCompare(int v1, int v2) {
    return v1 > v2;
}


void test04() {
    list<int> L;
    L.push_back(10);
    L.push_back(20);
    L.push_back(30);
    L.push_back(40);
    //L.reverse();
    printList(L);
    L.sort(myCompare);
    printList(L);
    //sort(L);所有不支持随机访问的迭代器 不可以用系统提供的算法
}

//自定义数据类型
  class Person {
public:
    Person(string name, int age) {
        this->m_Name = name;
        this->m_Age = age;
    }
    string m_Name;
    int m_Age;
    
    
};

bool myComparePerson(Person & p1, Person& p2) {
    return p1.m_Age > p2.m_Age;
}


void test05() {
    list<Person> L;
    Person p1("a",10);
    Person p2("b", 20);
    Person p3("c", 30);
    Person p4("d", 40);

    L.push_back(p1);
    L.push_back(p2);
    L.push_back(p3);
    L.push_back(p4);
    L.sort(myComparePerson);
    for (list<Person>::iterator it = L.begin(); it != L.end(); it++) {
        cout << (*it).m_Age << " ";
    }
    cout << endl;
    

}
int main() {
    test05();
    system("pause");
    return EXIT_SUCCESS;
}

09 set容器

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<list>
#include <set>
#include <string>
#include <unordered_set>
using namespace std;

void printSet(set<int>& s) {
    for (set<int>::const_iterator it = s.begin(); it != s.end(); it++) {
        cout << *it << " ";
    }
}



//关联式容器自动排序
void test01() {
    set<int> s1;
    s1.insert(5);
    s1.insert(1);
    s1.insert(9);
    s1.insert(3);
    s1.insert(7);
    s1.insert(7);
    printSet(s1);
    s1.erase(s1.begin());
    s1.erase(3);
    printSet(s1);
    

}


void test02() {
    set<int> s1;
    pair <set<int>::iterator, bool> ret = s1.insert(10);
    if (ret.second) {
        cout << "success!" << endl;
    }

    ret = s1.insert(10);
    if (ret.second) {
        cout << "success!" << endl;
    }
    else
        cout << "failure!" << endl;
    

}
//指定set规则 从大到小
class myCompare {
public:
    bool operator()(int v1, int v2) const {
        return v1 > v2;
    }
};


//set容器排序
void test03() {
    set<int,myCompare> s1;
    s1.insert(1);
    s1.insert(3);
    s1.insert(5);
    s1.insert(7);

    for (set<int, myCompare>::iterator it = s1.begin(); it != s1.end(); it++) {
        cout << *it << " ";
    }
    cout << endl;
    myCompare my;
    cout << my(1, 2);

}

//自定义数据类型
class Person {
public:
    Person(string name, int age) {
        this->m_Name = name;
        this->m_Age = age;
    }
    string m_Name;
    int m_Age;


};
class myComparePerson {
public:
    bool operator()(const Person& p1,const Person& p2) const{
        if (p1.m_Age > p2.m_Age)
            return true;
        return false;
    }

    
};

void test04() {
    set<Person,myComparePerson> s1;
    Person p1("大娃", 100);
    Person p2("二娃", 200);
    Person p3("三娃", 300);
    Person p4("四娃", 600);

    //插入自定义数据类型,上来就制定好排序规则

    s1.insert(p1);
    s1.insert(p2);
    s1.insert(p3);
    s1.insert(p4);

    for (set<Person, myComparePerson>::iterator it = s1.begin(); it != s1.end(); it++) {
        cout << "姓名:" << (*it).m_Name << ",年龄:" << it->m_Age << endl;
    }


}



int main() {
    test04();
}

10 map容器

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<list>
#include <set>
#include <map>
#include <string>
using namespace std;


void test01() {
    map<int, int> m;
    //第一种
    m.insert(pair<int, int>(1, 10));
    //第二种 推荐
    m.insert(make_pair(2, 20));
    //第三种、
    m.insert(map<int, int>::value_type(3, 30));
    //第四种 如果保证key存在,那么可以通过中括号访问
    m[4] = 40;
    for (map <int, int>::iterator it = m.begin(); it != m.end(); it++) {
        cout << "key = " << it->first << ",value = " << it->second << endl;
    }
    m[5];
    for (map <int, int>::iterator it = m.begin(); it != m.end(); it++) {
        cout << "key = " << it->first << ",value = " << it->second << endl;
    }

}

//m.find() 返回迭代器
void test02() {
    map<int, int> m;
    m.insert(pair<int, int>(1, 10));
    m.insert(make_pair(2, 20));
    m.insert(map<int, int>::value_type(3, 30));
    m[4] = 40;
    m.erase(1);
    for (map <int, int>::iterator it = m.begin(); it != m.end(); it++) {
        cout << "key = " << it->first << ",value = " << it->second << endl;
    }

    if (m.find(1) != m.end()) {
        cout << "find it!" << endl;
    }
    else
        cout << "not find it" << endl;

    int num = m.count(3); //只有0和1,multiset会大于1

    //返回第一个key >= keyelem的元素的迭代器
    map<int, int>::iterator ret = m.lower_bound(3);

    if (ret != m.end()) {
        cout << "lower_bound中value " << ret->second << endl;
    }

    //返回第一个key >= keyelem的元素的迭代器
    ret = m.upper_bound(3);

    if (ret != m.end()) {
        cout << "upper_bound中value " << ret->second;
    }

    pair<map<int, int>::iterator, map<int, int>::iterator> ret2 = m.equal_range(3);
    if (ret2.first != m.end()) {
        cout << "找到了equal_range的key:" << ret2.first->first << "value:" << ret2.first->second << endl;

    }

    if (ret2.second != m.end()) {
        cout << "找到了equal_range的key:" << ret2.second->first << "value:" << ret2.second->second << endl;

    }

}

//指定排序规则

class myCompare {
public:
    bool operator()(int v1, int v2) const {
        return v1 > v2;
    }
};


void test03() {
    map<int, int, myCompare> m;
    m.insert(pair<int, int>(1, 10));
    //第二种 推荐
    m.insert(make_pair(2, 20));
    //第三种、
    m.insert(map<int, int>::value_type(3, 30));
    //第四种 如果保证key存在,那么可以通过中括号访问
    m[4] = 40;

    for (map <int, int>::iterator it = m.begin(); it != m.end(); it++) {
        cout << "key = " << it->first << ",value = " << it->second << endl;
    }
}

int main() {
    test03();
    system("pause");
}

11 员工分组案例

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<list>
#include <set>
#include <map>
#include <string>
#include <vector>
using namespace std;
enum{ RENLI,YANFA,MEISHU };
class Worker {
public:
    string m_Name;
    int m_Money;
};


void createWorker(vector<Worker>& v) {
    string nameSeed = "ABCDE";
    for (int i = 0; i < 5; i++) {
        string name = "员工";
        name += nameSeed[i];

        int money = rand() % 10000 + 10000;

        Worker w;
        w.m_Name = name;
        w.m_Money = money;
        v.push_back(w);
    }
}

void setGroup(vector<Worker>& v, multimap<int, Worker>& m) {
    for (vector<Worker>::iterator it = v.begin(); it != v.end(); it++) {
        //随机产生部门编号
        int departmentId = rand() % 3;
        //将员工分到multimap中
        m.insert(make_pair(departmentId, *it));
    }
}

void showGroup(multimap<int, Worker>& m) {
    //人力部门显示
    cout << "人力部门显示如下:" << endl;
    multimap<int, Worker>::iterator pos = m.find(RENLI);
    int num = m.count(RENLI);
    int index = 0;
    for (; pos != m.end() && index < num; index++,pos++) {
        cout << "姓名:" << pos->second.m_Name << ",工资" << pos->second.m_Money << endl;
    }

    //研发部门显示
    cout << "人力部门显示如下:" << endl;
    pos = m.find(YANFA);
    num = m.count(YANFA);
    index = 0;
    for (; pos != m.end() && index < num; index++, pos++) {
        cout << "姓名:" << pos->second.m_Name << ",工资" << pos->second.m_Money << endl;
    }

    //美术部门显示
    cout << "人力部门显示如下:" << endl;
    pos = m.find(MEISHU);
    num = m.count(MEISHU);
    index = 0;
    for (; pos != m.end() && index < num; index++, pos++) {
        cout << "姓名:" << pos->second.m_Name << ",工资" << pos->second.m_Money << endl;
    }

}
int main() {
    srand(time(NULL));
    vector<Worker> v;
    createWorker(v);
    /*for (vector<Worker>::iterator it = v.begin(); it != v.end(); it++) {
        cout << "姓名:" << it->m_Name << ",工资:" << it->m_Money << endl;
    }*/

    //设置分组
    multimap<int, Worker> m;
    setGroup(v, m);


    //分部门显示员工
    showGroup(m);
}

12 函数对象的基本使用

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<list>
#include <set>
#include <map>
#include <string>
#include <vector>
using namespace std;


class Myprint {
public:
    void operator()(int num) {
        cout << num << endl;
        count++;
    }

    int count = 0;
};

void test01() {
    Myprint myPrint; //Myprint是一个类  而不是函数
    myPrint(111);
}


//函数对象超出普通函数概念,内部可以保存状态
void test02() {
    Myprint myPrint; //Myprint是一个类  而不是函数
    myPrint(111);
    myPrint(111);
    myPrint(111);
    myPrint(111);
    Myprint()(1000);
    cout << myPrint.count << endl;
}

//函数对象作为参数
void doPrint(Myprint print, int num) {
    print(num);
}

void test03() {
    doPrint(Myprint(), 7);
}

int main() {
    test02();
}

13 谓词

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<list>
#include <set>
#include <map>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
class GreaterThan20 {
public:
    //一元谓词
    bool operator()(int val) {
        return val > 20;
    }
};


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

    //查找第一个大于20的数字
    vector<int>::iterator pos = find_if(v.begin(), v.end(), GreaterThan20());
    if (pos != v.end()) {
        cout << "find it" << endl;
    }
}



class Mycompare {
public:
    bool operator()(int v1, int v2) {
        return v1 > v2;
    }
};



void print(int num) {
    cout << num << " ";
}
//二元谓词
void test02() {
    vector<int> v;
    v.push_back(10);
    v.push_back(20);
    v.push_back(30);
    v.push_back(40);

    sort(v.begin(), v.end(), Mycompare());
    for_each(v.begin(), v.end(), [](int val) {cout << val << " "; });
    for_each(v.begin(), v.end(), print);
}

int main() {
    test02();
}

14 内建函数对象

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<list>
#include <set>
#include <map>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;
//template<classT>T plus<T>//加法仿函数
//template<class T> T minus<T>//减法仿函数
//template<class T> T multiplies<T>//乘法仿函数
//template<class T> T divides<T>//除法仿函数
//template<class T> T modulus<T>//取模仿函数
//template<class T> T negate<T>//取负仿函数

void test01() {
    negate<int> n;
    cout << n(10) << endl;

    plus<int> p;
    cout << p(1, 1) << endl;
}

void test02() {
    vector<int> v;
    v.push_back(10);
    v.push_back(20);
    v.push_back(30);
    v.push_back(50);
    v.push_back(40);
    greater<int> g;
    sort(v.begin(), v.end(), g);
    for_each(v.begin(), v.end(), [](int num) {cout << num << " "; });
}
int main() {
    test02();
}

15 适配器

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<list>
#include <set>
#include <map>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;

class Myprint:public binary_function<int,int,void> {
public:
    void operator()(int v,int start) const{
        cout << v << " " << start << " " << v + start << endl;
    }
};

void test01() {
    vector<int> v;
    for (int i = 0; i < 10; i++) v.push_back(i);
    cout << "请输入起始值";
    int num;
    cin >> num;
    Myprint my;
    for_each(v.begin(), v.end(),bind2nd(my,num));
    for_each(v.begin(), v.end(), bind1st(my, num));

}

//一元取反适配器 not1
//继承 unary_function<参数类型1,返回值类型>
class GreaterThan5:public unary_function <int,bool> {
public:
    bool operator()(int num) const{
        return num > 5;
    }
};

void test02() {
    vector<int> v;
    for (int i = 0; i < 10; i++) {
        v.push_back(i);
    }

    vector<int>::iterator pos = find_if(v.begin(), v.end(), not1(GreaterThan5()));
    cout << "找到大于5的数为" << *pos;
}





//函数指针适配器
void MyPrint03(int v,int start) {
    cout << v + start << " ";
}

void test03() {
    vector<int> v;
    for (int i = 0; i < 10; i++) v.push_back(i);
    for_each(v.begin(), v.end(), bind2nd(ptr_fun(MyPrint03), 100));
}

//成员函数适配器

class Person {
public:
    Person(string name, int age) {
        this->m_Name = name;
        this->m_Age = age;
    }

    string m_Name;
    int m_Age;

    void showPerson() {
        cout << "姓名:" << this->m_Name << ",年龄:" <<this->m_Age << endl ;
    }

    void PlusAge() {
        this->m_Age++;
    }
};


void test04() {
    vector<Person> v;
    Person p1("aaa", 100);
    Person p2("bbb", 1000);
    Person p3("ccc", 10000);
    Person p4("ddd", 10);

    v.push_back(p1);
    v.push_back(p2);
    v.push_back(p3);
    v.push_back(p4);
    
    //成员函数适配器
    for_each(v.begin(), v.end(), mem_fun_ref(&Person::showPerson));
    for_each(v.begin(), v.end(), mem_fun_ref(&Person::PlusAge));
    for_each(v.begin(), v.end(), mem_fun_ref(&Person::showPerson));
}
int main() {
    test04();
    system("pause");
}

16 常用遍历算法

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<list>
#include <set>
#include <map>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;


void test01() {
    vector<int> v;
    for (int i = 0; i < 10; i++) v.push_back(i);

    for_each(v.begin(), v.end(), [](int num) {cout << num << " "; });
}


class Transform {
public:
    int operator()(int val) {
        return val + 10;
    }
};

void test02() {
    vector<int> v; //原容器
    for (int i = 0; i < 10; i++) v.push_back(i);

    vector<int> vTarget; //目标容器
    vTarget.resize(100);
    //cout << vTarget.size() << vTarget.capacity() << endl;
    transform(v.begin(), v.end(), vTarget.begin(),Transform());
    for_each(vTarget.begin(), vTarget.end(), [](int num) {cout << num << endl; });
}

class Transform2 {
public:
    int operator()(int val1,int val2) {
        return val1*val2;
    }
};

//将两个vector拼接在一起
void test03() {
    vector<int> v1;
    vector<int> v2;

    for (int i = 0; i < 10; i++) {
        v1.push_back(i + 100);
        v2.push_back(i + 200);
    }

    vector<int> vTarget(100);
    transform(v1.begin(), v1.end(),v2.begin(), vTarget.begin(), Transform2());
    for_each(vTarget.begin(), vTarget.end(), [](int num) {cout << num << endl; });
}


int main() {
    test03();
}

17 常用查找算法

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<list>
#include <set>
#include <map>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;
void test01() {
    vector<int> v;
    for (int i = 0; i < 10; i++) v.push_back(i);
    vector<int>::iterator pos = find(v.begin(), v.end(), 5);
    if (pos != v.end()) {
        cout << *pos << endl;
    }
}

class Person {
public:
    Person(string name, int age) {
        this->m_Name = name;
        this->m_Age = age;
    }

    bool operator==(const Person& p) {
        if (this->m_Name == p.m_Name && this->m_Age == p.m_Age)
            return true;
        return false;
    }

    string m_Name;
    int m_Age;
};

void test02() {
    vector<Person> v;
    Person p1("aaa", 10);
    Person p2("bbb", 10);
    Person p3("ccc", 10);
    Person p4("ddd", 10);
    v.push_back(p1);
    v.push_back(p2);
    v.push_back(p3);
    v.push_back(p4);

    vector<Person>::iterator pos = find(v.begin(), v.end(), p2);
    if (pos != v.end()) cout << "find it";
}

class Greaterthan5 {
public:
    bool operator()(int a) {
        return a > 5;
    }
};

void test03() {
    vector<int> v;
    for (int i = 0; i < 10; i++) v.push_back(i);
    v.push_back(4);
    v.push_back(4);
    v.push_back(4);
    v.push_back(4);

    int num = count(v.begin(), v.end(),4);
    cout << num << endl;
    num = count_if(v.begin(), v.end(), Greaterthan5());
    cout << num << endl;

}
int main() {
    test03();
}

18 常用排序算法

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<list>
#include <set>
#include <map>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;


//merge 两容器要有序并且顺序一致
void test01() {
    vector<int> v1;
    vector<int> v2;
    for (int i = 0; i < 10; i++) {
        v1.push_back(i);
        v2.push_back(i + 1);
    }
    

    vector<int> vTarget;
    vTarget.resize(v1.size() + v2.size());
    merge(v1.begin(), v1.end(), v2.begin(), v2.end(), vTarget.begin());
    for_each(vTarget.begin(), vTarget.end(), [](int v) {cout << v << " "; });

}

void test02() {
    vector<int> v;
    for (int i = 0; i < 10; i++) v.push_back(i);
    random_shuffle(v.begin(),v.end());
    for_each(v.begin(), v.end(), [](int v) {cout << v << " "; });

}

void test03() {
    vector<int> v;
    for (int i = 0; i < 10; i++) v.push_back(i);
    reverse(v.begin(), v.end());
    for_each(v.begin(), v.end(), [](int v) {cout << v << " "; });

}



int main() {
    test01();
}

19 常用算数生成算法

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<list>
#include <set>
#include <map>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <numeric>
using namespace std;

void test01() {
    
    vector<int> v;
    for (int i = 0; i < 10; i++) v.push_back(i);
    int sum = accumulate(v.begin(), v.end(), 0);
    cout << sum << endl;
}


void test02() {

    vector<int> v;
    for (int i = 0; i < 10; i++) v.push_back(i);
    fill(v.begin(), v.end(), 1000);
    for_each(v.begin(), v.end(), [](int num) {cout << num << " "; });
    
}


int main() {
    test02();
}

20 常用集合算法

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<list>
#include <set>
#include <map>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <numeric>
using namespace std;


void test01() {
    vector<int> v1;
    vector<int> v2;
    for (int i = 0; i < 10; i++) {
        v1.push_back(i);
        v2.push_back(i + 5);
    }
    vector<int> vTarget;
    vTarget.resize(v1.size() + v2.size());
    vector<int>::iterator itEnd = set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), vTarget.begin());
    for_each(vTarget.begin(), itEnd, [](int num) {cout << num << " "; });
}

void test02() {
    vector<int> v1;
    vector<int> v2;
    for (int i = 0; i < 10; i++) {
        v1.push_back(i);
        v2.push_back(i + 5);
    }
    vector<int> vTarget;
    vTarget.resize(v1.size() + v2.size());
    vector<int>::iterator itEnd = set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), vTarget.begin());
    for_each(vTarget.begin(), itEnd, [](int num) {cout << num << " "; });
}


void test03() {
    vector<int> v1;
    vector<int> v2;
    for (int i = 0; i < 10; i++) {
        v1.push_back(i);
        v2.push_back(i + 5);
    }
    vector<int> vTarget;
    vTarget.resize(v1.size() + v2.size());
    //v1 - v2
    vector<int>::iterator itEnd = set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), vTarget.begin());
    for_each(vTarget.begin(), itEnd, [](int num) {cout << num << " "; });
    cout << endl;
    // v2- v1
    itEnd = set_difference(v2.begin(), v2.end(), v1.begin(), v1.end(), vTarget.begin());
    for_each(vTarget.begin(), itEnd, [](int num) {cout << num << " "; });
}
int main() {
    test03();
}

追加用法

void append(){
    vector<int> a;
    for(int i = 0;i < 100;i++)
        a.push_back(i);

    int sum = accumulate(a.cbegin(),a.cend(),0);
    cout << sum;

    vector<int> s;
    //前缀和
    partial_sum(a.cbegin(),a.cend(),back_inserter(s));
    for(auto it:s) cout << it <<" ";
    
    //旋转数组
    rotate(a.begin(),a.begin() + 2,a.end());
    cout << endl;
    for(auto it: a) cout <<it <<" ";
    //分类
    vector<int> v = {0,1,2,3,4,5,6,7,8,9};
    partition(v.begin(),v.end(),[](int i){return i % 2 == 0;});
    for(auto it:v) cout << it<<" ";


    //找最大值
    cout << *max_element(v.begin(),v.end());
    //找最小值
    cout << *min_element(v.begin(),v.end());
}

lambda表达式

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<list>
#include <set>
#include <map>
#include <string>
#include <vector>
using namespace std;

int main() {
    //lambda表达式就是匿名函数(没有名字的函数)

    //[]捕获列表 ()参数列表  -> 返回值
    int c = [](int a, int b) -> int {
        return a + b;
    }(1, 2);

    cout << c << endl;

    auto f = [](int a, int b) {
        return a + b;
    };

    c = f(1, 2);
    cout << c << endl;


    //函数式编程  通常用于多线程,并发
    int d = [](int n) {
        return [n](int x) {
            return n + x;
        }(1);
    }(2);

    auto func = [](int n) {
        return [n](int x)  {
            return n + x;
        };
    };

    c = func(1)(2);

    cout << c << endl;
}
最后修改:2021 年 03 月 10 日 06 : 47 PM
如果觉得我的文章对你有用,请随意赞赏