C++ 容器详解

C++ 容器详解

首先说一下六大组件：

算法,容器,迭代器,仿函数(函数对象),分配器,适配器

简述： 线性容器:

vector(向量): 好比C语言中数组   顺序表  seqtable
(a)内存连续     支持[]运算符   下标访问
(b)动态内存管理    自动扩容
(c)通过分配器来管理动态内存 预分配内存空间 减少动态内存管理的额外开销
(d)可以随机位置做插入和删除，但只有在接近末尾进行插入和删除时才是高效的

预分配内存和初始化
vector v3(10); //10个int元素，初始值为0
vector v4(10,1024); //10个int元素，初始值全为1024
vector v5(10); //10个Stu对象，通过无参构造函数初始化一个对象 ，然后通过拷贝构造函数
//有的编译器 直接全部调用无参构造
vector v6(10,s); //10个Stu对象，通过拷贝构造初始化
对象如果放入到容器中，一般需要无参构造
vector v7(beg,end); //[beg,end)区间的元素来构造vector

list(列表)：  
	底层实现双向链表
(a)内存可以不连续  离散的结点    指针   不支持随机访问
(b)在任何位置插入和删除拥有O(1)的时间复杂度
(c)不能用全局的sort进行排序  全局的sort函数只支持连续内存的容器
    有成员sort 
(d)list删除之后，迭代器会失效   必须接收返回值

deque(双端队列)：
(a)内存连续，支持下标访问和随机迭代
(b)相对vector而言，在首尾两端都能进行高效地插入和删除
(c)因此需要在首尾两端都维护内存的开放性，其分配器的实现略加复杂
	空间利用率会比vector低
	时间复杂度会比vector要高一些
(d)对比vector多了push_front()/pop_front(),少了reserve
(e)[index]  deque下标访问进行两次下标访问 

容器适配器(用上面三个线性容器适配了容器的某些功能):

stack(堆栈)： 先进后出  后进先出
queue(队列)： 先进先出  后进后出
priority_queue(优先队列): "优"者先出

有一个经典的题目：用两个栈实现一个队列

class Solution
{
public:
    void push(int node) {
        stack1.push(node);
    }
    int pop() {
        if(!stack2.empty()){
            int res =stack2.top();
            stack2.pop();
            return res;
        }
        else {
            while(!stack1.empty()){
                stack2.push(stack1.top());
                stack1.pop();
            }
             int res =stack2.top();
            stack2.pop();
            return res;
        }
    }
private:
    stack stack1;
    stack stack2;
};

关联容器(底层实现是有序树–红黑树):

map(映射)    key-value对   一个键值对应一个value     key唯一(不重复)
	底层是红黑树
multimap(多重映射)  key-value对    key可以重复 底层是哈希表
set(集合)    没有值只有键的映射    key       key唯一不重复
	底层是红黑树
multiset(多重集合)    key可以重复  底层是哈希表

1.构造对象

map m;

2.插入元素

m[key] = value;          //如果key不存在，则插入key-value对
				如果key存在，则更新key所对应的value值
m.insert(pair(key,value))  插入一个键值对对象
	如果插入的key在map中已经存在，则插入失败，否则成功
返回值:
	pair::iterator,bool>

//pair类模板
template
class pair{
public:
	T first;
	K second;
public:
	pair(const T& t,const K& k):first(t),second(k){
		
	}
};
template
pair make_pair(const T& t,const K& k){
	return pair(t,k);
}

map的迭代器  指针一个pair对象   
map中存储的就是 pair对象    键值对
	类似于下标可以是任意类型的数组 

总结

线性容器： 频繁插入和删除 线性容器(list) 扩容比较少选择vector
关联容器: 查找 数据要经常性的进行查找，插入和删除很少 选择关联容器

STL容器共性:

1.所有的容器都支持拷贝构造和拷贝赋值 (深拷贝)，
	可以完整意义上的实现对容器的拷贝
2.所有的容器都支持 "== "  运算符。
	容器相等: 容器的类型相同，
	且容器中元素的类型相同，容器中元素的个数相等，
	对应位置元素还满足相等的特性  (类类对象 == )
3.容器中的元素都是放入源对象的拷贝  (调用拷贝构造函数生成一个新的对象)
	如果一个类把拷贝构造函数设置为私有属性，那么该类的对象将无法放入到容器中
4.容器中的元素需要支持完整的拷贝语义(深拷贝)
	智能指针(auto_ptr)不适合放在容器中
5.如果需要对容器中的元素进行排序或者查找 *** 作
	该元素的类型需要支持 "<" 和 "==" 操作符
	当然也可以提供函数对象，函数对象中实现()运算符
	class Comp{//仿函数
	public:
		bool operator()(const T& t1,const T& t2){
			
		}
	};