STL二

迭代器失效

为什么使用insert插入元素的时候迭代器可能会指向一个随机值？

因为如果插入的元素过多，那么vector就会发生扩容，然后把之前的数据复制到另一个新开辟的空间里了，然后迭代器所指的位置还是之前的位置，变成野指针了，因此它的值就可能是随机值了，并且继续插入的话，那就是在旧空间继续插入，也就是操纵野指针，是未定义行为了，可能会导致程序崩溃。

这个问题称为迭代器失效，解决办法：每次在使用迭代器之前就把迭代器重新置位一下

1
2
3
it = vec.begin();
it += 2;
//... 使用迭代器

vector的erase操作

1
2
3
4
5
6
7
8
vector<int> number = {4,4,4,4,3,4,2,1,5,6,7,4};
//删除所有等于4的元素
for(auto it = number.begin(); it != number.end(); ++it){
    if(4 == *it){
        number.erase(it);
    }
}
//结果发现并没有把所有的四删掉

为什么没有把所有的四删掉呢？

因为每次删掉元素之后，vector中所有的元素都需要往前移动，那这样就会导致一种情况，那就是如果当前位置是4，下一个位置也是4，那么删掉当前位置的元素之后，下一个位置移动到当前位置，实际上，移动到当前位置的元素仍然符合条件，应该删除，但是上面的逻辑并没有继续进行判断， 而是将迭代器向后移动了，那就把这个元素给保留下来了，所以没有把所有的四删掉

修改为：

1
2
3
4
5
for(auto it = number.begin(); it != number.end(); ++it){
    while(4 == *it){
        number.erase(it);
    }
}

list不会出现这样的问题，因为list删除元素不会导致容器元素移动，但是list删除需要接受一下迭代器，因为不接受的话，迭代器变成野指针了

1
2
3
4
5
6
7
8
for(auto it = number.begin(); it != number.end(); ){
    if(4 == *it){
        it = number.erase(it);
    }
    else{
        ++it;
    }
}

清空操作

1
2
3
4
number.clear();
//只是元素删除掉了，但是并没有回收空间
number.shrink_to_file();
//将多余的空间回收掉

deque是没有capacity函数的

1
deq.capacity();//error

也有clear和shrink_to_file函数

1
2
deq.clear();
deq.shrink_to_file();

list没有capacity和shrink_to_file函数，主要是list也不需要这俩，因为额list没有多余的空间，并且list的size和capacity是一样的

总结：三种序列式容器都有clear函数进行清空元素，以及获取元素个数的size函数，对于vector与deque而言，还有回收多余空间的函数shrink_to_file函数，对于vector还有记录容量大小的函数capacity

swap函数

可以交换两个容器的内容，三个序列式容器都支持

1
2
num1.swap(num2);
//num1和num2的元素发生交换

resize函数

针对于vector的如果指定新的size是旧容量的一倍以上两倍一下，那么就按两倍的扩容，如果是两倍以上的话，那就是把容量扩成指定的新size

如果指定的大小小于旧容量，就会从末尾开始删元素直至与指定大小相同

该函数list vector deque都拥有

emplace_back函数

1
2
num1.emplace_back(1);
//同push_back往后面加一个元素

和push_back之间的区别：

如果是自定义类型

1
2
3
4
5
6
class Point{
    ...
};

vec.push_back(Point(1,2));//又要构造又要拷贝
vec.emplace(1,2);//不需要Point关键字，并且不需要进行拷贝

emplace的效率更高，因为少了一次拷贝构造

对于deque还有emplace_front函数

reserve函数

用来预留空间的

front/back函数

获取容器的第一个元素/最后一个元素

list的一些特殊操作

sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
list<int> li = {1,4,2,3};
li.sort();//默认按照从小到的顺序排列

//传入比较器
li.sort(std::less<int>());//std::less<int>()相当于创建了一个临时对象

//或者创建局部变量
std::less<int> tmp;
li.sort(tmp);

//更改比较规则
li.sort(std::greater<int>());

//需要自定义比较规则
struct CompareList{
  bool operator()(const int& lhs,const int &rhs)const{
      return lhs < rhs;
  }  
};

li.sort(CompareList());//同样也是使用无参构造传入一个临时对象

std::less与std::greater是两个类型，less等价于执行了小于符号，greater等价于执行了大于符号

同样CompareList也是自定义了比较规则，这样的写法称为函数对象的写法

reverse函数

逆置函数

1
li.reverse();//将列表元素逆置

unique函数

去重函数，去掉的是去掉连续重复的元素

1
li.unique();

如果想要去除所有重复的元素，使用配合sort使用

1
2
li.sort();
li.unique();

merge函数

合并两个链表

1
2
3
4
5
6
7
8
9
10
11
12
li.merge(li2);
//发现合并完成之后，只是把li2的元素加到了li的后面
//如果想让合并完成之后仍然可以保持有序
li.sort();
l2.sort();
li.merge(li2);
//发现合并完成之后也是有序的
//那让从大到小排序然后合并可以让合并完成之也是有序的吗
li.sort(greater<int>());
li2.sort(greater<int>());
li.merge(li2);//发现又乱序了，所以想要合并完之后让链表保持有序，只能是按照从小到大的顺序进行排序，然后再merg。
//并且合并完成之后，li2就变成空了

splice函数

把另一个链表的全部元素/迭代器所指的元素/迭代器范围内的元素 移动到调用该函数的链表中迭代器所指的位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
list<int> li = {1,2,3,4,2,232,332,4,34};
list<int> li2 = {1123,1,432,4,2234,23,4,232,2877};
auto it = li.begin();
++it;
++it;

li.splice(it, li2);//li2的元素全部移动到了li迭代器所指的元素的前面

auto it2 = li2.begin();

li.splice(it, li2, it2);


auto it3 = li3.end();
--it3;

li.splice(it,li2,it2,it3);//是一个左闭右开的区间，it3所指的元素是取不到的

问题：splice里面的第二个参数（被移动元素的链表）和调用该函数的链表可以是同一个吗？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//在同一个链表中的操作
it = li.begin();
++it;
++it;
it2 = li.end();
--it2;
--it2;
--it2;

it3 = li.end();
--it3;

//搞了一个范围 it指向第三个元素  it2指向倒数第三个元素  it3指向倒数第一个元素
li.splice(it, li, it2, it3);
//这样操作的结果就是把it2, it3之间的元素移动到了it的前面，这么做是有风险的加入 it在it2 和it3之间 的话，移动就可能发生bug

一些问题

vector扩容不是会按两倍扩容吗，为什么insert插入元素的时候有时候不遵循这个规则呢？

设capacity为n ,size为m 插入元素的个数为t

情况一：t < n - m 就不会扩容

情况二：n - m < t < m,就会按照size的两倍进行扩容

情况三： n - m < t < n; t > m ,就会按照t+m进行扩容

情况四：n - m < t , t > n;也会按照t+m进行扩容

对于push_back而言，每次插入元素的个数是固定的，只要原始的空间大小不是0，那么每次按照两倍的扩容肯定是够的，但是对于insert插入而言，因为并不知道每次插入元素的个数是多少，所以不能按照某个值的两倍进行扩容

关联式容器

set和multiset

set不能出现重复值，并且会自动排序，默认是按从小到大

multiset可以有重复值，下面只写不同的，相同的不再赘述

构造函数

跟vector类似，但是少了一个count构造的，因为set没有重复值，而count构造是构建一个具有n个相同元素的容器，所以没有

1
2
3
4
5
set<int> s = {2,34,1,1,5,6};


//希望让从大到小排序
set<int, std::greater<int>> s = {2,34,1,1,5,6};

multiset构造方式跟set是完全一样的，但是k值可以不唯一

查找

有两种方法：count和find

1
2
3
4
5
6
7
8
size_t cnt = s.count(34);

set<int>::iterator it = s.find(34);
if(it!= s.end()){
    //存在
}else{
    //不存在
}

multiset查找迭代器要找的元素如果是有重复值的，那么迭代器指向的元素是指向第一个目标元素的

lower_bound和upper_bound

lower_bound返回第一个大于等于传入key的元素的迭代器

upper_bound返回第一个大于传入key的元素的迭代器

1
2
3
4
multiset<int> ms = {1,1,1,1,11,2,3,3,3,3,34,5,6,7};

auto it = ms.lower_bound(3);
auto it2 = ms.upper_bound(3);

equal_range

传入一个key值，返回一个pair<iterator,iterator> 第一个迭代器指向的是大于等于给定key的迭代器，第二个迭代是指向的是大于给定key的迭代器

1
2
3
4
5
6
pair<multiset<int>::iterator,multiset<int>::iterator> ret = number.equal_range(3);
while(ret.first != res.second){
    //有值 打出来
    cout << *ret.first << " ";
    ++ret.first;
}

insert

返回值是一个pari<iterator,bool> 因为插入可能成功也可能失败，插入失败bool就为false,itertaor就为空

并且可以传一个元素，,传大括号也可以传迭代器范围也可以

1
2
3
4
5
6
7
8
9
10
11

pair<set<int>>::iterator, bool> ret = number.insert(100);
if(ret.second){
    //插入成功
}else{
    //插入失败
}

vector<int> vec = {1,2,3,4,5};
s.insert(vec.begin(),vec.end());
s.insert({3,4,5,325,63423,57324});

multiset的insert的返回值没必要是pair类型了，因为可以有重复的值，那插入元素就一定是成功的了，pair的second一定是true了，没什么意义了，所以insert的返回值变成iterator了

emplace_hint

erase

删除一个元素或者一定范围的元素

swap

交换两个set的元素

不支持下标操作

1
s[0];//error

不支持修改容器内元素的值

因为底层是由红黑树实现的，所以不允许通过迭代器修改元素的值，因为修改值会改变红黑树的结构

往set中存自定义类型

对于set容器而言，如果传递的类型key是自定义类型，那么第二个模板参数Compare就需要改写，改写的方式由如下几种，要么直接改写std::less，要么给Compare重新传递一个模板参数，而std::less本质上就是在比较两个自定义类型的小于符号，所以可以有小于符号的重载；可以将std::less针对于自定义类型及进行特化；可以自己实现一个类，重载函数调用运算符（写法类似std::less）,最终，set针对于自定义类型而言有三种改写方法：==模板特化，运算符重载，函数对象==

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
43
44
45
46
47
#include <math.h>

class Point{
public:
    Point(int x,int y)
    :_ix(x)
    ,_iy(y)
    {}
    friend ostream & operator<<(ostream& os,const Point &rhs);
    
    double getDistance(){
        return hypot(_ix,_iy);
    }
    friend bool operator<(...);
private:
    int _ix;
    int _iy;
}
ostream & Point::operator<<(...){
    ...
}

bool operator<(const Point &lhs, const Point &rhs){
    if(lhs.getDistance() < rhs.getistance()){
        return true;
    }else if(lhs.getDistance() == rhs.getDistance()){
        if(lhs._ix < rhs._ix){
            return true;
        }
        else if(lhs.ix == rhs._ix){
            if(lhs.iy < rhs.iy){
                return true;
            }else{
                return false;
            }
        }else{
            return false;
        }
    }else{
        return false;
    }
    
}


set<Point> s = {Point(1,2), Point(3,4), Point(5,6)};//比较逻辑也会有问题，也需要自定义
print(s);//会有问题，因为自定义类型还需要重载输出流运算符

重载小于符号可以，但是重载大于符号行不行？

不可以，因为模板的Compare默认是less,没有设定Compare的时候，只能重载<即小于符号

模板的特化

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
43
44
45
46
47
48
49
50
51
class Point{
public:
    Point(int x,int y)
    :_ix(x)
    ,_iy(y)
    {}
    friend ostream & operator<<(ostream& os,const Point &rhs);
    
    double getDistance(){
        return hypot(_ix,_iy);
    }
	friend bool operator<(...);
	int getX(){
        return _ix;
    }
    int getY(){
        return _-iy;
    }
    
    
private:
    int _ix;
    int _iy;
}
//命名空间是可以进行无限扩展的
namespace std{
//模板的特化，全特化
templast <>
struct {
    bool less<Point>(const Point &lhs,const Point &rhs)const {
    if(lhs.getDistance() < rhs.getistance()){
        return true;
    }else if(lhs.getDistance() == rhs.getDistance()){
        if(lhs.getX() < rhs.getX()){
            return true;
        }
        else if(lhsgetX() == rhs.getY()){
            if(lhs.iy < rhs.iy){
                return true;
            }else{
                return false;
            }
        }else{
            return false;
        }
    }else{
        return false;
    }
}
};
}

也可以自定以Compare类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
struct ComparePoint{
  bool operator()(const Point &lhs,const Point &rhs)const {
      if(lhs.getDistance() < rhs.getistance()){
        return true;
    }else if(lhs.getDistance() == rhs.getDistance()){
        if(lhs.getX() < rhs.getX()){
            return true;
        }
        else if(lhsgetX() == rhs.getY()){
            if(lhs.iy < rhs.iy){
                return true;
            }else{
                return false;
            }
        }else{
            return false;
        }
    }else{
        return false;
    }
  }  
};
set<Point,Compare> s;

multiset针对与自定义类型而言，也需要改写第二个模板参数Compare,改写的方法有三种：==模板特化，运算符重载，函数对象==

map

构造函数

1.map存放的是key-value类型，key值是唯一的，不能重复，value值可以相同也可以不同

2.默认会按照key升序排列

3.底层使用红黑树实现的

1
2
3
4
5
6
7
8
9
10
11
map<int,string> m = {
    make_pair(1,"hello"),//利用make_pair返回结果是pair类型
    pair<int, string>(2,"world"),//使用pair的临时对象
    {3,"qie"},//利用大括号构建pair
    {3,"qie"}
}

//每一个e都是一个pair类型，
for(auto & e: m){
    cout << e.first << ", " << e.second << endl;
}