一、C++的STL

1. 智能指针

1.1. auto_ptr

（无论什么情况下都不要使用，C++98标准，到了C++11标注引入了shared_ptr，unique_ptr,，weak_ptr）

1.2. shared_ptr

shared_ptr和auto_ptr最大的区别就是，shared_ptr解决了指针间共享对象所有权的问题，也就是auto_ptr中的赋值的奇怪问题。所以满足了容器的要求，可以用于容器中。而auto_ptr显然禁止共享对象所有权，不可以用于容器中。

（1）默认构造函数，函数参数为变量地址

（2）拷贝构造函数，函数参数为引用

（3）重载函数operator*

（4）重载函数operator->

（5）重载函数operator=，使之可以进行隐性转换操作，注：实际C++源码中是没有这个的，构造函数用关键字explicit声明，在定义对象时必须显示调用初始化式，不能使用赋值操作符进行隐式转换。

（6）空函数判断

（7）引用次数统计函数

注意：使用shared_ptr也要引用头文件#include<memory>，如下使用简单的源码实现

#ifndef _SHARED_PTR_H
#define _SHARED_PTR_H
/*
一个模板T* ptr,指向实际的对象
一个引用次数
重载operator*和operator->,使得能像指针一样使用share_ptr
重载copy constructer，使其引用次数加一
重载operator=，如果原来的shared_ptr已经有对象
*/
template<typename T>
class shared_ptr
{
public:
shared_ptr(T* p) : count(new int(1)),_ptr(p);//默认的构造函数，必须自己显示的开辟内存
shared_ptr(shared_ptr<T>& p):count(&(++p.count)),_ptr(p.ptr);//拷贝构造函数，属于强制转换，显式
T& operator*();//
T* operator->();
shared_ptr<T> & operator=(shared_ptr<T>& p);//重载等号，保证保存同为shared_ptr的指针能够互转，等号计数器减1，右边计数器加1.
~shared_ptr();
bool empty();//检查是否指向同一个空T
int GetCount();
private:
int *count;//引用计数器
T* _ptr;//每创建一个对象，则有一个指针指向一个shared_ptr的类型
};

#include"_shared_ptr.h"
template<typename T>
shared_ptr<T>::shared_ptr(T* p=nullptr):count(new int(1)),_ptr(p)//默认的构造函数，显式开辟内存
{
if(_ptr){
count = new int(1);//如果初始化不为空，则计数器为1
}else{
count = new int(0);//如果初始化为空，则计数器为0
}
}
template<typename T>
shared_ptr<T>::shared_ptr(shared_ptr<T>&p):count(&(++p.count)),_ptr(p.ptr)//拷贝构造函数，属于强制转换，显式
{
if(this != p)
{
this->_ptr = p._ptr;
this->count = p.count;
*(this->count)++;
}
}
template<typename T>
T& shared_ptr<T>::operator*(){
return *(this->_ptr);
}
template<typename T>
T* shared_ptr<T>::operator->(){
return this->_ptr;
}
template<typename T>
shared_ptr<T>& shared_ptr<T>::operator=(shared_ptr<T>& p){
//重载等号，保证保存同为shared_ptr的指针能相互转化，等号左边计数器减1,右边计数器加1.
++*(p.count);//等式右边引用次数加1，左边引用次数减1
if(this->_ptr && 0 == --*this->count) //当左边引用次数为0
{
delete count;
delete _ptr;
}
this->count = p.count;
this->_ptr = p._ptr;
return *this;
}
template<typename T>
bool shared_ptr<T>::empty()//检查是否有一个指向空T，当为空的时候，count必须为0
{
return _ptr == nullptr;
}
template<typename T>
int shared_ptr<T>::GetCount()
{
return *count;
}

1.3. unique_ptr

unique_ptr的构造函数与auto_ptr一样，构造函数采用explicit声明，防止复制/拷贝时不必要的类型转换，在定义对象时必须显示调用初始化式，不能使用赋值操作符进行隐式转换。注：此代码未包含自定义删除器

成员函数：

（1）get函数：获取内部对象的指针，由于已经重载了()方法，因此和直接使用对象是一样的。

（2）release函数：放弃内部对象的所有权，将内部指针置空，此指针需要手动释放。

（3）reset函数：销毁内部对象并接受新的对象的所有权。

（4）默认构造函数，函数参数为变量地址

（5）拷贝构造函数，函数参数为引用

（6）重载函数operator*

（7）重载函数operator->

（8）重载函数operator=

#ifndef UNIQUE_PTR_H
#define UNIQUE_PTR_H
template<typename T>
class _unique_ptr
{
public:
_unique_ptr(T* p = nullptr) :_ptr(p);
//默认构造函数
_unique_ptr(_unique_ptr<T>& p) :_ptr(p._ptr); //拷贝构造函数
T& operator*();
T* operator->();
_unique_ptr<T>& operator=(_unique_ptr<T>& p); //赋值操作符重载
T* get();
T* release();
void reset(T* p);
private:
T * _ptr;
};
#endif

#include"unique_ptr.h"
template<typename T>
_unique_ptr<T>::_unique_ptr(T* p)
{
_ptr = p;
}
template<typename T>
_unique_ptr<T>::_unique_ptr(_unique_ptr<T>& p)
{
_ptr = p.release();
}
template<typename T>
T& _unique_ptr<T>::operator*()
{
return *(this->_ptr);
}
template<typename T>
T* _unique_ptr<T>::operator->()
{
return this->_ptr;
}
template<typename T>
_unique_ptr<T>& _unique_ptr<T>::operator=(_unique_ptr<T>& p)
{
if (p.get() != this->get())
{
delete _ptr;
}
_ptr = p._ptr;
}
template<typename T>
T* _unique_ptr<T>::get()
{
return this->_ptr;
}
template<typename T>
T* _unique_ptr<T>::release()
{
T* tmp = _ptr;
delete _ptr;
return tmp;
}
template<typename T>
void _unique_ptr<T>::reset(T* p)
{
if (p != _ptr)
{
delete _ptr;
}
_ptr = p;
}

4、weak_ptr

   weak_ptr 是一种不控制对象生命周期的智能指针, 它指向一个 shared_ptr 管理的对象. 进行该对象的内存管理的是那个强引用的 shared_ptr。 weak_ptr只是提供了对管理对象的一个访问手段。weak_ptr 设计的目的是为配合 shared_ptr 而引入的一种智能指针来协助 shared_ptr 工作, 它只可以从一个 shared_ptr 或另一个 weak_ptr 对象构造, 它的构造和析构不会引起引用记数的增加或减少。定义在 memory 文件中(非memory.h), 命名空间为 std.

总结：

封装普通指针使其表现的像普通指针一样。超过类的作用域，将会自己调用析构函数，自动释放资源
auto_ptr：不可以用于容器，不建议使用，不支持复制和赋值，如果进行了赋值和复制操作，并不报错
unique_ptr：不支持复制和赋值，直接赋值会报错，同一时刻对象仅能拥有一个unique_ptr指向自身
shared_ptr：解决指针间对象共享所有权的问题，auto_ptr是独享，允许多个指针指向同一个对象。基于引用计数，不要一个原始指针初始化多个shared_ptr，避免循环使用避免内存泄露。
对象初始化时应用数为1，指向对象成为另一个对象副本，引用数加一，析构减一。
weak_ptr：不控制对象生命周期的智能指针，只提供了管理对象的访问手段，用于协助shared_ptr的工作，用于观测资源的使用情况。use_count()可以一观察资源的应用数。

2. 容器

STL有什么基本组成

STL主要由：以下几部分组成：
容器，迭代器，仿函数算法，分配器，配接器
他们之间的关系：分配器给容器分配存储空间，算法通过迭代器获取容器中的内容，仿函数可以协助算法完成各种操作，配接器用来套接适配仿函数

2.1 vector

底层为数组，支持随机访问，节点大小是动态的，支持下标访问。随机存取效率很高（O(1)），插入效率不高。
扩容原理：以原大小的两倍配置一份新空间（看编译器的，vs是1.5，gcc是2），如果要插入的值的数量超过当前容量的两倍，是直接扩容到能容纳所有元素的空间大小，而不会拘泥于多少倍，将原空间数据拷贝过来，会导致迭代器失效。

2.2 list

底层为双向链表，内存空间不连续，只能通过指针访问数据，插入删除高效，随机存取非常没有效率。适用于对象需要大量删除插入操作的环境。
list的iterator不支持+，+=，<操作

list.sort()：合并前两个元素，合并后两个元素，两个子序列合并，序列大小变化顺序为2->4->8->16…完成排序（O(log(n))）

2.3 deque

双向队列，一个中央控制器+多个缓冲区，支持首尾快速增删，支持随机访问。

2.4 stack

底层为deque/list，封闭头部，不使用vector作为底层的原因是vector扩容耗时。

2.5 queue & priority_queue

queue：底层为deque/list，封闭头部，不使用vector作为底层的原因是vector扩容耗时。
priority_queue：优先队列，以vector为底层，以heap为处理规则管理底层实现。

2.6 红黑树为底层的容器

插入删除，查找时间复杂度为O(log(n))
作为关联容器，set不同于map的地方在于，set的key就是value。

2.7 红黑树

红黑树的特点：

根节点是黑色，叶节点是黑色的null节点，任意节点到其叶节点经过的黑色节点数量是相同的。
去除掉黑色null节点，红黑树是一层黑一层红。
红黑树是近平衡的二叉搜索树，和平衡二叉搜索树相比，红黑树的平衡没有那么平衡，插入后可以保证调整三次之间可以使树达到平衡条件

2.8 hash表为底层的容器

查询时间复杂度O(1)，均无序

hash表冲突解决

1、扩大每个桶的容量
2、闭地址：桶后增加溢出链
3、开地址；寻找下一个有空间的桶

3. 容器失效

序列性容器::(vector和list和deque)

erase迭代器不仅使所指向被删元素的迭代器失效，而且使被删元素之后的所有迭代器失效，所以不能使用erase(iter++)的方式，但是erase的返回值为下一个有效的迭代器。

所以正确方法为::

for( iter = c.begin(); iter != c.end(); )
iter = c.erase(iter);

关联性容器::(map和set比较常用)

erase迭代器只是被删元素的迭代器失效，但是返回值为void，所以要采用erase(iter++)的方式删除迭代器，
所以正确方法为::

for( iter = c.begin(); iter != c.end(); )
c.erase(iter++);

删除：Erase

结论：在STL里，我们不能以指针来看待迭代器，指针是与内存绑定的，而迭代器是与容器里的元素绑定的，删除了之后，该迭代器就失效了，在对其重新赋值之前，不能再访问此迭代器。

1.对于序列容器vector,deque来说，使用erase(itertor)后，后边的每个元素的迭代器都会失效，但是后边每个元素都会往前移动一个位置，但是erase会返回下一个有效的迭代器；

2.对于关联容器map set来说，使用了erase(iterator)后，当前元素的迭代器失效，但是其结构是红黑树，删除当前元素的，不会影响到下一个元素的迭代器，所以在调用erase之前，记录下一个元素的迭代器即可。

3.对于list来说，它使用了不连续分配的内存，并且它的erase方法也会返回下一个有效的iterator，因此上面两种正确的方法都可以使用。

插入：Insert

插入一旦让capacity变化之后，所有的迭代器都失效了！capacity发生变化，容器内部做的不仅仅是增加capacity这么简单，因为容器所在内存后面可能没有足够的内存让我们使用，所以，容器要重新开辟一段足够大的内存来存储容器里的元素，当前内存会被释放。这样一来，迭代器自然失效了。

C++ primer 总结：迭代器失效

（1）增加元素到容器后

• 对于vector和string，如果容器内存被重新分配，iterators,pointers,references失效；如果没有重新分配，那么插入点之前的iterator有效，插入点之后的iterator失效；
• 对于deque，如果插入点位于除front和back的其它位置，iterators,pointers,references失效；当我们插入元素到front和back时，deque的迭代器失效，但reference和pointers有效；
• 对于list和forward_list，所有的iterator,pointer和refercnce有效。

（2）从容器中移除元素后

• 对于vector和string，插入点之前的iterators,spointers,references有效；off-the-end迭代器总是失效的；
• 对于deque，如果插入点位于除front和back的其它位置，iterators,pointers,references失效；当我们插入元素到front和back时，off-the-end失效，其他的iterators,pointers,references有效；
• 对于list和forward_list，所有的iterator,pointer和refercnce有效。

（3）在循环中refresh迭代器

• 　　当处理vector,string,deque时，当在一个循环中可能增加或移除元素时，要考虑到迭代器可能会失效的问题。我们一定要refresh迭代器。

• int arr[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
  deque<int> v(arr,arr+sizeof(arr)/sizeof(*arr));
  for (auto it = v.begin(); it != v.end(); )
  {
  if ((*it) & 1)
  {
  it = v.insert(it, *it);
  it += 2;
  }
  else
  it = v.erase(it);
  }

• 　　至于it+=2，很容易解释，insert之后，it指向新增加的元素，+2之后，it指向下一个要处理的元素。

（4）在循环不变式中不要store off-the-end迭代器

　　这个很容易理解了，增加或移除元素之后，off-the-end失效了，不store的话，每次从end()函数中取的都是最新的off-the-end，自然不会失效。

为什么需要迭代器：

Iterator类的访问方式就是把不同集合类的访问逻辑抽象出来，使得不用暴露集合内部的结构而达到循环遍历集合的效果。

STL里resize和reserve的区别

resize()会构造出新的元素，而reserve()只是为元素预留出空间而已。reserve()只是预留空间，而不会构造新的元素出来

STL的allocaotr

STL的分配器用于封装STL容器在内存管理上的底层细节。

在C++中，其内存配置和释放如下：

new运算分两个阶段：(1) 调用::operator new配置内存;(2)调用对象构造函数构造对象内容

delete运算分两个阶段：(1) 调用对象希构函数；(2)掉员工::operator delete释放内存

为了精密分工，STL allocator将两个阶段操作区分开来：

内存配置有alloc::allocate()负责，

内存释放由alloc::deallocate()负责；

对象构造由::construct()负责，

对象析构由::destroy()负责。

同时为了提升内存管理的效率，减少申请小内存造成的内存碎片问题，SGI STL采用了两级配置器，当分配的空间大小超过128B时，会使用第一级空间配置器；当分配的空间大小小于128B时，将使用第二级空间配置器。

第一级空间配置器直接使用malloc()、realloc()、free()函数进行内存空间的分配和释放，

第二级空间配置器采用了内存池技术，通过空闲链表来管理内存。

二、关于内存泄露

2.1 段错误

段错误通常发生在访问非法内存地址的时候，具体来说分为以下几种情况：

• 使用野指针
• 试图修改字符串常量的内容

strcpy()函数

1，检查指针有效性；

2，返回目的指针des；

3，源字符串的末尾 '' 需要拷贝；

4，考虑拷贝时内存重叠。

void * my_memcpy(void *dst,const void *src,unsigned int count)
{
assert(dst);
assert(src);
void * ret = dst;
if (dst <= src || (char *)dst >= ((char *)src + count))//源地址和目的地址不重叠，低字节向高字节拷贝
{
while(count--)
{
*(char *)dst = *(char *)src;
dst = (char *)dst + 1;
src = (char *)src + 1;
}
}
else
//源地址和目的地址重叠，高字节向低字节拷贝
{
dst = (char *)dst + count - 1;
src = (char *)src + count - 1;
while(count--)
{
*(char *)dst = *(char *)src;
dst = (char *)dst - 1;
src = (char *)src - 1;
}
}
return ret;
}

2.2 内存泄漏

内存泄漏(memory leak)是指由于疏忽或错误造成了程序未能释放掉不再使用的内存的情况。内存泄漏并非指内存在物理上的消失，而是应用程序分配某段内存后，由于设计错误，失去了对该段内存的控制，因而造成了内存的浪费。

内存泄漏的分类：

• 堆内存泄漏 （Heap leak）。对内存指的是程序运行中根据需要分配通过malloc,realloc new等从堆中分配的一块内存，再是完成后必须通过调用对应的 free或者delete 删掉。如果程序的设计的错误导致这部分内存没有被释放，那么此后这块内存将不会被使用，就会产生Heap Leak.
• 系统资源泄露（Resource Leak）。主要指程序使用系统分配的资源比如 Bitmap,handle ,SOCKET等没有使用相应的函数释放掉，导致系统资源的浪费，严重可导致系统效能降低，系统运行不稳定。死锁和僵尸进程和孤儿进程。
• 没有将基类的析构函数定义为虚函数。当基类指针指向子类对象时，如果基类的析构函数不是virtual，那么子类的析构函数将不会被调用，子类的资源没有正确是释放，因此造成内存泄露。
• 野指针（未初始化，释放之后未置空，指针操作超越变量的作用域（note:不要还回指向栈内存的指针引用，因为栈内存在函数结束时会被释放））

2.3 关于malloc是在堆，还是映射区分配内存的

malloc实际上是通过调用brk和mmap来分配内存的，如果需要的空间比较小，brk就可以实现，这种情况下就是产生堆区，从堆中分配内存，但是如果需要的空间比较大，就会通过mmap实现，这种情况下就是不产生堆区，直接从匿名内存映射区来分配内存

2.4 new和malloc的区别

• 属性：new/delete是C++关键字，需要编译器支持。malloc/free是库函数，需要头文件支持。
• 参数：使用new操作符申请内存分配时无须指定内存块的大小，编译器会根据类型信息自行计算。而malloc则需要显式地指出所需内存的尺寸。
• 返回类型：new操作符内存分配成功时，返回的是对象类型的指针，类型严格与对象匹配，无须进行类型转换，故new是符合类型安全性的操作符。而malloc内存分配成功则是返回void * ，需要通过强制类型转换将void*指针转换成我们需要的类型。
• 分配失败：new内存分配失败时，会抛出bac_alloc异常。malloc分配内存失败时返回NULL。
• 自定义类型： new会先调用operator new函数，申请足够的内存（通常底层使用malloc实现）。然后调用类型的构造函数，初始化成员变量，最后返回自定义类型指针。delete先调用析构函数，然后调用operator delete函数释放内存（通常底层使用free实现）。 malloc/free是库函数，只能动态的申请和释放内存，无法强制要求其做自定义类型对象构造和析构工作。
• 重载：C++允许重载new/delete操作符，特别的，布局new的就不需要为对象分配内存，而是指定了一个地址作为内存起始区域，new在这段内存上为对象调用构造函数完成初始化工作，并返回此地址。而malloc不允许重载。
• 内存区域：new操作符从自由存储区（free store）上为对象动态分配内存空间，而malloc函数从堆上动态分配内存（视情况而定！）。自由存储区是C++基于new操作符的一个抽象概念，凡是通过new操作符进行内存申请，该内存即为自由存储区。而堆是操作系统中的术语，是操作系统所维护的一块特殊内存，用于程序的内存动态分配，C语言使用malloc从堆上分配内存，使用free释放已分配的对应内存。自由存储区不等于堆，如上所述，布局new就可以不位于堆中。

2.4 Linux虚拟地址空间

为了防止不同进程同一时刻在物理内存中运行而对物理内存的争夺和践踏，采用了虚拟内存。

虚拟内存技术使得不同进程在运行过程中，它所看到的是自己独自占有了当前系统的4G内存。所有进程共享同一物理内存，每个进程只把自己目前需要的虚拟内存空间映射并存储到物理内存上。

事实上，在每个进程创建加载时，内核只是为进程“创建”了虚拟内存的布局，具体就是初始化进程控制表中内存相关的链表，实际上并不立即就把虚拟内存对应位置的程序数据和代码（比如.text .data段）拷贝到物理内存中，只是建立好虚拟内存和磁盘文件之间的映射就好（叫做存储器映射），等到运行到对应的程序时，才会通过缺页异常，来拷贝数据。还有进程运行过程中，要动态分配内存，比如malloc时，也只是分配了虚拟内存，即为这块虚拟内存对应的页表项做相应设置，当进程真正访问到此数据时，才引发缺页异常。

虚拟内存的好处：

1.扩大地址空间；

2.内存保护：每个进程运行在各自的虚拟内存地址空间，互相不能干扰对方。虚存还对特定的内存地址提供写保护，可以防止代码或数据被恶意篡改。

3.公平内存分配。采用了虚存之后，每个进程都相当于有同样大小的虚存空间。

4.当进程通信时，可采用虚存共享的方式实现。

5.当不同的进程使用同样的代码时，比如库文件中的代码，物理内存中可以只存储一份这样的代码，不同的进程只需要把自己的虚拟内存映射过去就可以了，节省内存

6.虚拟内存很适合在多道程序设计系统中使用，许多程序的片段同时保存在内存中。当一个程序等待它的一部分读入内存时，可以把CPU交给另一个进程使用。在内存中可以保留多个进程，系统并发度提高

7.在程序需要分配连续的内存空间的时候，只需要在虚拟内存空间分配连续空间，而不需要实际物理内存的连续空间，可以利用碎片

虚拟内存的代价：

1.虚存的管理需要建立很多数据结构，这些数据结构要占用额外的内存

2.虚拟地址到物理地址的转换，增加了指令的执行时间。

3.页面的换入换出需要磁盘I/O，这是很耗时的

4.如果一页中只有一部分数据，会浪费内存。

三、C++基础

3.1 类和结构体的区别

• 结构体（sturct）是一种值类型，而类（class）是引用类型。区别在于复制方式，值类型的数据是值赋值，引用类型的数据是引用复制。
• 结构体使用栈存储（Stack Allocation），而类使用堆存储（Heap Allocation)。
• 栈的空间相对较小.但是存储在栈中的数据访问效率相对较高。
• 堆的空间相对较大.但是存储在堆中的数据的访问效率相对较低
• 结构体使用完之后就自动解除内存分配，类实例有垃圾回收机制来保证内存的回收处理

如何选择结构体还是类

• 1． 堆栈的空间有限，对于大量的逻辑的对象，创建类要比创建结构好一些
• 2． 结构体表示如点、矩形和颜色这样的轻量对象，例如，如果声明一个含有 1000 个点对象的数组，则将为引用每个对象分配附加的内存。在此情况下，结构体的成本较低。
• 3． 在表现抽象和多级别的对象层次时，类是最好的选择，因为结构体不支持继承（C++11是支持继承的）
• 4． 大多数情况下该类型只是一些数据时，结构体时最佳的选择
• 5. C++类内的引用数据成员以及const常量都只能通过构造函数的初始化列表进行初始化，因为一旦进入构造函数函数体内部，就不再是初始化操作而是赋值操作，引用数据成员和const常量都是不能进行赋值操作的。

引用传递的作用

• 引用传递可减少类的构造和析构次数，减少程序开销。
• 引用传递可以避免类继承时的截断问题，确保多态性。

算法

1. 单调栈

#include <iostream>
#include <vector>
#include <stack>
using namespace std;
//n个整数的无序数组，找到每个元素后面比它大的第一个数，要求时间复杂度为O(N)
vector<int> find(vector<int> &num)
{
int len = num.size();
//空数组，返回空
if(len == 0)
return {};
stack<int> notFind;//栈：num中还未找到符合条件的元素索引
vector<int> res(len, -1);//返回结果：初始化-1，表示未找到
int i = 0;
while(i < len)//遍历数组
{
//如果栈空或者当前num元素不大于栈顶，将当前元素压栈，索引后移
if(notFind.empty() || num[notFind.top()] >= num[i])
notFind.push(i++);
else//有待处理元素，且num当前元素大于栈顶索引元素，符合条件，更新结果数组中该索引的值，栈顶出栈。
{
res[notFind.top()] = num[i];
notFind.pop();
}
}
return res;
}
int main()
{
vector<int> num = {1, 3, 2, 4, 99, 101, 5, 8};
// vector<int> num = {1, 1, 1, 1, 1, 1, 1};
// vector<int> num = {};
vector<int> res = find(num);
for(auto i : res)
cout << i << "
";
return 0;
}

2. LRU

#核心代码模式
#include<unodered_map>
class Solution{
public:
vector<int> LRU(vector<vector<int>>& operators,int k)
{
/**
* lru design
* @param operators int整型vector<vector<>> the ops
* @param k int整型 the k
* @return int整型vector
*/
vector<int> r;
vector<int> key;
vector<int> result;
for(int i = 0;i < operators.size();i ++)
{
if(operators[i][0] == 1)
{
set(operators[i][1],operators[i][2],r,key,k);
}
if(operators[i][0] == 2)
{
set(operators[i][1],r,key,result);
}
}
return rerult;
}
void set(int a,int b,vector<int>& r,vector<int>& key,int k)
{
/*使用vector当做一个队列或者一个链表，这里的存储的数据顺序是1,2,3,其中3元素是最新的，同时保证key和vakue同步*/
if(r.size()<k)
{
key.push_back(a);
r.push_back(b)
}else{//超出容量删除第一个元素，并将插入的元素放到第一个位置(这里的第一位置是vector的最后位置)
key.erase(key.begin());
r.erase(r.begin());
key.push_back(a);
r.push_back(b);
}
}
void get(int a, vector<int>& r,vector<int> &key,vector<int>& result)
{
int t = -1;
for(int i = 0;i < key.size();i ++)
{
if(a == key[i]){t = i;break;}//
}
if(t == -1){
result.push_back(-1);
}else{
int t1,t2;
t1 = key[t];
t2 = r[t];
//访问之后将访问之后的数据提前
key.erase(key.begin()+t);//删除之前的数据
r.erase(r.begin()+t);
key.push_back(t1);
r.push_back(t2);//保持key和value的值同步
result.push_back(t2);
}
}
};

#include<unordered_map>
#include<list>
class Solution{
public:
/**
* lru design
* @param operators int整型vector<vector<>> the ops
* @param k int整型 the k
* @return int整型vector
*/
vector<int> LRU(vector<vector<int>>& operators,int k)
{
vector<int> result;
cap = k;
result.reserve(operators.size());
if(k != 0)
{
for(const vector<int>& opt:operators){
if(opt[0] == 1) set(opt[1],opt[2]);
else if(opt[0] == 2) result.push_back(get(opt[1]));
}
}
return result;
}
int get(int key)
{
auto it = m.find(key);
if(it == m.end()) return -1;
dlist.splice(dlist.begin(),dlist,it->second);//拼接
return it->second->second;
}
void set(int key,int value)
{
auto it = m.find(key);
if(it!=m.end()) dlist.erase(it->second);
dlist.push_front(make_pair(key,value));
m[key] = dlist.begin();
if(m.size()>cap)
{
int k = dlist.rbegin()-first;
dlist.pop_back();
m.erase();
}
}
private:
int cap;
list<pair<int,int>> dlist;
unordered_map<int,list<pair<int,int>>::iterator> m;
/*负载因子 = 容器存储的总键值对 / 桶数
默认情况下，无序容器的最大负载因子为 1.0。如果操作无序容器过程中，使得最大复杂因子超过了
默认值，则容器会自动增加桶数，并重新进行哈希，以此来减小负载因子的值。需要注意的是，此过
程会导致容器迭代器失效，但指向单个键值对的引用或者指针仍然有效。*/
};

3. 排序的稳定性和复杂度

      不稳定：

      选择排序（selection sort）— O(n2)

      快速排序（quicksort）— O(nlogn) 平均时间, O(n2) 最坏情况; 对于大的、乱序串列一般认为是最快的已知排序

      堆排序 （heapsort）— O(nlogn)

      希尔排序 （shell sort）— O(nlogn)

      基数排序（radix sort）— O(n·k); 需要 O(n) 额外存储空间 （K为特征个数）

      稳定：

      插入排序（insertion sort）— O(n2)

      冒泡排序（bubble sort） — O(n2)

      归并排序 （merge sort）— O(n log n); 需要 O(n) 额外存储空间

      二叉树排序（Binary tree sort） — O(nlogn); 需要 O(n) 额外存储空间

      计数排序  (counting sort) — O(n+k); 需要 O(n+k) 额外存储空间，k为序列中Max-Min+1

      桶排序 （bucket sort）— O(n); 需要 O(k) 额外存储空间

最后

以上就是紧张身影为你收集整理的杂项总结一、C++的STL二、关于内存泄露三、C++基础算法的全部内容，希望文章能够帮你解决杂项总结一、C++的STL二、关于内存泄露三、C++基础算法所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。