404-C++之STL模板库（1-8）

1、什么是STL？

C++ STL从广义来讲包括了三类：算法，容器和迭代器。

• 算法包括排序，复制等常用算法，以及不同容器特定的算法。
• 容器就是数据的存放形式，包括序列式容器和关联式容器，序列式容器就是list，vector等，关联式容器就是set，map等。
• 迭代器就是在不暴露容器内部结构的情况下对容器的遍历。

2、使用智能指针管理内存资源，RAII是怎么回事？

• RAII全称是“Resource Acquisition is Initialization”，直译过来是“资源获取即初始化”，也就是说在构造函数中申请分配资源，在析构函数中释放资源。
• 因为C++的语言机制保证了，当一个对象创建的时候，自动调用构造函数，当对象超出作用域的时候会自动调用析构函数。所以，在RAII的指导下，我们应该使用类来管理资源，将资源和对象的生命周期绑定。

智能指针（std::shared_ptr和std::unique_ptr）即RAII最具代表的实现，使用智能指针，可以实现自动的内存管理，再也不需要担心忘记delete造成的内存泄漏。

毫不夸张的来讲，有了智能指针，代码中几乎不需要再出现delete了。

3、迭代器：++it、it++哪个好，为什么

++it好！

1、前置返回一个引用，后置返回一个对象；

// ++i实现代码为：
int& operator++()
{

  *this += 1;
  return *this;

} 

2、前置不会产生临时对象，后置必须产生临时对象，临时对象会导致效率降低。

//i++实现代码为：                 
int operator++(int)                 
{
int temp = *this;                   

   ++*this;                       

   return temp;                  
} 

4、STL中hashtable的实现？

STL中的hashtable使用的是开链法解决hash冲突问题；

如下图所示：

• hashtable中的每一个bucket所维护的list既不是list也不是slist，而是其自己定义的由hashtable_node数据结构组成的linked-list；
• bucket聚合体本身使用vector进行存储。
• hashtable的迭代器只提供前进操作，不提供后退操作；
• 在hashtable设计bucket的数量上，其内置了28个质数[53, 97, 193,…,429496729]，在创建hashtable时，会根据存入的元素个数选择大于等于元素个数的质数作为hashtable的容量（vector的长度），其中每个bucket所维护的linked-list长度也等于hashtable的容量。
• 如果插入hashtable的元素个数超过了bucket的容量，就要进行重建table操作，即找出下一个质数，创建新的buckets vector，重新计算元素在新hashtable的位置。

5、STL中vector的实现

vector是一种序列式容器，其数据安排以及操作方式与array非常类似，两者的唯一差别就是对于空间运用的灵活性。

array占用的是静态空间，一旦配置了就不可以改变大小，如果遇到空间不足的情况还要自行创建更大的空间，并手动将数据拷贝到新的空间中，再把原来的空间释放。

vector则使用灵活的动态空间配置，维护一块连续的线性空间，在空间不足时，可以自动扩展空间容纳新元素，做到按需供给。其在扩充空间的过程中仍然需要经历：重新配置空间，移动数据，释放原空间等操作。

源码：

const size_type len  = old_size + max(old_size, n);

Vector扩容倍数与平台有关，在Win + VS 下是 1.5倍，在 Linux + GCC 下是 2 倍

---

vector提供的是三个指针：（大小就是三根指针）

• start：元素起始处；
• finish：元素终止处；
• end of storage：表示整个空间的终点；

默认的分配器： alloc

[]作用符：所有容器有连续空间这种特性(链表的节点是分离的)，就必须提供[]；

vector扩容机制：

1、先判断有没有足够的空间；

 finish != end_of_storage

2、没有备用空间

• 分配时，进行两倍增长；前半段用来放置原数据，后半段用来放置新数据；
• 释放原来的vector；调整迭代器，指向新的vector；

---

6、array深度探索

array占用的是静态空间，一旦配置了就不可以改变大小，如果遇到空间不足的情况还要自行创建更大的空间，并手动将数据拷贝到新的空间中，再把原来的空间释放。

array：数组，包装成容器（可以遵循容器的规则），提供迭代器，以便于算法操作；

• array需要指定大小 ，没有构造函数和析构函数；
• 只要是连续空间，迭代器就可以单纯的指针来表现，不需要用其他的 ，在萃取机种，会跑到指针那一部分；
• 这里array直接将指针（non-class iterator）拿来当迭代器；

array实现：

---

7、slist和forward_list

使用slist时需要计入头文件： #include

list是双向链表，而slist（single linked list）是单向链表；

区别：

• list的迭代器是双向的Bidirectional iterator，slist的迭代器属于单向的Forward iterator。
• 虽然slist的很多功能不如list灵活，但是其所耗用的空间更小，操作更快。

根据STL的习惯，插入操作会将新元素插入到指定位置之前；

slist是不能回头的，只能往后走，因此在slist的其他位置插入或者移除元素是十分不明智的，但是在slist开头却是可取的，slist特别提供了insert_after()和erase_after()供灵活应用。

insert_after(): 在指定位置后面插入;
erase_after(): 删除指定位置后面的元素;

考虑到效率问题，slist只提供push_front()操作，元素插入到slist后，存储的次序和输入的次序是相反的。

push_front()：在链表左边插入；

slist的单向迭代器如下图所示：

slist默认采用alloc空间配置器配置节点的空间，其数据结构主要代码如下：

template 
class slist
{
	...
private:
    ...
    static list_node* create_node(const value_type& x){}//配置空间、构造元素
    static void destroy_node(list_node* node){}//析构函数、释放空间
private:
    list_node_base head; //头部
public:
    iterator begin(){}
    iterator end(){}
    size_type size(){}
    bool empty(){}
    void swap(slist& L){}//交换两个slist，只需要换head即可
    reference front(){} //取头部元素
    void push_front(const value& x){}//头部插入元素
    void pop_front(){}//从头部取走元素
    ...
}

测试案例：

#include 
#include 
#include 
using namespace std;

int main()
{
	forward_list fl;
	fl.push_front(1);
	fl.push_front(3);
	fl.push_front(2);
	fl.push_front(6);
	fl.push_front(5);

	forward_list::iterator ite1 = fl.begin();
	forward_list::iterator ite2 = fl.end();
	for(;ite1 != ite2; ++ite1)
	{
		cout << *ite1 <<" "; // 5 6 2 3 1
	}
	cout << endl;

	ite1 = find(fl.begin(), fl.end(), 2); //寻找2的位置

	if (ite1 != ite2)
		fl.insert_after(ite1, 99);
	for (auto it : fl)
	{
		cout << it << " ";  //5 6 2 99 3 1
	}
	cout << endl;

	ite1 = find(fl.begin(), fl.end(), 6); //寻找6的位置
	if (ite1 != ite2)
		fl.erase_after(ite1);
	for (auto it : fl)
	{
		cout << it << " ";  //5 6 99 3 1
	}
	cout << endl;	
	return 0;
}

需要注意的是C++标准委员会没有采用slist的名称，forward_list在C++ 11中出现，它与slist的区别是没有size()方法。

forward_list： 单向链表。

和之前双向链表list相比，只有一个指针了；

---

8、list

• 对任何位置元素的插入和删除都是常数时间；
• list不能保证节点在存储空间中连续存储；
• 拥有迭代器，迭代器的“++”、“–”操作对于的是指针的操作，list提供的迭代器类型是双向迭代器：Bidirectional iterators。

list节点的结构见如下源码：

template 
struct __list_node{
    typedef void* void_pointer;
    void_pointer prev;
    void_pointer next;
    T data;
}

从源码可看出list显然是一个双向链表。

list与vector的另一个区别是，在插入和接合操作之后，都不会造成原迭代器失效，而vector可能因为空间重新配置导致迭代器失效。

list也是一个环形链表，因此只要一个指针便能完整表现整个链表。list中node节点指针始终指向尾端的一个空白节点，因此是一种“前闭后开”的区间结构。

list的空间管理默认采用alloc作为空间配置器，为了方便的以节点大小为配置单位，还定义一个list_node_allocator函数可一次性配置多个节点空间。

由于list的双向特性，其支持在头部（front)和尾部（back)两个方向进行push和pop操作，当然还支持erase，splice，sort，merge，reverse，sort等操作。