28.C++进阶 - STL 集合容器的基本介绍和使用

类似java的集合，

1.vector容器, 底层是数组，动态数组，会自动扩展。

java的vector，底层封装了一个Object数组。
C++的vector，是一个线性顺序结构，每个对象都有一个整形的索引值。
只有在预先知道它大小的情况下，vector的性能才是最优的。

1.1 容量,size是角标。

• 向量大小：vec.size()
• 向量真实大小：vec.capacity();
• 向量潘孔：vec.empty();

1.2 修改

• 末尾添加元素：vec.push_back();
• 末尾删除元素：vec.pop_back();
• 任意位置插入元素：vec.insert()
• 任意位置删除元素：vec.erase(v.begin())
• 清空向量元素： vec.clear()

1.3 迭代器

• 开始指针：vec.begin();
• 末尾指针：vec.end(); // 指向最后一个元素的下一个位置
• 指向常量的末尾指针：vec.cend();

1.4 元素的访问

• 下标访问：vec[1]; // 并不会检查是否越界，越界程序宕机
• at方法访问：vec.at(1); // 会检查是否越界，是抛out of range异常。
• 访问第一个元素：vec.front()
• 访问最后个元素：vec.back()

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

void main(){
    vector<int> v;
    vector<int> v(10); // 初始大小 10
    vector<int> v(10,0); // 初始化10个0
    v.insert(v.begin(), 1);
    v.insert(v.begin(), 2); // 插入到最前面
    v.insert(v.end(), 5);
    // 修改
    v.front() = 33; // 引用当左值 当右值。
    v.back() = 44;  // 最后一个值
    
    // 遍历vector
    for(int i=0; i<v.size(); i++){
        cout<< v[i] << "\t" << endl;
    }
    cout << endl;
    for(vector<int>::iterator it=v.begin(); it!=v.end(); it++) { 
        // 迭代器遍历, 对当前指针it 取值*
        cout << *it << "\t" << endl;
    }
}

2.stack容器:栈

先进后出，类似火车倒车。
不能通过角标来取获取值，没有迭代器，不支持循环遍历。

• push() 压栈，向栈顶添加一个元素。
• pop() 出栈，弹出栈顶。从栈顶删除一个元素。弹出没有返回值。
• size() 容器大小
• top() 获取栈顶元素，不会改变栈的大小。不能对空栈使用top().
• empty() 判空
• swap() 交换两个栈的所有元素(内容)

#include <stack>
void main() {
    stack<int> s; // 定义 
    s.push(11); // 压入栈
    while(!s.empty()) { // 非空检查
        int top = s.top(); // 拿到元素
        s.pop(); // 弹出栈顶item，移除。没有返回值。
        cout << top << endl;
    }
}

3.queue容器：先进先出，两边开口的 队列

queue 队列-先进先出。底层可以链表 或数组实现。

void main() {
    queue<int> q;
    q.push(11);
    q.push(12);
    q.front() = 42; // 插入到最前面
    cout << q.front()<< endl;
    q.pop(); // 弹出
    int back = q.back(); // 最后加入的
    
    while(!q.empty()) {//遍历
        cout << q.front << endl; // 取出item
        q.pop(); // 弹出item
    }
}

优先级队列，根据索引优先，数据结构是数组，排序的方式是堆排序NlogN。O(N²)
priority_queue<int, vector<int>, less<int>> pq;
int 存放的数据
vector<int> 里面的数据类型，数组
less 从小到大, greater 从大到小

4.list 增删改查，基于双向链表的结构

链表分类：单链表，双链表，回环链表。
LinkedList：双向链表，查询慢，判断item在链表的前面还是后面，可以用二分法查找。

#include <list>
void main() {
    list<int> l;
    l.push_front(11); // 插入最前面
    l.push_back(22); // 插入最后面
    l.push(l.begin(), 10)
    // 2.修改，不能通过角标访问和修改
    l.back() = 33; // 左值右值 
    l.front() = 44; // 修改第一个item
    // 3.迭代器遍历
    for(list<int>:::iterator it=l.begin(); it!=l.end(); it++) {
        cout << *it << endl;
    }
    // 4.移除
    l.erase(l.begin()); // 删掉一个
    l.pop_front(); // 移除第一个
    l.pot_back();  // 移除最后一个
}

set容器

底层使用红黑树结构，set对存入的数据进行排序。
重复插入，并不会报错。默认set是从小到大排序less，从大到小greater.
count() item总数；
s.find(1) 是否找到

#include <set>
void main() {
    set<int> s; // set<int, greater<int>> s;
    s.insert(3);// 不需要迭代器，也不需要指定位置
    s.insert(5);
    s.insert(4); 
    s.insert(3);
    // 重复的插入，并不报错，返回两个值,插入迭代器位置，是否插入成功
    // 返回两个值，构建一个pair
    pair<set<int, greater<int>>:: iterator, bool> res = s.insert(6); 
    bool insert_succeed = res.second;
    if(insert_succeed){
        cout << "插入成功"<< end;
    } else{
        cout << "插入失败"<< end;
    }
    for(set<int>::iterator it=s.begin(); it!=s.end(); it++) {
        cout<< *it << endl;
    }    
}

// 谓词（函数谓词），用来做对比
boolean compare(cosnt Student &_Left, const Student &_Right){
    return _Left.grade > _Right.grade;    
}
// 函数对象：仿函数
struct comparefunction {
    // 重载括号()运算符, 仿函数 
    bool operator()(cosnt Student &_Left, const Student &_Right) const{
        return _Left.grade > _Right.grade;
    }
};
// 对象数据类型,排序
Student: string name; int grade;
void main() {
    // set<Student, greater<Student>> s;
    set<Student, comparefunction> s;
    Student s1("Darren1", 2);
    Student s2("Darren2", 5);
    Student s3("Darren3", 9);
    s.insert(s1);
    s.insert(s2);
    s.insert(s3);
    
    for(set<Student>::iterator it=s.begin(); it!=s.end(); it++) {
        cout<< it->name.c_str() << "~~"<< it->gradle << endl;
    }
}

谓词(函数谓词)：

按照特定的规则，所编写的函数，就叫谓词，他就是个函数。

multiset 允许重复存储的 set容器。用法和set类似，只不过里面元素可以重复。

精华：集合底层的数据结构原理。