qfedu-cpp-level/day9

STL（一）

1. string 容器

string 也是字符串的类型，可以理解时它是用于存放字符的容器。

1.1 String 和 c 风格字符串对比

1) char * 是一个指针，string 是一个类
2) string 封装了很多实用的成员方法
   查找 find，拷贝 copy，删除 delete 替换 replace，插入 insert
3) 不用考虑内存释放和越界
   string 管理 char*所分配的内存。每一次 string 的复制，取值都由 string 类负责维
护，不用担心复制越界和取值越界等。

1.2 string 容器 api

// 构造函数
string();    //创建一个空的字符串 例如: string str;
string(const string& str);//使用一个 string 对象初始化另一个 string 对象
string(const char* s);//使用字符串 s 初始化
string(int n, char c); //使用 n 个字符 c 初始化

// 赋值
string& operator=(const char* s);//char*类型字符串 赋值给当前的字符串
string& operator=(const string &s);//把字符串 s 赋给当前的字符串
string& operator=(char c);//字符赋值给当前的字符串
string& assign(const char *s);//把字符串 s 赋给当前的字符串
string& assign(const char *s, int n); //把字符串 s 的前 n 个字符赋给当前的字
符串
string& assign(const string &s);//把字符串 s 赋给当前字符串
string& assign(int n, char c);//用 n 个字符 c 赋给当前字符串
string& assign(const string &s, int start, int n);//将 s 从 start 开始 n 个
字符赋值给字符串

// 取值
char& operator[](int n);//通过[]方式取字符
char& at(int n);//通过 at 方法获取字符


// 字符串拼接
string& operator+=(const string& str);//重载+=操作符
string& operator+=(const char* str);//重载+=操作符
string& operator+=(const char c);//重载+=操作符
string& append(const char *s);//把字符串 s 连接到当前字符串结尾
string& append(const char *s, int n);//把字符串 s 的前 n 个字符连接到当前字符串结尾
string& append(const string &s);  //同 operator+=()
string& append(const string &s, int pos, int n);//把字符串 s 中从 pos 的 n 个字符连接到当前字符串结尾
string& append(int n, char c);//在当前字符串结尾添加 n 个字符 c

// 查找与替换
int find(const string& str, int pos = 0) const; //查找 str 第一次出现位置, 从 pos 开始查找， 如果未查找到返回  -1
int find(const char* s, int pos = 0) const; //查找 s 第一次出现位置,从 pos 开始查找
int find(const char* s, int pos, int n) const; //从 pos 位置查找 s 的前 n个字符第一次位置
int find(const char c, int pos = 0) const; //查找字符 c 第一次出现位置
int rfind(const string& str, int pos = npos) const;//查找 str 最后一次位置,从 pos 开始查找
int rfind(const char* s, int pos = npos) const;//查找 s 最后一次出现位置, 从 pos 开始查找
int rfind(const char* s, int pos, int n) const;//从 pos 查找 s 的前 n 个字符最后一次位置
int rfind(const char c, int pos = 0) const; //查找字符 c 最后一次出现位置
string& replace(int pos, int n, const string& str); //替换从 pos 开始 n 个字符为字符串 str
string& replace(int pos, int n, const char* s); //替换从 pos 开始的 n 个字符为字符串 s

// 比较 ，返回值 0:相等， 1:大于s,  -1：小于s
int compare(const string &s) const;//与字符串 s 比较
int compare(const char *s) const;//与字符串 s

// 截取子字符串
string substr(int pos = 0, int n = npos) const;//返回由 pos 开始的 n 个字符组成的字符串

// 插入与删除
string& insert(int pos, const char* s); //插入字符串
string& insert(int pos, const string& str); //插入字符串
string& insert(int pos, int n, char c);//在指定位置插入 n 个字符 c
string& erase(int pos, int n = npos);//删除从pos 开始的 n 个

// 转成 char *
const char * c_str()  将当前字符串转成 char *

// 获取字符串的长度
int size();

2. vector 容器

2.1 vector 与数组的区别

vector 的结构类同于数组，数组是静态的，在定义时确定的数组的大小；而 vector 是动态的，添加元素时如果空间不足时，则会自动扩容器（2^n）；整体来说，vector 比较灵活的，而且 vector 是类模板，可以存放任意类型的元素。

2.2 vector 迭代器

vector 维护一个线性空间(线性连续空间), vector 迭代器所需要的操作行为 是(*,->, ++, --, +, -, +=, -=)运算符重载等。vector 支持随机存取，vector 提供的是随机访问迭代器(Random Access Iterator), 迭代器中的元素即为 vector 容器中的元素。

【重要说明】: vector 容器扩容之后，原迭代器则无效，需要重新获取获取器

所谓动态增加大小，并不是在原空间之后续接新空间(因为无法保证原空间之后尚有可配置的空间)，而是一块更大的内存空间，然后将原数据拷贝新空间，并释放原空间。
因此，对 vector 的任何操作，一旦引起空间的重新配置，指向原vector的所有迭代器就都失效了。这是程序员容易犯的一个错误，务必小心。

2.3 vector 容器 api

3.3.1 构造函数

// 构造函数
vector<T> v;   //采用模板实现类实现，默认构造函数
vector(v.begin(), v.end());//将 v[begin(), end())区间中的元素拷贝给本身。
vector(n, elem);//构造函数将 n 个 elem 拷贝给本身。
vector(const vector &vec);//拷贝构造函

3.3.2 赋值操作

assign(beg, end);//将[beg, end)区间中的数据拷贝赋值给本身。
assign(n, elem);//将 n 个 elem 拷贝赋值给本身。
vector& operator=(const vector &vec);//重载等号操作符
swap(vec);// 将 vec 与本身的元素互换

3.3.3 大小操作

int size();   // 返回容器中元素的个数
bool empty();   //判断容器是否为空， 返回bool值（0， 1）
void resize(int num);  //重新指定容器的长度为 num，若容器变长，则以默认值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除。
void resize(int num, elem);  //重新指定容器的长度为 num，若容器变长，则以 elem 值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除。
int capacity();  //容器的容量
void reserve(int len);  //容器预留 len 个元素长度，预留位置不初始化，元素不可访问。

3.3.4 存取操作

at(int idx);   //返回索引 idx 所指的数据，如果 idx 越界，抛出 out_of_range 异常。
operator[](int idx);  //返回索引 idx 所指的数据，越界时，运行直接报错
front();     //返回容器中第一个数据元素
back();      //返回容器中最后一个数据元素

3.3.5 插入和删除

insert(const_iterator pos, int count, T ele); //迭代器指向位置 pos 插入 count个元素 ele.
push_back(ele); //尾部插入元素 ele
pop_back();//删除最后一个元素
erase(const_iterator start, const_iterator end); //删除迭代器从 start 到 end 之间的元素， 删除[start, end)区间的所有元素
erase(const_iterator pos);  //删除迭代器指向的元素
clear();   //删除容器中所有元素

2.4 小技巧示例

2.2.4.1 巧用 swap 收缩内存空间

resize()+swap()实现 vector 收缩内存空间

resize(n);
vector<T>(v).swap(v);

3. deque 容器

3.1 deque 基本概念

vector 容器是单向开口的连续内存空间，deque 则是一种双向开口的连续线性空间。

所谓的双向开口，意思是可以在头尾两端分别做元素的插入和删除操作，当然，vector 容器也可以在头尾两端插入元素，但是在其头部操作效率奇差，无法被接受。

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

1) 在于 deque 允许使用常数项时间对头端进行元素的插入和删除操作。
2) 在于 deque 没有容量的概念，因为它是动态的以分段连续空间组合而成，随时可以增加一段新的空间并链接起来。
3) deque 没有必须要提供所谓的空间保留(reserve)功能
4) 虽然deque容器也提供了 Random Access Iterator,但是它的迭代器并不是普通的指针，其复杂度和vector 不是一个量级，这当然影响各个运算的层面。因此，除非有必要，我们应该尽可能的使用vector，而不是deque。
5）对 deque 进行的排序操作，为了最高效率，可将 deque 先完整的复制到一个 vector 中，对 vector 容器进行排序，再复制回 deque。

3.2 deque 实现原理

逻辑上，deque 容器是连续的空间, 是由一段一段的定量的连续空间构成。一旦有必要在 deque 前端或者尾端增加新的空间，便配置一段连续定量的空间，串接在 deque 的头端或者尾端。

deque 最大的工作就是维护这些分段连续的内存空间的整体性的假象，并提供随机存取的接口。

既然 deque 是分段连续内存空间，那么就必须有中央控制（map 实现的），维持整体连续的假象，数据结构的设计及迭代器的前进后退操作颇为繁琐。

中央控制： 连续小空间，由 map 实现，存放是地址，地址指向的另一个连续空间为缓冲区。

缓冲区：是 deque 的存储空间的主体。

3.3 常用 API

3.3.1 构造函数

deque<T> deqT;//默认构造形式
deque(beg, end);//构造函数将[beg, end)区间中的元素拷贝给本身。
deque(n, elem);//构造函数将 n 个 elem 拷贝给本身。
deque(const deque &deq);//拷贝构造函数。

3.3.2 赋值操作

assign(beg, end);//将[beg, end)区间中的数据拷贝赋值给本身。
assign(n, elem);//将 n 个 elem 拷贝赋值给本身。
deque& operator=(const deque &deq); //重载等号运算符
swap(deq);// 将 deq 与本身的元素互换

3.3.3 大小操作

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

3.3.4 双端插入和删除

void push_back(elem);//在容器尾部添加一个数据
void push_front(elem);//在容器头部插入一个数据
void pop_back();//删除容器最后一个数据
void pop_front();//删除容器第一个数据

3.3.5 数据存取

at(idx);//返回索引 idx 所指的数据，如果 idx 越界，抛出 out_of_range。
operator[]; //返回索引 idx 所指的数据，如果 idx 越界，不抛出异常，会直接出错。
front();//返回第一个数据。
back();//返回最后一个

如：operator[] 操作数据，超出范围之后，则会直接报错并不抛出异常

【注意】 string 泛型的 deque 默认分配 16 个， int 默认 128 个

3.3.6 插入操作

void insert(iterator pos,T elem);//在 pos 位置插入一个 elem 元素的拷贝，返回新数据的位置。
void insert(iterator pos,int n,T elem);//在 pos 位置插入 n 个 elem 数据，无返回值。
void insert(iterator pos,iter_beg,iter_end);//在 pos 位置插入[beg,end)区间的数据，无返回值。

3.3.7 删除操作

clear();//移除容器的所有数据
iterator erase(iterator beg,iterator end);//删除[beg,end)区间的数据，返回下一个数据的位置。
iterator erase(iterator pos);//删除 pos 位置的数据，返回下一个数据的位置。

4 stack 容器

4.1 stack 基本概念

stack 是一种先进后出(First In Last Out,FILO)的数据结构，它只有一个出口，stack 容器允许新增元素、移除元素、取得栈顶元素，但是除了最顶端外，没有任何其他方法可以存取 stack 的其他元素。换言之，stack 不允许有遍历行为。

4.2 stack 没有迭代器

stack 所有元素的进出都必须符合”先进后出”的条件，只有 stack 顶端的元素，才有机会被外界取用。Stack 不提供遍历功能，也不提供迭代器。

4.3 常用 API

4.3.1 构造函数

stack<T> stkT;//stack 采用模板类实现， stack 对象的默认构造形式：
stack(const stack &stk);//拷贝构造函数

4.3.2 赋值操作

stack& operator=(const stack &stk);//重载等号操作符

4.3.3 数据存取

void push(elem);//向栈顶添加元素
void pop();//从栈顶移除第一个元素
T top();//返回栈顶元素

4.3.4 大小操作

empty();//判断堆栈是否为空
size();//返回堆栈的大小

案例： 人员的淘汰方式（业绩从高到低、后入职）

#include <iostream>
#include <vector>
#include <stack>

using namespace std;
class Worker;
class Date
{
    friend Worker;
    friend ostream &operator<<(ostream &cout, Date &date)
    {
        cout << date.year << "年" << date.month << "月" << date.day << "日";
        return cout;
    }

private:
    int year;
    int month;
    int day;

public:
    Date(int year, int month, int day)
    {
        this->year = year;
        this->month = month;
        this->day = day;
    }
    bool operator>(Date &other)
    {
        // cout << *this << " pk " << other << endl;
        return year > other.year || (year == other.year && month > other.month) || (year == other.year && month == other.month && day > other.day);
    }
    bool operator<=(Date &other)
    {
        return year <= other.year && month <= other.month && day <= other.day;
    }
};
class Worker
{
public:
    string name;     // 姓名
    Date *hire_date; // 入职时间
    double volume;   // 业绩值

public:
    Worker(const string &name, Date *hire_date, double volume)
    {
        this->name = name;
        this->hire_date = hire_date;
        this->volume = volume;
    }
    Worker(const Worker &other)
    {
        Date *hire_date = new Date(other.hire_date->year, other.hire_date->month, other.hire_date->day);
        this->hire_date = hire_date;
        this->name = other.name;
        this->volume = other.volume;
    }
    Worker &operator=(const Worker &other)
    {
        this->hire_date->year = other.hire_date->year;
        this->hire_date->month = other.hire_date->month;
        this->hire_date->day = other.hire_date->day;
        this->name = other.name;
        this->volume = other.volume;
        return *this;
    }

    ~Worker()
    {
        if (hire_date)
            delete hire_date;
        hire_date = NULL;
    }

    void show()
    {
        cout << "name=" << name << ",hire_date=" << *hire_date << ",volume=" << volume << endl;
    }
};

void sortByHireDate(Worker *p, int size)
{
    for (int i = 0; i < size - 1; i++)
    {
        int min = i;
        for (int j = i + 1; j < size; j++)
        {
            if (*(p[min].hire_date) > *(p[j].hire_date))
            {
                min = j;
            }
        }
        if (min != i)
        {
            // cout << p[i].name << " 和 " << p[min].name << " 交换数据" << endl;
            Worker tmp = p[i]; // 拷贝构造函数
            p[i] = p[min];     // operator=重载
            p[min] = tmp;
        }
    }
}

void sortByVolume(Worker *p, int size)
{
    for (int i = 0; i < size - 1; i++)
    {
        int min = i;
        for (int j = i + 1; j < size; j++)
        {
            if (p[min].volume < p[j].volume)
            {
                min = j;
            }
        }
        if (min != i)
        {
            // cout << p[i].name << " 和 " << p[min].name << " 交换数据" << endl;
            Worker tmp = p[i]; // 拷贝构造函数
            p[i] = p[min];     // operator=重载
            p[min] = tmp;
        }
    }
}

int main(int argc, char const *argv[])
{
    Worker w1("disen", new Date(2020, 1, 15), 1000);
    Worker w2("jack", new Date(2021, 1, 15), 100);
    Worker w3("lucy", new Date(2020, 2, 15), 500);
    Worker w4("mack", new Date(2020, 3, 25), 300);
    Worker w5("judy", new Date(2022, 5, 18), 400);
    Worker w6("rose", new Date(2023, 1, 10), 1200);

    Worker m[] = {w1, w2, w3, w4, w5, w6};
    // sortByHireDate(m, 6);
    sortByVolume(m, 6);
    vector<Worker> v1(m, m + 6);
    stack<Worker> s1;
    vector<Worker>::iterator it = v1.begin();
    while (it != v1.end())
    {
        (*it).show();
        s1.push(*it);
        it++;
    }

    // 辞退2位新来的员工
    // cout << "-----辞退2位新来的员工----" << endl;
    cout << "-----业绩最差的2位员工----" << endl;
    for (int i = 0; i < 2; i++)
    {
        s1.top().show();
        s1.pop();
    }

    return 0;
}