Summary1.2 数据结构 STL整合

#include <list>

list<int> linklist;

int main() {
  // 往链表头部插入元素
  linklist.push_front(2); // 2
  linklist.push_front(1); // 1 2
  // 往链表尾部插入元素
  linklist.push_back(3); // 1 2 3
  
  // 链表排序
  linklist.sort();
  // 链表去重
  linklist.unique();
  // 链表长度
	int linklistlen = linklist.size();
}

// 功能描述 => 查找出现单次的,并尽可能的节省空间
#include <map>

map<int, bool> m;

// map两种遍历方式
// map利用迭代器进行遍历，需要设置迭代器并且指向对应的map
map<int, bool>::iterator iter = m.begin(); 
// 或者通过auto来声明：
auto iter2 = m.begin();
while(iter != m.end()) {
  cout<<"key = "<<iter->first<<"       value = "<<iter->second<<endl;
  iter++;
}
// map遍历利用最新的C++17的写法进行遍历,C++11/13/15都是不支持的
for (auto [k, v]: m) cout<<"key = "<<k<<"       value = "<<v<<endl;


// map边遍历边移除
for (1~n) {
  cin>>t;
  if (m.count(t))  m.erase(t); // m.count(t) 返回0或1，数出现次数，map只允许一个key出现一次，所以只有0或1 m.erase(t)移除掉t的key所对应的那个项
  else m[t] = true;
}

// 迭代器的移动 => 迭代器只能进行自增操作，也即只能进行 iter++或者iter--，无法进行其他操作
if (iter->first > (--iter)->first) {printf("当前迭代器的key比他前面的迭代器的key的值要大");}

#include <set>
set<int> s;

s.insert(1);
s.insert(4);
s.insert(2);
s.insert(1);

for (int i: s) printf("%d ", i); // 1 2 4 首先会有序，其次会把重复的删掉

int a[10]和b[10] = {7,1,1,90,1,4,4,4,5,1}, n = 10; // 数据

// 去重
int newn = unique(a, a+n)-a; // 利用unique去重，返回的值是去重之后的数组的长度
for (int i = 0; i < newn; ++i) printf("%d ", a[i]); // 7 1 90 1 4 5 1 

// 区间语法
// 0~n-1 => n => sort(a, a+n), unique(a, a+n)-a
// 1~n => n => sort(a+1, a+n+1), unique(a+1, a+n+1)-a-1

// 离散化（首先排序，然后去重得到真实位次，最后进行对应）
sort(a, a+n); // 首先排序
int nn = unique(a, a+n)-a; // 然后得到真实的每个数的位次
for (int i = 0; i < n; ++i) b[i] = lower_bound(a, a+nn, b[i])-a;
for (int i = 0; i < n; ++i) printf("%d ", b[i]);

#include <vector>
vector<int> b;
#include <algorithm>

int main(){
  // 向量末尾插入元素
  b.push_back(1);
  // 向量开头插入元素
  b.insert(b.begin(), 2); // 2 1
  // 向量任意位置插入
  int idx = 1;
  b.insert(b.begin()+idx, 3); // 2 3 1 idx为1插入到索引为1的地方
  // 移除
  b.erase(b.begin()+idx); // 2 1 idx为1移除
  // 带迭代器iteration的可以调整整个序列方向 => 注意是reverse，不是reserve；而且不是b.reverse,是外部的方法，包含在algorithm库中
  reverse(b.begin(), b.end()); // 1 2
  // 排序，sort外部的方法，包含在algorithm库中
  sort(b.begin(), b.end());
  // 查找
  auto iter = find(b.begin(), b.end(), target_num);
  if (iter != b.end()) printf("找到了");
  else printf("没找到");
  // 易错：vector移除队尾元素
  b.erase(b.end()); // 会报错，因为b.end()实质上不是向量的最后一个，而是最后一个的下一个，就像find函数，看他是否有找到的实质就是看迭代器是否到了最后一个之后的end，而不是最后一个
  b.pop_back(); // 正确写法
  
  // 三种遍历方式
  for (int i = 0; i < b.size(); i++) {b[i]}
  for (int num: b) {num} / for (node nd: b) {nd.x, nd.y}
  for (auto it = b.begin(); it != b.end();) {it->x, it->y}
  
  // 边遍历，边移除=>在遍历的时候防止因为越界而报错（通过索引来进行访问，但是不方便移除操作；通过iterator进行访问，方便移除，并且方便将指针指向下一个元素）
  for (auto it = b.begin(); it != b.end();) {
    if (条件) it = b.erase(it); // 保证移除之后指针不会错误
    else it++; // 不移除的话指针自动变化
  }
}

#include <queue>
queue<int> q;

int main(){
  // 往优先队列中添加元素
  q.push(2);
  q.push(1);
  // 获取队首 并 移除队首元素
  int queue_front = q.front(); pq1.pop();
  // 获取队尾
  int queue_back = q.back();
}

#include <queue>
// 小顶堆 - 默认的int为容器中的元素
priority_queue<int, vector<int>, greater<int>> pq1;
// 大顶堆 - 默认的
priority_queue<int> pq2;
// 重载大于号的 - 容器元素为结构体node的
priority_queue<node, vector<node>, greater<node>> pq3;
// 重载小于号的 - 容器元素为结构体node的
priority_queue<node, vector<node>, less<node>> pq4;

int main(){
  // 往优先队列中添加元素
  pq1.push(2);
  pq1.push(1);
  // 获取队首 并 移除队首元素
  int queue_top = pq1.top(); pq1.pop();
  // 优先队列无法获取队尾，只能获取队首
}

// greater => 只能重载 > （大于号），重载成<会报错，因为greater是指利用>的比较方式
struct node{
  int val;
  bool operator > (const node n) const{return val>n.val;} // val的值由小到大
}
priority_queue<node, vector<node>, greater<node>> pq;
// less => 只能重载 < （小于号），重载成>会报错，因为less是指利用<进行比较的方式
struct node{
  int val;
  bool operator < (const node n) const{return val>n.val;} // val的值由小到大
}
priority_queue<node, vector<node>, less<node>> pq;

#include <algorithm>

int main() {
  int a = {1, 3, 6, 7, 14, 15, 18}, n=7; // 提前排好序的 或者 提前先排序的
  int pos1 = lowerbound(a, a+n, 7); // 大于等于7的边界 => 3
  int pos2 = upperbound(a, a+n, 7); // 大于7的边界 => 4
  int b = {18, 15, 14, 7, 6, 3, 1}, n=7; //如果是反向的递减排序
  int pos3 = lowerbound(b, b+n, 7); // 小于等于7的边界 => 3
  int pos4 = lowerbound(b, b+n, 7); // 小于7的边界 => 4
}

std::vector<int> vec {1,2,3,4,5,6,7,8,9,10};
cout << "修改前" << endl;
for (auto& n :vec) // 将遍历的变量声明为引用类型，即可以修改内容
    std::cout << n++;
cout << endl;
cout << "修改后" << endl;
for (auto j : vec)
    std::cout << j;

std::vector<std::string> strs;
cout << "修改前" << endl;
for (auto && s :strs) { // 将遍历的变量声明为引用类型，即可以修改内容
    std::cout << n+;
}

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

int main() {
    string str1 = "abc123def456xyz789t1";
    string str2 = "123456789";

    // 完全匹配-固定字串
    cout<<regex_match(str1, regex("123"))<<"\n"; // 0 完全匹配不同
    cout<<regex_match(str2, regex("123"))<<"\n"; // 0 完全匹配不同
    cout<<regex_match(str1, regex("123456789"))<<"\n"; // 0
    cout<<regex_match(str2, regex("123456789"))<<"\n"; // 1 完全匹配，字符串一模一样

    // 完全匹配-仅通配符
    cout<<regex_match(str1, regex("\\d+"))<<"\n"; // 0 完全匹配不同，因为要求的全是数字，而被匹配中有字符串
    cout<<regex_match(str2, regex("\\d+"))<<"\n"; // 1 完全匹配，被匹配字符串中只有数字

    // 完全匹配-存在外部字符+通配符
    cout<<regex_match(str1, regex("abc123def456xyz(\\d+)"))<<"\n"; // 1 完全匹配，前面要相同部分，后面是通配部分
    cout<<regex_match(str2, regex("abc123def456xyz(\\d+)"))<<"\n"; // 0 完全匹配不同，前面就不同。

    printf("-------------\n");

    // 搜索=>返回列表，用smatch
    // 搜索-固定子串
    smatch search_result;
//    regex_search(str1, search_result, regex("123")); // 用承接的smatch穿进去来得到值
//    cout<<search_result.size()<<"\n";
//    for (int i = 0; i < search_result.size(); ++i) {
//        cout<<search_result[i]<<"\n";;
//    }
    regex_search(str1, search_result, regex("abc(\\d+)def(\\d+)xyz(\\d+)t(\\d+)")); // 用承接的smatch穿进去来得到值
    cout<<search_result.size()<<"\n";
    for (int i = 0; i < search_result.size(); ++i) {
        cout<<search_result[i]<<"\n";;
    }

    return 0;
}