About C++ STL

Vector

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<vector>
vector<int> a,b; //缺省所有参数时 size直接为0的
vector<int> a(10) //注意不使用[] 使用()来选定大小 值默认为0

vector<>::reverse_iterator i;//在STL库中定义反向迭代器 
//迭代器可以用来遍历，反向迭代器++之后往前移动 通过加*号的迭代器 也可以直接访问数组元素的值(作为在STL中封装好的指针来使用)
begin(),end(),rbegin(),rend(); //后两个的意思

a.assign(b.begin(),b.begin()+3); //b数组的前3个元素分给a
a.assign(4,2); //4个2

a.back(); a.front(); a[i]; a.clear(); a.empty(); a.pop_back();

//删除a中第一个（从第0个算起）到第二个元素，也就是说删除的元素从a.begin()+1算起（包括它）一直到a.begin()+3（不包括它）结束
a.erase(a.begin()+1,a.begin()+3);
a.push_back(); a.emplace_back(); //两者一样功能 建议使用emplace 优化内存 c++11可以使用

a.insert(a.begin()+1,5); //第一个参数就是插入值之后这个值在数组里的下标！注意使用迭代器(前插)
a.insert(a.begin()+1,3,5); //可以连续插入多个一样的 插入个数是第二个参数
a.inse3rt(a.begin()+1,b+3,b+6); //b是数组，在1号下标插入 b的[3,6)下标元素(不包括最后一个)

a.size();a.capacity(); //返回数组大小 由于在空间不够时vector每次都直接扩大一倍，size返回的是元素的个数 而capacity返回的是现在vector能容纳多少个元素

a.resize(10); //把长度变成10 多删 少补(值随机)
a.resize(10,2); //与上面的区别在于补的数值默认为2
a.reserve(100); //注意和reverse区分 注意：reserve是保留空间，但不创建对象(resize的可以直接调用)


a.swap(b); //交换向量a和b
//b为向量，向量的比较操作还有 != >= > <= <
a==b;
return vector<int>(a.begin(), a.begin()+k) ; 我们可以通过这个语句 来返回数组的 前k项

注意

  1. vector 没有length() 函数

  2. ==vector 只能push_back 和 pop_back 从头插入 使用insert(a.begin(), value)==

  3. ==所有的STL返回整型 全部都是 unsigned long 我们需要在前面加括号 用int型接收它们==

  4. size 和 capicity 大部分时候不需要关注

  5. ==在你直接初始化一个二维数组时 你可以使用memset 也可以这样==

    ==vector<vector<int>> (5, vector<int>(6,1)) 显然 这里用了套娃的属性==

  6. 少使用push_back() 要使用emplace_back();

  7. **vector<pair <int, int> > 或者 vector<vector<int,int> > 在用sort比较时 会先比较first 如果first相同，再比较second **

  • 关于pair
    • Pair 定义有序对 是结构体 调用使用 .first 和 .second 比较时也是先比较first 再比较second

String

1
2
3
4
5
6
7
8
9
10
11
12
#include <cstring> == #include <string.h> //他们都是c语言的字符串库 ⚠️ 它们是不能定义string的 但可以使用字符串函数(如 strcpy)

char* char[] //都可以通过赋值 直接传给字符串对象 但字符串转到char[] 需要用data()或c_str()

string a, b

a.compare(b); //cmp函数 a和b相同返回0 a和b不同返回-1

a.find(b); // 寻找子串 , 未找寻到 返回 string::npos

a.substr(3, 2)  // 从下标3开始 截取2个字符.
a.substr(2) // 从下标2开始的所有字符 (包括2).

注意string::npos的使用

Hash table

  • C++ 17 hash table 遍历 (迭代器遍历则应当注意我们不能通过迭代器更改元素值)

    for (auto& [_, c] : cnt) { maxCnt = max(maxCnt, c); } // first 和 second, 用 _ 也可以不命名

  • 请务必使用(mp.count(element)) 来查看是否存在某个元素, 使用 !mp[element]

    e.g 525. 连续数组

Priority_queue

自实现heap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class min_heap {
public:
    min_heap() { //下标从1开始
        nums.emplace_back(nullhead);
    }
    void Insert(int val) {
        nums.emplace_back(val);
        Shift_up((int)nums.size() - 1);
    }
    void Shift_up(int index) {
        while (index / 2) {
            if (nums[index/2] > nums[index]) swap(nums[index], nums[index/2]); //由于向下取整 2i 和 2i+1 对应的双亲只要除2就能到
            index /= 2;
        }
    }
    int heap_top() {
        return this->nums[1];
    }
    void heap_delete(int index) {
        if (nums.size() == 1) {
            cout << "ERROR";
            return;
        }
        nums.erase(nums.begin() + 1 + index);
        heap_sort();
    }
    void heap_sort() {
        int index = (int)nums.size() - 1;
        while (index > 1) {
            Shift_up(index);
            index --;
        }
    }
    void heap_print() { //用来测试
        for (int i = 1; i < nums.size(); ++i) {
            cout << nums[i] << " ";
        }
        cout << endl;
    }
private:
    vector<int> nums;
};

要点：

  1. 上浮「shift_up」操作的关键在于 我们取1开始 两个孩子分别是 2i 和 2i+1 它们俩除2 可以同时到达双亲节点
  2. 我们把上浮定义成 可以指定任何一个下标 上浮。 这样的好处是 之后的 heap_sort 以及 Insert 函数 都很方便写了 「heapsort就是把每个元素都上浮，insert就是加到末尾然后上浮」
  3. 要注意的是 下标从1 开始 返回top的时候不要用front！

⚠️ 优先队列是一种数据结构 但堆不是 堆是优先队列的内部实现方式

普通方法

  • priority_queue<int> q;//等价于默认，从大到小排
  • priority_queue<int, vector<int>, less<int>> q;//等价于默认，从大到小排
  • priority_queue<int, vector<int>, greater<int>> q; 　　//通过操作，按照元素从小到大的顺序出队
  • priority_queue<TreeNode*, vector<TreeNode*>, decltype(cmp)> q{cmp};

自定义优先级

1
2
3
4
5
6
7
8
9
10
11
12
13
struct cmp {
    bool operator ()(int a, int b) {    //通过传入不同类型来定义不同类型优先级
        return a > b;    //最小值优先
      //return a < b; // 最大值优先
    }
};
priority_queue<int, vector<int>, cmp > q;

//或者可以使用这种方式定义
auto cmp = [](const TreeNode* a, const TreeNode* b) {
    return a->val > b->val;
};
priority_queue<TreeNode*, vector<TreeNode*>,  decltype(cmp)> q{cmp};

自定义结构体、优先级

1
2
3
4
5
6
7
8
9
10
11
12
13
14
struct node {
    int priority;
    int value;
    friend bool operator < (const node &a, const node &b) {
        return a.priority < b.priority;
    }
    /* 这样写也可以
    bool operator < (const node &a) const {
        return priority < a.priority;
    }
    */
};

priority_queue<node> q;

因为标准库默认使用元素类型的 < 操作符来确定它们之间的优先级关系。而且自定义类型的 < 操作符与 > 操作符并无直接联系，故会编译不过。

错误示范：

1
2
3
4
5
6
7
struct node {
 int priority;
 int value;
 friend bool operator > (const node &a, const node &b) {   //错误示范
     return a.priority > b.priority;
 }
};

decltype关键字 ( C++11 )

decltype，在C++中，作为操作符，用于查询表达式的数据类型.

有时我们希望从表达式的**类型推断**出要定义的**变量类型**，但是不想用该表达式的值初始化变量 ( 如果要初始化就用auto了 )。为了满足这一需求，C++11新标准引入了decltype类型说明符，它的作用是**选择并返回操作数的数据类型**，在此过程中，编译器**分析**表达式并得到它的类型，却**不实际计算**表达式的值。

基本用法

1
2
3
4
5
6
7
8
9
10
int getSize();
int main() {
    int tempA = 2;
    
    /*1.dclTempA为int*/
    decltype(tempA) dclTempA;
    /*2.dclTempB为int，对于getSize根本没有定义，但是程序依旧正常，因为decltype只做分析，并不调用getSize，*/
    decltype(getSize()) dclTempB;
    return 0;
}

与 const 结合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
double tempA = 3.0;
const double ctempA = 5.0;
const double ctempB = 6.0；
const double *const cptrTempA = &ctempA;
/*1.dclTempA推断为const double（保留顶层const，此处与auto不同）*/
decltype(ctempA) dclTempA = 4.1;
/*2.dclTempA为const double，不能对其赋值，编译不过*/
dclTempA = 5;
/*3.dclTempB推断为const double * const*/
decltype(cptrTempA) dclTempB = &ctempA;
/*4.输出为4（32位计算机）和5*/
cout<<sizeof(dclTempB)<<"    "<<*dclTempB<<endl;
/*5.保留顶层const，不能修改指针指向的对象，编译不过*/
dclTempB = &ctempB;
/*6.保留底层const，不能修改指针指向的对象的值，编译不过*/
*dclTempB = 7.0;

与引用结合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int tempA = 0, &refTempA = tempA;

/*1.dclTempA为引用，绑定到tempA*/
decltype(refTempA) dclTempA = tempA;
/*2.dclTempB为引用，必须绑定到变量，编译不过*/
decltype(refTempA) dclTempB = 0;
/*3.dclTempC为引用，必须初始化，编译不过*/
decltype(refTempA) dclTempC;
/*4.双层括号表示引用，dclTempD为引用，绑定到tempA*/
decltype((tempA)) dclTempD = tempA;

const int ctempA = 1, &crefTempA = ctempA;

/*5.dclTempE为常量引用，可以绑定到普通变量tempA*/
decltype(crefTempA) dclTempE = tempA;
/*6.dclTempF为常量引用，可以绑定到常量ctempA*/
decltype(crefTempA) dclTempF = ctempA;
/*7.dclTempG为常量引用，绑定到一个临时变量*/
decltype(crefTempA) dclTempG = 0;
/*8.dclTempH为常量引用，必须初始化，编译不过*/
decltype(crefTempA) dclTempH;
/*9.双层括号表示引用,dclTempI为常量引用，可以绑定到普通变量tempA*/
decltype((ctempA))  dclTempI = ctempA;

与指针结合

1
2
3
4
5
6
int tempA = 2;
int *ptrTempA = &tempA;
/*1.常规使用dclTempA为一个int *的指针*/
decltype(ptrTempA) dclTempA;
/*2.需要特别注意，表达式内容为解引用操作，dclTempB为一个引用，引用必须初始化，故编译不过*/
decltype(*ptrTempA) dclTempB;

decltype 总结

decltype和auto都可以用来推断类型，但是二者有几处明显的差异：

1.auto忽略顶层const，decltype 保留顶层 const；

2.对引用操作，auto推断出原有类型，decltype推断出引用；

3.对解引用操作，auto推断出原有类型，decltype推断出引用；

4.auto推断时会实际执行，decltype不会执行，只做分析。

总之在使用中过程中和const、引用和指针结合时需要特别小心。

Lambda 与 decltype 结合

1
2
3
4
5
vector<int> counts(26, 0);
auto cmp = [&](const char& letter1, const char& letter2) {
						return counts[letter1 - 'a']  < counts[letter2 - 'a'];
};
priority_queue<char, vector<char>,  decltype(cmp)> qu{cmp};
#C++ #Programming #Data Structure
About C++ STL
https://www.mementos.top/1976/04/01/about C++ STL/
作者
Natsumi
发布于
1976年4月1日
许可协议