[后台开发工程师总结系列] 8.STL概论

STL概论

长久以来软件届一直希望建立一种可复用的东西，以及一种得以造出“可重复运用东西”的方法。

子程序、程序、函数、类别、函数库、类别库、组件、结构模块化设计、模式、面向对象 …

都是为了 复用性的提升

复用性必须建立在某种标准之上，但是在许多环境下开发最基本的算法和数据结构还迟迟不能有标准。大量程序员从事重复劳动，完成前人完成而自己不拥有的代码。

例子

现在需要编写一个排序函数，这涉及到一个问题，从流中读入数据事先并不知道数据的长度 ，然而C/C++ 数组只能申请定长数组，超过数组上限就会出现越界。为了弥补该缺陷，就必须采用下列方案的一种：

1. 采用大容量的静态数据分配
2. 限定输入的数据个数
3. 采用动态的内存分配

显然，前两种方法都有缺陷。只能使用指针及动态内存来妥善解决上述问题，使程序具有较好的灵活性。这需要New()、delete() 或者 malloc() realloc() free() 等函数，这样程序就会相当的不简洁。

为了建立数据结构算法的标准，降低耦关系，提升独立性、弹性，交互操作性，诞生了STL

六大组件简单介绍

1. 空间配置器：内存池实现小块内存分配,对应到设计模式–单例模式（工具类，提供服务，一个程序只需要一个空间配置器即可），享元模式（小块内存统一由内存池进行管理）
2. 迭代器：迭代器模式，模板方法
3. 容器：STL的核心之一，其他组件围绕容器进行工作：迭代器提供访问方式，空间配置器提供容器内存分配，算法对容器中数据进行处理，仿函数伪算法提供具体的策略，类型萃取　　实现对自定义类型内部类型提取。保证算法覆盖性。其中涉及到的设计模式：组合模式（树形结构），门面模式（外部接口提供），适配器模式（stack，queue通过deque适配得到），建造者模式（不同类型树的建立过程）。
4. 类型萃取：基于范型编程的内部类型解析，通过typename获取。可以获取迭代器内部类型value_type,Poter,Reference等。(算法)
5. 仿函数：一种类似于函数指针的可回调机制，用于算法中的决策处理。涉及：策略模式，模板方法。
6. 适配器：STL中的stack，queue通过双端队列deque适配实现，map，set通过RB-Tree适配实现。涉及适配器模式。

空间配置器 allocator

软件开发中，不免于程序需求可能使用很多小块内存，在程序中动态的申请和释放。这个过程不一定能控制好，所以可能出现以下问题：

1. 内存碎片问题
2. 因为一直申请小块内存，malloc系统产生调用性能问题

内部碎片：因为内存对齐、访问效率（CPU取址次数）而产生，比如申请3字节而得到4字节或8字节

外部碎片：系统中该内存中总量足够，但是不连续而造成的浪费。

下面是STL空间配置器的细节

if(n > (size_t)_MAX_BYTES){
    return malloc_alloc::allocate(n); // 一级空间配置器
}else{
    // 二级空间配置器
}

大致实现：

一级空间配置器直接封装malloc，free 进行处理，增加了C++中的set_handler机制，增加内存分配时客户端可选处理机制。

一级空间配置器

static void *Allocate(size_t n)
{
    ___TRACE("__MallocAllocTemplate to get  n = %u\n",n);
    void *result = malloc(n);
    if (0 == result)
    {
        result = OomMalloc(n);
    }
    return result;
}
void *__MallocAllocTemplate::OomMalloc(size_t n)
{
    ___TRACE("一级空间配置器,不足进入Oo中n = %u\n",n);
    void(*my_malloc_handler)();
    void* result;
    for (;;) // 不断尝试释放、配置、再释放、再配置
    {
        my_malloc_handler = __malloc_alloc_oom_handler;
        if (0 == my_malloc_handler)
        {
            __THROW_BAD_ALLOC;
        }
        (*__malloc_alloc_oom_handler)(); //调用处理历程，企图释放内存
        result = malloc(n);
        if (result)
            return result;
    }
}

第一级配置器以malloc()、free()、realloc() 等C函数执行实际的内存配置和释放，类似于C++ 的new-handler机制，但是他不能直接使用（未使用::operator new来配置内存）。

所谓new-handler 机制是，要求系统在内存配置无法满足时，调用你指定的函数，一旦new无法完成任务，在丢出异常之前，调用客户端的历程，这就被称为new-handler。

请注意，第一级配置器都是在malloc和realloc调用不成功后，改为调用oom_malloc，后两者内有循环，不断调用 “内存不足例程”，但是如果这个例程未被设定，便老实的 __THROW_BAD_ALLOC;

二级空间配置器

二级空间配置器避免了太多额外的小区造成的内存碎片。二级配置器的做法是，如果区块足够大（超过128字节）则以内存池管理，此法又被称为层次管理：每次配置一块大内存，并且维护自由链表。下次如果还有相同的内存需求，就从free-list中拨出，如果客户端释放，就回收到free-list中，配置器配置也回收，为了方便起见，二级配置器主动把内存的需求量上调至8的倍数。

 static  size_t _FreeListIndex(size_t __bytes) 
    {
        return (((__bytes) + (size_t)_ALIGN-1)/(size_t)_ALIGN - 1);
    }

static void* Allocate(size_t n)
    {
        void * ret = 0;
        ___TRACE("二级空间配置器申请n = %u\n",n);
        if(n>_MAX_BYTES)
            ret = MallocAlloc::Allocate(n);

        _Obj* volatile * __my_free_list = _freeList + _FreeListIndex(n);

        _Obj* __result = *__my_free_list;
        if (__result == 0)
            ret = _Refill(RoundUp(n));
        else
        {
            *__my_free_list = __result -> _freeListLink;
            ret = __result;
        }
        return ret;
    }

chunk_alloc() 函数以 end_free - start_free 来判断内存池。 如果容量充足，就一次性调20个区块给free-list, 但是如果剩余区块不够20 但是大于1， 就拨出剩余能拨出的区块。最后如果剩余不到1个区块了 ，那就重新从堆中配置内存。新的配置量是一个两倍的需求加一个逐渐增大的附加量。

迭代器

迭代器是一种抽象的设计概念，现实程序语言中并没有直接对应这个概念的实物。

《设计模式》中对于迭代器的定义如下：提供一种方法，使之能够依次巡防某个聚合物容器所含的各个元素，而又无需包括该聚合物内部的表述方式。

不论是泛型思维或STL的实际应用，迭代器都扮演着重要角色。STL的中心思想在于，将数据容器和算法分开，彼此独立设计，最后再将他们撮合在一起，而迭代器就扮演了这个黏胶角色。

迭代器是一种行为类似指针的对象，而指针行为中最常见的内容是提领（dereference）和成员访问（member access）因此迭代器最重要的工作就是对opreator* 和 opreator-> 进行重载工作。关于这一点C++有智能指针。

STL 容器

容器	底层数据结构	时间复杂度	有无序	可不可重复	其他
array	数组	随机读改 O(1)	无序	可重复	支持快速随机访问
vector	数组	随机读改、尾部插入、尾部删除 O(1) 头部插入、头部删除 O(n)	无序	可重复	支持快速随机访问
list	双向链表	插入、删除 O(1) 随机读改 O(n)	无序	可重复	支持快速增删
deque	双端队列	头尾插入、头尾删除 O(1)	无序	可重复	一个中央控制器 + 多个缓冲区，支持首尾快速增删，支持随机访问
stack	deque / list	顶部插入、顶部删除 O(1)	无序	可重复	deque 或 list 封闭头端开口，不用 vector 的原因应该是容量大小有限制，扩容耗时
queue	deque / list	尾部插入、头部删除 O(1)	无序	可重复	deque 或 list 封闭头端开口，不用 vector 的原因应该是容量大小有限制，扩容耗时
priority_queue	vector + max-heap	插入、删除 O(log2n)	有序	可重复	vector容器+heap处理规则
set	红黑树	插入、删除、查找 O(log2n)	有序	不可重复
multiset	红黑树	插入、删除、查找 O(log2n)	有序	可重复
map	红黑树	插入、删除、查找 O(log2n)	有序	不可重复
multimap	红黑树	插入、删除、查找 O(log2n)	有序	可重复
hash_set	哈希表	插入、删除、查找 O(1) 最差 O(n)	无序	不可重复
hash_multiset	哈希表	插入、删除、查找 O(1) 最差 O(n)	无序	可重复
hash_map	哈希表	插入、删除、查找 O(1) 最差 O(n)	无序	不可重复
hash_multimap	哈希表	插入、删除、查找 O(1) 最差 O(n)	无序	可重复

vector

vector 是线性容器，它的元素按照线性排列，和动态数组类似。和数组类似的是，它的元素存在一块连续的内存空间中，这意味着不仅可以通过迭代器访问，还可以使用指针偏移访问元素。和数组不一样的是，vector能够自动增长或缩短储存空间。

vector的优点如下所示：

1. 可以使用下标访问个别元素
2. 迭代器可以按照不同的顺序遍历容器
3. 可以在容器的默认增加、删除元素

关于STl容器，只要不超过最大值，其可以自动增长到足以容纳用户放进去的数据大小。（这个容量值，可以同过调用maxsize()来获得）

对于vector和string，如果需要更多的空间，类似realloc思想增长，vector支持随机访问，因此提高了效率，内部通过动态数组实现。

//vector 查找
vector<int>::iterator iter;
iter = find(vec.begin(),vec.end(),3);

//vector 删除
iterator erase(iterator position) // 删除后指向删除元素的下一个位置
iterator erase(iterator frist, iterator last)

vector<int>::iterator iter = vec.begin();
while(iter!=vec.end()){
    if(*iter==target){
        iter = erase(iter);
    }else{
        iter++;
    }
}

//vector 增加
iterator insert(iterator loc, const TYPE &val); // 指定位置loc 插入值为val的元素，返回指向这个元素的迭代器
void insert(itrator loc, size_type num, const TYPE &val); // 同上，插入num 个元素 
void insert(itrator loc, itrator start, itrator end); // 插入迭代器区间的元素

vector内存管理

1. 使用reverse() 提前设定容量大小

STL最令人称赞的特性之一就是只要不超过最大值，其可以自动增长。如果需要更多空间就会类似realloc的思想来增长大小。vector容器支持随机访问，因此效率较高。 如果有大量的元素需要push_back，应提前使用reverse函数提前设定，避免多次的扩容操作，介绍一下只有vector与string提供的几个函数

函数名	介绍
size()	获得容器中的元素个数，但不能获得容器为他分配的容器大小
capacity()	获得容器已经分配的内存容纳多少元素。
resize()	用来强制把容器改为容纳n个元素。如果n小于当前大小，尾部元素会被销毁；如果n大于当前大小，默认构造元素添加到元素尾；如果大于当前容量，触发重新分配
reverse()	强制把容量改为不小于n，n不小于当前大小

1. 交换技巧来修整内存

有一种方法将它的最大容量修正到其当前容量，这种方法被称为“收缩到合适”，只需要一条语句

vector<int>(ivec).swap(ivec);

1. swap强行释放内存

template<class T> void VlearVector(vector<T>& v)
{
    vector<T> vTemp;
    vTemp.swap(v);
}

vector类简单实现

第二版参考《stl源码》

template<class T, class Alloc=alloc>
class vector{
public:
	typedef T value_type;
	typedef value_type* pointer;
	typedef value_type* iterator;
	typedef value_type& reference;
	typedef size_t size_type;
	typedef ptrdiff_t difference_type;
protected:
	typedef simple_alloc<value_type, Alloc> data_allocator;
	iterator start;
	iterator finish;
	iterator end_of_storage;
	void insert_aux(iterator posotion, const T& x);
    void deallocate(){
    	if(start)
    		data_allocator::deallocate(start,end_of_storage-start);
    }
    void fill_initialize(size_type n, const T& vlaue){
    	start = allocate_and_fill(n, value);
    	finish = start + n;
    	end_of_storage = finish;
    }
public:
	iterator begin(){return start;}
	iterator end(){return finish;}
	size_type size() const {return size_type(end()-begin());}
	size_type capacity() const{return size_type(end_of_storage-begin());}
	bool empty() const {return engin()==end()}
	reference operator[](size_type n){return *(begin()+n);}
	vector():start(0),finish(0),end_of_storage(0){}
	vector(size_type n,const T& value){fill_initialize(n,value);}
	vector(int n,const T& value){fill_initialize(n,value);}
	vector(long n,const T& value){fill_initialize(n,value);}
	explicit vector(size_type n) {fill_initlialize(n,T());}
    ~vector(){
    	destroy(start,finish);
    	deallocate();
    }
    reference front(){ return *begin();}
    reference back() { return *(end()-1);}
    void push_back(const T& x){
    	if(finish!=end_of_storage){
    		construct(finish, x);
    		++finish;
    	}else
    		insert_aux(end(),x);
    }
    void pop_back(){
    	--finish;
    	destory(finish);
    }
    iterator erase(iterator position){
    	if(position+1 != end())
    		copy(position+1,finish,position);
    	--finish;
    	destory(finish);
    	return position;
    }
    void resize(size_type new_size, const T& x){
    	if(new_size<size())
    		erase(begin()+new_size(),end());
    	else
    		insert(end(),newsize()-size(),x);
    }
    void resize(size_type new_size){resize(new_size,T());}
    void clear(){erase(begin(),end());}
protected:
iterator allocate_and_fill(size_type n, const T& x){
		iterator result = data_allocatpr::
	}
}
template<class T, class Alloc>
void vector<T, Alloc>::insert_aux(iterator position, const T& x){
	if(finish != end_of_storage){
		construct(finish,*（finish-1));
		++finish;
		T x_copy = x;
		copy_backword(position, finish-2,finish-1);
		*position = x_copy;
    }else{
    	const size_type old_size = size();
    	const size_type len = old_size != 0?2*oldsize:1;
    	iterator new_start = data_allocator::allocate(len);
    	iterator new_finish = new_start;
        try {
        	new_finish = uninitialized_copy(start,posotion,new_start);
        	construct(new_finish, x);
        	++new_finish;
        	new_finish = uninitialized_copy(positon,finish,new_finish);
            } catch(...){
        	destroy(new_start,new_finish);
            data_allocator::deallocate(new_start,len);
            thow;
        }
        destroy(begin(),end());
        deallocate();
        start = new_start;
        finish = new_finish;
        end_of_storage = new_start+len;
    }
}

map、set

1. map的本质

map本质是一类关联式容器，属于模板类关联的本质在于元素的值与某个特点的键相关联，而并非通过元素在数组的位置获取。它的特点是增加和删除节点对迭代器的影响很小，除了要操作的节点，对其他节点都没什么影响。对迭代器来数不能修改键值，只能修改实值。map内部自建一颗红黑树（非严格意义的平衡二叉树），该树内部数据有序

定义：
    map<T_key, T_value> mymap;

插入元素：
    mymap.insert(pair<T_key, T_value>(key, value));  //同key不插入
    mymap.insert(map<T_key, T_value>::value_type(key, value)); //同key不插入
    mymap[key] = value; //同key覆盖

删除元素：
    mymap.erase(key); //按值删
    mymap.erase(iterator); //按迭代器删

修改元素：
    mymap[key] = new_value;

遍历容器：
    for(auto it = mymap.begin(); it != mymap.end(); ++it){
        cout<< it->first << " => " << it->second << '\n';
    }

基于红黑树实现的map结构（实际上是map, set, multimap，multiset底层均是红黑树），不仅增删数据时不需要移动数据，其所有操作都可以在O(logn)时间范围内完成。另外，基于红黑树的map在通过迭代器遍历时，得到的是key按序排列后的结果，这点特性在很多操作中非常方便。

红黑树的特性

1. 它是一颗二叉排序树（继承二叉排序树的特点）：
   • 若左子树不空，则左子树的上所有节点的值均小于等于它根节点的值
   • 若右子树不空， 则右子树上所有节点的值均大于等于它根节点的值
   • 左右子树分别也是二叉排序树。
2. 红黑树的要求
   • 树中所有节点非红即黑
   • 根节点必为黑节点
   • 红节点的子节点必须为黑
   • 从根到任何发路径上的的黑节点数相同
3. 查找时间一定可以控制在O(log N)之内
4. 红黑树定义如下

enum Color {
    RED = 0,
    BLACK = 1
};
struct RBTreeNode {
    struct RBTreeNode*left, *right, *parent;
    int key;
    int data;
    Color color;
};

所以对红黑树的操作需要满足两点：1.满足二叉排序树的要求；2.满足红黑树自身要求。通常在找到节点通过和根节点比较找到插入位置之后，还需要结合红黑树自身限制条件对子树进行左旋和右旋。

相比于AVL树，红黑树平衡性要稍微差一些，不过创建红黑树时所需的旋转操作也会少很多。相比于最简单的BST，BST最差情况下查找的时间复杂度会上升至O(n)，而红黑树最坏情况下查找效率依旧是O(logn)。所以说红黑树之所以能够在STL及Linux内核中被广泛应用就是因为其折中了两种方案，既减少了树高，又减少了建树时旋转的次数。

从红黑树的定义来看，红黑树从根到NULL的每条路径拥有相同的黑节点数（假设为n），所以最短的路径长度为n（全为黑节点情况）。因为红节点不能连续出现，所以路径最长的情况就是插入最多的红色节点，在黑节点数一致的情况下，最可观的情况就是黑红黑红排列……最长路径不会大于2n，这里路径长就是树高。

hashtable

hashtable被视为一种字典结构，提供对于任何有名项的存取操作和删除操作。

如何避免array过大？是用某种映射函数，使得元素映射至“大小可以接受的索引”，这个函数被称为散列函数。使用散列函数必然会带来一个问题：可能有不同的元素被映射到相同的位置，这便是所谓的碰撞问题。

碰撞问题一般有两种方案：拉链法、线性探测法

线性探测

提出一个名词：负载系数，元素个数除以表格大小。负载系数永远在0~1之间，

当 散列函数 计算某个位置，而该位置不可用该怎么办？ 最简单的方法就是循序接着往下找，只要表格足够大总会找到一个空间。而删除必须采取惰性删除（标记删除序号，实际删除待表格整理时再进行）

两个假设 1.表格足够大，2 每个元素独立 但实际情况往往不乐观，往往需要不断解决碰撞问题

二次探测

static int prime[28] =
{
    57,        97,         193,        389,        769,
    1543,      3079,       6151,       12289,      24593,
    49157,     98317,      196613,     393241,     786433,
    1572869,   3145739,    6291469,    12582917,   25165843,
    50331653,  100663319,  201326611,  402653189,  805306457,
    1610612741
};

class HashMapUtil
{
public:
    static int find_NextPrimeNumber(int current)
    {
        //Find the next prime number by searching in the prime number list
        int i = 0;
        for( ; i < 28 ; i++ )
            if(current < prime[i])
                break;
        return prime[i];     //return the next larger prime.
    }
};

二次探测主要用来解决 主集团问题， 该方法描述很简单，碰撞时尝试 H+1*1，H+2*2, H+ 3*3来代替H+1, H+2,H+3 等。幸运的是，假设表格大小为质数，永远保持0.5以下的负载系数，每个新元素的插入查找不大于2

另外，二次探测有个简便的计算技巧

hi = h0 +  i\*i (MOD M)

hi-1 = h0 + (i-1) *(i-1) (MOD M)

整理得，hi = hi-1 + 2*i-1 (MOD M)

这样每一次迭代并不需要太大的计算资源。

开链

拉链法，在《STL源码》中被称为开链，及对于冲突的元素维护一个链表

从上图我们可以发现哈希表是由数组+链表组成的，一个长度为16的数组中，每个元素存储的是一个链表的头结点。那么这些元素是按照什么样的规则存储到数组中呢。一般情况是通过hash(key)%len获得，也就是元素的key的哈希值对数组长度取模得到。比如上述哈希表中，12%16=12,28%16=12,108%16=12,140%16=12。所以12、28、108以及140都存储在数组下标为12的位置。

HashMap其实也是一个线性的数组实现的,所以可以理解为其存储数据的容器就是一个线性数组。这可能让我们很不解，一个线性的数组怎么实现按键值对来存取数据呢？这里HashMap有做一些处理。

首先HashMap里面实现一个静态内部类Entry，其重要的属性有 key , value, next，从属性key,value我们就能很明显的看出来Entry就是HashMap键值对实现的一个基础bean，我们上面说到HashMap的基础就是一个线性数组，这个数组就是Entry[]，Map里面的内容都保存在Entry[]里面。

hash算法的存取

// 存储时:
int hash = key.hashCode(); 
int index = hash % Entry[].length;
Entry[index] = value;

// 取值时:
int hash = key.hashCode();
int index = hash % Entry[].length;
return Entry[index];

面试常考题

1. vector 的结构

public:
	typedef T value_type;
	typedef value_type* pointer;
	typedef value_type* iterator;
	typedef value_type& reference;
	typedef size_t size_type;
	typedef ptrdiff_t difference_type;
protected:
	typedef simple_alloc<value_type, Alloc> data_allocator;
	iterator start;
	iterator finish;
	iterator end_of_storage;
	void insert_aux(iterator posotion, const T& x);
    void deallocate(){}
    void fill_initialize(size_type n, const T& vlaue){}
public:
	iterator begin(){return start;}
	iterator end(){return finish;}
	size_type size() const {return size_type(end()-begin());}
	size_type capacity() const{return size_type(end_of_storage-begin());}
	bool empty() const {return engin()==end()}
	reference operator[](size_type n){return *(begin()+n);}
	vector():start(0),finish(0),end_of_storage(0){}
	vector(size_type n,const T& value){fill_initialize(n,value);}
	vector(int n,const T& value){fill_initialize(n,value);}
	vector(long n,const T& value){fill_initialize(n,value);}
	explicit vector(size_type n) {fill_initlialize(n,T());}
    ~vector()
    reference front(){ return *begin();}
    reference back() { return *(end()-1);}

2. vector 和 list 的区别和应用场景

vector 是地址空间连续，支持随机存取的数组。优点是存取方便，缺点是非末尾的增、删复杂度较高。

list 是不支持随机的存取的链表，优点是增、删复杂度O(1)，缺点是查找复杂度O（n）

vector拥有一段连续的内存空间，因此支持随机访问，如果需要高效的随即访问，而不在乎插入和删除的效率，使用vector。list拥有一段不连续的内存空间，如果需要高效的插入和删除，而不关心随机访问，则应使用list。

3. vector怎么增加内存

通过源码对比回答， 当vector因为增加元素而超出容量，即（finish==capacity时）,进行以下操作

1. 保存原指针（start, finish, capacity）
2. 计算新数组的容量大小（为原大小的两倍），并申请这样大小的空间，记录新的数组指针（new_start, new finish , new_capacity）
3. 在新的数组中复制原数组, 然后完成当下的增加元素操作。
4. 释放原数组空间
5. 用新数组指针替换原指针。

4. 遍历vector的几种写法

// 1. [] 数组遍历
for(int i=0; i<vec.size(); i++){
    cout<<vec[i]<<endl;
}
// 2. 迭代器遍历
for(vector<int>::iterator it = vec.begin(); it!=vec.end(); it++){
    cout<<*it<<endl;
}
// 3. C++11 的新特性冒号遍历（不支持修改）
for(int num:vec){
    cout<<num<<endl;
}

5. 对STL内存分配的理解，为什要有空间配置器

软件开发中，不免于程序需求可能使用很多小块内存，在程序中动态的申请和释放。这个过程不一定能控制好，所以可能出现以下问题：内存碎片问题、因为一直申请小块内存，malloc系统产生调用性能问题。 为了解决以上问题，而且为了方便管理malloc申请空间不足的情况，STL模拟了new_handler 提供用户错误处理接口。

6. hashtable java实现

package prepare;
/** 
* @author : Menghui Chen 
* @version ：2018年3月20日 下午7:14:04 
* @Description:
*/
public class HashMap<T, V> {
    static class Node<T, V> {
        Node<T, V> next;
        private T key;
        private V value;
        public void setKey(T k) {
            this.key = k;
        }
        public T getKey() {
            return key;
        }
        public void setValue(V value) {
            this.value = value;
        }
        public V getValue() {
            return value;
        }
        public Node(T k, V v) {
            this.key = k;
            this.value = v;
        }
    }
    Node[] tab;
    public HashMap(int capacity) {
        tab = new Node[capacity];
    }
    public V put(T key, V value) {
        int index = getIndex(key);
        Node node = new Node(key, value);
        if (tab[index] == null) {
            tab[index] = node;
            return null;
        } else {
            Node head = tab[index];
            Node pre = searchList(head, key);
            if (pre.next == null) {
                pre.next = node;
                return null;
            } else {
                V old =  (V) pre.next.value;//here
                pre.next.value = value;
                return old;
            }
        }
    }
    public Node searchList(Node node, T k) {
        Node pre = null;
        while (node != null) {
            if (hash((T)node.key) == hash(k) && (node.key == k || node.key.equals(k))) {
                break;
            }
            pre = node;
            node = node.next;
        }
        return pre;
    }
    public V get(T key) {
        int index = getIndex(key);
        if (tab[index] == null) {
            return null;
        } else {
            Node head = tab[index];
            head = searchList(head, key);
            if (head == null && head.next == null) {
                return null;
            } else {
                return (V)head.next.value;
            }
        }
    }
    public int hash(T key) {
        return (key.hashCode() >> 16) ^ key.hashCode();
    }
    public int getIndex(T key) {
        return hash(key) % tab.length; 
    }
}

7. map 与 unordered_map 的区别和应用场景

map本质是一类关联式容器，属于模板类关联的本质在于元素的值与某个特点的键相关联，而并非通过元素在数组的位置获取。它是一种通过内建红黑树实现了O(logN) 时间复杂度内实现 增删改查的数据结构，且其内部元素有序。

unordered_map被视为一种字典结构，提供对于任何有名项的存取操作和删除操作。利用哈希映射表实现了元素的增、删、查、改操作

二者的主要区别在于map有序, 而unordered_map无序， 他们的应用场景也主要取决于是否要求元素有序。

1. STL中有几种map

unordered_map 哈希表 不可重复 无序

map 红黑树 不可重复 有序

multi-map 红黑树 有序