CSTL容器简介(一)
容器分类序列式 容器-ordered
代表:vector, deque, list
特点:元素存储有固定位置,与元素值无关关联式 容器-sorted
代表:set, multiset, map, multimap
特点:元素存储位置与值有关,与插入次序无关各个容器优缺点Vector
Vector利用一段连续内存管理元素,类似数组
优点:利用索引直接存取,尾插 如速度快
缺点:头部插入慢 ,要依次移动所有元素让位置,不太适合大量元素
vector intVec; intVec.push_back(123); //尾部插入 intVec[1] == 123 //数组下标法读取, 随机读取deque
deque和vector类似,也利用连续内存管理元素,可向两端扩展,
优点:利用索引直接存取,头插,尾插 如速度快
缺点:中间插 入慢,要依次移动所有元素让位置。deque douDeque; douDeque.push_front( 1*1.1 ) //头部插入 douDeque/push_back( 2*2.2) //尾部插入 list
list采用双向链表管理元素,内存可以不连续
优点:任何位置插入 速度都快,内存分配灵活
缺点:不支持随机存取,查找费时 list testList; testList.push_back( 345 ); //尾部插入 testList.front(); //返回第一个元素 testList.pup_front(); //删除第一个元素 //list支持很多操作方法,比如insert earse等…set
set类似集合,特点是不允许有重复值,内部元素根据值自动排序。
优点:红黑树存储,插入删除快,二分查找速度比较快
缺点:不能直接修改元素值multiset
相比set,允许有重复的元素值map
map支持key-value这样的字典查询方式,红黑树存储结构
优点:根据key值查找速度快
缺点:空间占用高,插入删除查找都是logn时间复杂度,不支持随机存取multimap
相比map,支持1个key多应多个value的存储,key-value是多对多的关系。