STL四

unordered_multiset

头文件

没有<unordered_multiset>引入的头文件应该是<unordered_set>

与unordered_set的对比

构造函数

与unordered_set的一点区别是可以有重复值

其他操作

例如查找，等其他操作也是完全一样的

针对自定义类型

写法与unordered_set是完全一样的，也要实现模板参数Hash和KeyEqual

unordered_multimap

头文件

#include <unordered_map>

与unordered_map的对比

key值是可以重复的，并且不支持下标操作了

总结：

1.无序关联式容器的底层实现是哈希

2.无序关联式容器中的元素是没有顺序的

3.无序关联式容器中，只有unordered_map具备下标

容器的选择

1.元素是不是有序的

首先想到关联式容器，最不应该想到的是无序关联式容器，其次才是序列式容器

2.容器有没有下标

可以进行下标操作的容器

序列式容器：vector deque

关联式容器：map

无序关联式容器:unordered_map

这些下标操作只能被非常量容器使用，因为下标操作可能涉及修改元素

3.查找的时间复杂度

序列式容器：O(N)

关联式容器：O(logN)

无序关联式容器：O(1)

4.迭代器的类型

随机访问迭代器：vector deque

双向迭代器：list 关联式容器

前向迭代器：无序关联式容器

容器适配器

stack

queue

priority_queue的使用

1.模板参数

2.构造函数

头文件

#include <queue>

初始化

1
priority_queue<int> pque = {1,2,3};//error没有提供大括号的写法
1
2
3
//迭代器范围
vector<int> vec = {1,2,4,4,,23,42,34,23,45};
priority_que<int> pque(vec.begin(),vec.end);

3.遍历

1
2
3
4
for(auto &elem:pque){//error  没有迭代器做支撑，用不了这种方法
    
}
pque[0];//error 也没有下标访问操作
1
2
3
4
5
6
//遍历只能将元素一一弹出然后遍历
while(!pque.empty()){
    cout << pque.top() << endl;
    pque.pop():
}
//发现打印的顺序是从大到小，但是默认的排序不是std::less吗 按理来说打印的顺序应该是从小到大
1
2
3
4
5
6
7
8
9
//探究
for(size_t idx = 0; idx != vec.size(); ++idx){
    pque.push(vec[idx]);
    cout << "优先级最高的元素"<<pque.top() << endl;//发现每次都是把最大值向上顶，说明优先级队列底层的排序方法使用的是大根堆，
}
while(!pque.empty()){
    cout << pque.top() << endl;
    pque.pop():
}

原理：当插入元素的时候，就需要重新调整堆的结构，当堆顶元素比新插入的元素要小，也就是满足std::less，那么新插入的元素会作为新的堆顶，当堆顶比新插入的元素要大，就不满足std::less就不会置换，也就是老的堆顶依旧是堆顶。

基本操作

1
2
3
4
5
插入操作：push;
获取顶部元素：top;
删除顶部元素：pop;
容器是不是空的：empty;
元素个数的函数:size();

注意：容器适配器是没有迭代器的，所以不能使用迭代器进行遍历

存储自定义类型

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
52
53
54
55
56
57
58
59
60
61
62
63
#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;
    }
    
}



priority_queue<Point> pque;
vector<Point> vec = {
    Point(1,2),
    Point(3,4),
    Point(4,5),
    Point(7,8)
}

for(size_t idx = 0; idx != vec.size(); ++idx){
    pque.push(vec[idx]);
    cout << pque.top() << endl;
}

while(!pque.empty()){
    cout << pque.top() << " ";
    pque.pop();
}

除了可以函数重载<还可以进行模板的特化，函数对象等方法

迭代器

流迭代器

ostream_iterator

1
ostream_iterator<int> osi(cout,"\n");
1
2
3
4
5
6
#include <algorithm>

vector<int> vec = {1,2,3,4};
ostream_iterator<int> osi(cout,"\n");
copy(vec.begin(),vec.end(),osi);
//效果 将1234输出到了屏幕上 实现了遍历容器的效果

数据是怎么输出到屏幕上的呢？

正常输出一个数据是这样的cout << 1 << "\n"cout ,1,”\n”都有，就剩一个<<没有，但是底层实现的时候把<<给重载了

istream_iterator

1
2
3
vector<int> vec;
istream_iterator<int> isi(cin);
copy(isi,istream_iterator<int>(),vec.begin());

把isi,istream_iterator这个里面的元素放到第三个参数里面，第三个参数要求一个OutPutIt迭代器，但是vector是一个随机访问迭代器，是OutPutIt的派生类，所以也是可以的，当然也可以传一个ostream_ierator

1
copy(vec.begin(),vec.end(),osteream_iterator<int>(cout, " "));//遍历容器内的数据，将vector中的元素进行输出

运行结果是等待输入，然后输入数据后回车发生了段错误，主要是因为vec没有空间，vec.begin()是一个野指针导致的错误

采用新方法使用back_inserter

1
2
3
4
vector<int> vec;
istream_iterator<int> isi(cin);
copy(isi,istream_iterator<int>(),std::back_inserter(vec));
copy(vec.begin(),vec.end(),osteream_iterator<int>(cout, " "));

应用

将list的元素插入到vec的尾部

1
2
3
4
5
6
7
vector<int> vec = {1,3,5};
list<int> lstNum = {2,6,8,4,10};
copy(list.begin(),list.end(),back_inserter(vec));
//也可以写
copy(list.begin(),list.end(),back_insert_ioterator<vector<int>>(vec));
//输出
copy(vec.begin(),vec.end(),ostream_iterator<int>(cout,' '));

front_inserter和front_insert_iterator

与back_insert_iterator基本一致

1
2
3
4
copy(vec.begin(),vec.end(),front_insert_iterator<list<int>>(lstNum));
//或者
copy(vec.begin(),vec.end(),front_inserter(lstNum));
//效果是vec里面的元素反着插到list的头部了，因为是头插法

但是这个有一定的局限性，如果是要把list的元素插入set或者vector里面，那么就不可以用了

inserter

1
2
3
4
5
6
set<int> setNum = {2,4,6,1,4,7,8};
//需要两个参数 ，容器，以及容器的待插入位置的迭代器
auto it = setNum.begin();
copy(vec.begin(),vec.end(),inserter(setNum,it));
//打印
copy(setNum.begin(),setNum.end(),ostream_iterator<int>(cout,' '));

back_inserter是函数模板，该函数的返回类型是back_insert_iterator类型，底层会调用push_back

front_inserter是函数模板，该函数的返回类型是front_insert_iterator类型，底层会调用push_front

inserter是函数模板，该函数的返回类型是insert_iterator类型，底层会调用insert函数

反向迭代器reverse_iterator

rbegin指向的是容器的最后一个元素，rend指向的容器的第一个元素的前一个位置

1
2
3
4
5
6
7
8
9
10
11
vector<int> vec = {1,4,3,2,5,7};
vector<int>::iterator it = vec.begin();
for(;it != vec.end(); ++it){
    cout << *it << " ";
}
//想要反着打容器内的元素
vector<int>::iterator it2 = vec.rbegin();
for(;it2 != vec.rend();++it2)//注意第三个参数是++，而不是--
{
    cout << *it << endl;
}

下午练习：

第一题

Leetcode 146 LURCache的实现

普通版本

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
52
53
54
55
56
57
58
59
60
61
class LRUCache {
public:
    LRUCache(int capacity) 
    :_size(capacity)
    {
        _kv.reserve(capacity);
    }
    
    int get(int key) {
        if(_kv.find(key)!=_kv.end()){
            auto it = _que.begin();
            for(;it != _que.end(); ++it){
                if(*it == key) {
                    _que.erase(it);
                    break;
                }
                
            }
            _que.push_front(key);
            return _kv[key];
        }
        else return -1;
    }
    
    void put(int key, int value) {
        if(_kv.find(key) != _kv.end()){
            
            auto it = _que.begin();
            for(;it != _que.end(); ++it){
                if(*it == key) {
                    _que.erase(it);
                    break;
                }
            }
            _que.push_front(key);
            _kv[key] = value;
            return;
        }
        if(_kv.size() < _size ){
            _kv[key] = value;
            _que.push_front(key);
        }else{
            int oldkey = _que.back();
            auto it = --_que.end();
            _que.erase(it);
            _kv.erase(oldkey);
            _kv[key] = value;
            _que.push_front(key);
        }
    }
    unordered_map<int,int> _kv;
    list<int> _que;
    int _size;
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */

普通版本没有使get和put 的时间复杂度到达O(1)但是比较好理解

高效版本

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
52
class LRUCache {
public:
    LRUCache(int capacity) 
    :_size(capacity)
    {
        _timeout.reserve(capacity);
    }
    
    int get(int key) {
        auto it = _timeout.find(key);
        if(it != _timeout.end()){
            //说明找到了
            _ele.splice(_ele.begin(),_ele,it->second);
            return it->second->second;
        }
        return -1;
    }
    
    void put(int key, int value) {
        auto it = _timeout.find(key);
        if(it != _timeout.end()){
            _ele.splice(_ele.begin(),_ele,it->second);
            it->second->second = value;
            return;
        }
        if(_timeout.size() < _size){
            _ele.push_front(pair<int,int>(key,value));
            _timeout[key]=_ele.begin();
        }
        else{
            int oldkey = _ele.back().first;
            _timeout.erase(oldkey);
            _ele.pop_back();
            _ele.push_front(pair<int,int>(key,value));
            _timeout[key]=_ele.begin();
        }


    }

    unordered_map<int,list<pair<int,int>>::iterator> _timeout;
    list<pair<int,int>> _ele;
    int _size;

};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */

高效版本通过存储迭代器来在O(1)的平均时间复杂度内来找到需要更改的元素

第二题

Q:无序关联式容器有哪些？各自具有哪些特点？

A:unordered_map

特点：存储键值对，通过哈希表实现快速查找，每个键值对中的键都必须是唯一的

unordered_set

特点：存储唯一的元素集合，通过哈希表实现快速查找

unordered_multimap:

特点：允许存储重复的键值对，通过哈希表实现快速查找

unordered_multiset：

允许存储重复的元素集合，通过哈希表实现快速查找

第三题

涉及图论，使用广度优先搜索，只要找到一个符合条件的一定是最短的，暂时跳过 等看到图论重新看

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
class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> wordSet(wordList.begin(),wordList.end());
        if(wordSet.find(endWord) == wordSet.end()) return 0;
        unordered_map<string,int> visitMap;

        queue<string> que;
        que.push(beginWord);
        visitMap.insert(pair<string,int>(beginWord,1));

        while(!que.empty()){
            string word = que.front();
            que.pop();
            int path = visitMap[word];
            for(int i = 0; i < word.size(); ++i){
                string newWord = word;
                for(int j = 0; j < 26; ++j){
                    newWord[i] = j +'a';
                    if(newWord == endWord) return path+1;
                    if(wordSet.find(newWord) != wordSet.end() && visitMap.find(newWord) == visitMap.end()){
                        visitMap.insert(pair<string,int>(newWord,path+1));
                        que.push(newWord);
                    }
                }
            }
        }
        return 0;
    }
};