logo
搜索
我的图书馆

发文章

发文工具

其他工具

留言交流
搜索
分享

STL容器的常用方法

 CodeNutter 2016-07-24

以下内容如有错误，欢迎指出。

STL容器都是以类模板的形式实现的，所以在使用之前必须用类型进行实例化为具体的模板类

vector

以int类型实例化

vector<int> vec1;//构造空的vector
vector<int> vec2(10);//构造大小为10，值按照默认初始化规则默认初始化
vector<int> vec3(10, 1);//构造大小为10，初始值为1
vector<int> vec4(vec2);//通过拷贝vec2来构造
vector<int> vec5(vec3.begin(), vec3.end);//用[First,last)之间的元素来构造

vec1=vec2;//赋值操作
vec1.size();//返回vec1的大小，这里为10
vec1.empty();//判断vec1是否为空，为空返回true，否则返回false
vec1.at(n);//返回vec1中的第n个元素的引用，会判断是否越界
vec1[n];//返回vec1中的第n个元素的引用，不会判断是否越界
vec1.front();//返回vec1中的头元素的引用
vec1.back();//返回vec1中的最后一个元素的引用
vec1.push_back(1);//在vec1的最后插入值为1的元素，可能会引起空间从新分配
vec1.pop_back();//删除vec1的最后一个元素
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15

注意：vector没有pop_front和push_front操作

vector<int>::iterator it1=vec1.begin();//返回头迭代器
vector<int>::iterator it2=vec1.end();//返回尾后迭代器
vector<int>::iterator it3=vec1.rbegin();//返回尾后迭代器
vector<int>::iterator it4=vec1.rend();//返回头迭代器
  • 1
  • 2
  • 3
  • 4

注意：插入操作都是在position（哨兵迭代器）之前插入

vector<int>::iterator it=vec1.insert(2,4);//在vec1第三个元素之前插入值为4的元素，返回插入元素的迭代器
vec1.insert(2,3,4);//在vec1的第三个元素之前插入3个值为4的元素，返回void
vec1.insert(2,vec3.begin(),vec3.end());//在vec1的第3个元素之前插入[First,last)
vec1.assign(vec3.begin(),vec3.begin()+5);//将vec3的前5个元素赋值给vec1前5个元素
vec1.erase(1);//删除vec1的第2个元素，其实真实操作是把后面的元素依次向前复制
vec1.erase(vec1.begin(),vec.begin()+2);//删除迭代器范围内的元素
vec1.clear();//删除所有元素

vec1.swap(vec2);//交换两个vector
vec1.reserve(20);//重新分配大小为20
vec1.capacity();//返回当前分配的存储空间的长度（这个可能比实际需求的空间大）
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11

注意：

  • vector分配的空间是连续的
  • vector插入元素，如果不引起空间重新分配，会使插入位置以后的迭代器全部失效。如果引起空间重新分配，所有迭代器都会失效。
  • 删除元素，会使当前位置及后面的所有迭代器失效。
  • vector的迭代器是Random Access itreator，可以说是类似一般指针，在侯捷的《STL的源码剖析》中typedef value_type* iterator。而在VS中就是类似一般指针，由于属于派生类，sizeof大小为12。但是总体来说都支持一般指针的所有操作。

list

以int类型实例化

list<int> l1;//构造一个空list
list<int> l2(10,1);//构造大小为10，元素值为1
list<int> l3(l2);//通过拷贝l2来构造
list<int> l4(l3.begin(), l3.begin()+5);//用[first,last)来构造


l1=l2;//赋值操作
l2.resize(20);//将l2的大小变为20，在以前list尾节点后面追加int()元素，若大小比以前小直接从后删除多余的节点
l2.resize(25,2);//将l2大小变为25，增加的元素的值为2，若大小比以前小直接从后删除多余的节点
l1.size();//返回l1的大小
l1.empty();//判断是否为空，为空，返回true；否则返回false


l1.front();//返回第一个元素的引用
l1.back();//返回最后一个元素的引用
l1.push_front(5);//在第一个位置之前插入一个值为5元素，返回void
l1.pop_front();//删除第一个元素，返回void
l1.push_back(5);//插入一个值为5的元素到最后，返回void
l1.pop_back();//删除最后一个元素，返回void


list<int>::iterator it1;
it1=l1.begin();//返回起始迭代器，头的下一个，list源码实现中head是一个空节点
l1.end();//返回尾后迭代器
l1.rbegin();//返回尾后迭代器
l1.rend();//返回头迭代器


l2.insert(l2.end(), 2);//在l2的尾端插入一个值为2的元素，返回指向插入元素的迭代器
l2.insert(l2.begin(), 4, 3);//在l2的起始位置插入4个值为3的元素，返回void
l2.insert(l2.begin(), l1.begin(), l1.end());//在l2的起始位置插入l1的区间[first,last)，返回void
l2.assign(l1.begin(), l1.begin()+3);//用[first,last)重新给l2赋值，先删除l2的所有元素再插入
l2.assign(5,4);//先删除l2的所有元素再插入5个值为4的元素
l2.erase(l2.begin());//删除l2的第一个元素，返回下一个迭代器
l2.erase(l2.begin(), l2.begin()+2);//删除[first,last)区间元素，返回指向删除区间的下一个元素的迭代器
l2.clear();//删除所有元素
l1.remove(5);//删除所有元素之等于5的节点，返回void
l1.remove_if(predicate);//删除所有让一元谓词为true的元素
l1.unique();//删除每一个和前一个元素相同的元素


l3.sort();//用<操作排序
l4.sort(predicate);//用满足谓词的顺序排序
l3.merge(l4);//合并l4到l3（要求两个链表都为有序队列，按递增排序）
l1.swap(l3);//交换l1和l3，返回void
l1.splice(l1.begin()+1, l3);//将l3拼接在l1.begin()+1之后，返回void
l1.splice(l1.begin(), l4, l4.begin());//将l4.begin()所指节点拼接到l1的第一个节点之后，返回void
l1.splice(l1.begin(), l5.begin(), l5.end());//将[first,last)拼接到l1的第一个节点之后，返回void
l1.reverse();//倒置链表
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49

list的迭代器型别是Bidirectional iterator

list<int>::iterator it=l1.begin();//list的迭代器支持以下操作
operator*();
operator->();
operator++();//前自加
operator++(int);//后自加
operator--();
operator--(int);
operator==();
operator!=();
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

注意

  • list分配的空间是非连续空间
  • list巧妙的实现为一个环状链表，链表的head为一个空节点
  • list的插入操作不会造成迭代器失效，删除操作只会使指向被删除元素的迭代器失效

deque（双端队列）

以int类型实例化

deque<int> deq1;//构造一个空deque
deque<int> deq2(10);//构造大小为10的deque，值为int()
deque<int> deq3(10,4);//大小为10，值为4
deque<int> deq4(deq3);//拷贝构造
deque<int> deq5(deq4.begin(), deq4.end());//拷贝[first,last)来构造


deq1=deq2;//赋值
deq1.begin();//返回头迭代器
deq1.end();//返回尾后迭代器
deq1.rbegin();//返回尾后迭代器
deq1.rend();//返回头迭代器


deq1.resize(15);//重新分配大小，并在后面填补值为int()的元素
deq1.resize(20,4);//重新分配大小，并在后面填补值为4的元素
deq1.size();//返回队列大小
deq1.empty();//判断队列是否为空，为空返回true，否则返回false


deq1.at(5);//返回位置为5的元素的引用，以0为基准
deq1[5];//返回位置为5的元素的引用，以0为基准
deq1.front();//返回第一个元素的引用
deq1.back();//返回最后一个元素的引用
deq1.push_front(4);//在队列头的位置插入一个值为4的元素
deq1.pop_front();//删除队列的第一个元素
deq1.push_back(4);//在队列的最后
deq1.pop_back();//删除队列的最后一个元素


deq2.assign(deq1.begin(), deq1.begin()+10);//用[first,last)来赋值，先删除所有元素
deq2.assign(10,3);//先删除所有元素，再分配10个大小，值为3
deq2.insert(deq2.begin(), 7);//在队列头插入值为7的元素
deq2.insert(deq2.begin(), 3, 7);//在队列头插入3个值为7的元素
deq2.insert(deq2.begin(), deq1.begin(),deq1.begin()+4);//插入[first,last)
deq2.erase(deq2.begin());//删除迭代器所指元素
deq2.erase(deq2.begin(),deq2.begin()+3);//删除[first,last)区间元素
deq2.clear();//删除所有元素
deq3.swap(deq1);//交换两个队列
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39

deque的迭代器型别是Random Access iterator

deque<int>::iterator it=deq1.begin();//deque的迭代器支持以下操作
operator*();
operator->();
operator++();//前自加
operator++(int);//后自加
operator--();
operator--(int);
operator+();
operator+=();
operator-();
operator-=();
operator[]();
operator==();
operator!=();
operator>();
operator<();
operator>=();
operator<=();
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18

注意

  • deque分配的空间是分段定量连续空间，为了维持整体连续的假象，采用一块map（一小块连续空间），其中每个元素（node）都是指针，指向另一段较大的连续线性空间，称为缓冲区，这才是存储空间主体。
  • deque的迭代器型别是Random Access iterator，实现起来比vector的迭代器复杂。
  • deque插入元素到首尾时，会使首尾迭代器失效，但是指向元素的引用和指针不会失效，插入到除首尾之外的其他位置会导致迭代器、引用和指针失效。删除首尾元素，会使首尾迭代器失效，删除首尾之外的其他位置的元素会导致迭代器、引用和指针失效。

queue（先进先出，底端进顶端出）

queue的默认底层实现容器是deque

以int类型实例化

queue<int> que1;//构造空的queue
queue<int> que2(deque<int>(5,3));//deque容器来构造

que1.empty();//判断是否为空，为空返回true，否则返回false
que1.size();//返回队列大小
que1.front();//返回队列的第一个元素的引用
que1.back();//返回队列最后一个元素的引用
que1.push(1);//从底端插入
que1.pop();//从顶端删除，返回void
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

注意：queue只能从头尾访问元素，不提供迭代器，不能遍历。

priority_queue(优先队列)

默认底层实现容器为vector，默认用最大堆（max-heap）完成优先

以int类型实例化

priority_queue<int> prique1;//构造空的优先队列
priority_queque<int> prique2(vec1.begin(), vec1.end());//用一个vector的[first,last)区间来构造

prique2.empty();//判断队列是否为空
prique2.size();//
prique2.top();//返回最高优先级元素的引用
prique2.push(1);//插入值为1的元素，会进行堆排序
prique2.pop();//删除最高优先级元素
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8

注意：priority_queue只有顶端元素才能被外界取用，不提供迭代器，不提供遍历

stack(先进后出，顶端出入)

默认底层实现容器deque

以int类型实例化

stack<int> sta1;//构造一个空的stack
stack<int> sta2(deque<int>(5,3));//用deque容器构造

sta2.empty();
sta2.size();
sta2.top();//返回顶端元素的引用
sta2.push(1);//从顶端插入值为1的元素
sta2.pop();//从顶端删除元素
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8

注意：stack是先进先出的数据结构，只能从顶端存取元素，不提供迭代器，不提供遍历

map

map的实现分两种：继承rb_tree实现、组合rb_tree实现

  • 底层以RB_tree(红黑树)实现key排序，每个节点的值叫value_type。默认用了less<key_type>模板函数作为key_compare。
  • map要注意区分key_type，value_type，mapped_type。其中value_type=pair<cosnt key_type, mapped_type>
  • map的模板声明：
    template<class _Kty,//键值类型
    class _Ty,//映射值类型
    class _Pr = less<_Kty>,//键值比较仿函数类型,默认less
    class _Alloc = allocator<pair<const _Kty, _Ty> > >//配置器类型
    class map;
map<string, int> students1;//构造一个空的map
map<string, int> students2;//
  • 1
  • 2

注意：用insert向map中插入元素时，采用的底层机制rb_tree的insert_unique()实现。如果已经有键值相等的元素则插入失败，如果没有相同键值的元素存在则插入。operator[]操作，先查找map中是否有相同键值，如果有就返回mapped_type的引用，如果没有就插入mapped_type(),也就是默认值，然后返回mapped_type的引用。插入操作和删除操作都会进行红黑树的调整，但是只会使当前迭代器失效，对其他迭代器没有影响

students1["xiaoming"]=9;//相当于查找或插入xiaoming，对返回的mapped引用赋值
students1.insert(pair<string,int>("xiaohong",10));//插入一个pair
students1.insert(make_pair("xiaozhang",11));//插入一个pair
students1.insert(map<string,int>::value_type("xiaoli,10"));

students2=students1;//赋值运算
map<string,int>::iterator it=students2.begin();//返回map的第一个迭代器
students1.end();//返回map的尾后迭代器

students2.erase(it);//删除it迭代器所指的元素，返回指向下一个元素的迭代器
students2.erase("xiaoli");//删除students2中键值和“xiaoli”相同的元素，返回删除的所有匹配元素的个数
students2.erase(students2.begin(),students2.begin()+1);删除[first,last)区间元素
students2.clear();//删除所有元素

students1.size();//返回map容器的大小
students1.empty();//判断map容器是否为空
students1.find("xiaoming");//返回指向配置键值元素的迭代器，如果没有找到就返回尾后迭代器
students1.count("xiaoming");//返回所有键值匹配元素的个数
students1.lower_bound("xiaoming");//返回指向最左端不小于这个键值的元素的迭代器（这里的例子不合适用这个方法,单单说明这个方法的用法）
students1.upper_bound("xiaoming");//返回指向最左端大于这个键值的元素的迭代器
students1.swap(students2);//交换两个map
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21

map的迭代器型别是bidirectional iterator，自增自减都是通过rb_tree的迭代器的内部函数实现的

map的迭代器支持以下主要操作
operator*();
operator->();
operator++();//前自加
operator++(int);//后自加
operator--();
operator--(int);
operator==();
operator!=();
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

注意

  • map分配的节点空间是非连续空间。每个节点也就是红黑树的节点，包括left，right，parent，color，value_type成员变量。
  • map的迭代器型别是bidirectional access iterator，实现起来比list的迭代器复杂。
  • map插入操作不会造成迭代器失效，删除操作只会使指向被删除元素的迭代器失效。
  • operator[]操作，先查找map中是否有相同键值，如果有就返回mapped_type的引用，如果没有就插入mapped_type(),也就是默认值，然后返回mapped_type的引用。

set

set的实现和map一样也分两种：继承rb_tree实现、组合rb_tree实现

  • 底层以RB_tree(红黑树)实现key排序，只有键值，key_type和value_type是一样的。默认用了less<key_type>模板函数作为key_compare。
  • set的模板声明：
    template<class _Kty,//健
    class _Pr = less<_Kty>,//用于排序比较仿函数
    class _Alloc = allocator<_Kty> >
    class set；
int array[5]={0,1,2,3,4};
set<int> orderset1(array,array+5);//用[first,last)构造一个set
set<int> orderset2;//构造一个空的set
  • 1
  • 2
  • 3

注意：用insert向set中插入元素时，采用的底层机制rb_tree的insert_unique()实现。如果已经有键值相等的元素则插入失败，如果没有相同键值的元素存在则插入。插入操作和删除操作都会进行红黑树的调整，但是只会使当前迭代器失效，对其他迭代器没有影响

orderset1.insert(10);//插入一个键值为10的元素
orderset2=orderset1;//赋值运算
set<int>::iterator it=orderset1.begin();//返回set的第一个迭代器
orderset1.end();//返回set的尾后迭代器

orderset1.erase(it);//删除it迭代器所指的元素，返回指向下一个元素的迭代器
orderset1.erase(0);//删除orderset1中键值为0相同的元素，返回删除的所有匹配元素的个数
orderset1.erase(orderset1.begin(),orderset1.begin()+1);删除[first,last)区间元素
orderset1.clear();//删除所有元素

orderset2.size();//返回set容器的大小
orderset2.empty();//判断set容器是否为空
orderset2.find(4);//返回指向键值为4的元素的迭代器，如果没有找到就返回尾后迭代器
orderset2.count(2);//返回所有键值匹配元素的个数
orderset2.lower_bound(3);//返回指向最左端不小于这个键值的元素的迭代器
orderset2.upper_bound(4);//返回指向最左端大于这个键值的元素的迭代器
orderset2.swap(orderset1);//交换两个set
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17

set的迭代器型别是bidirectional iterator，自增自减都是通过rb_tree的迭代器的内部函数实现的

set的迭代器支持以下主要操作
operator*();
operator->();
operator++();//前自加
operator++(int);//后自加
operator--();
operator--(int);
operator==();
operator!=();
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

注意

  • set分配的节点空间是非连续空间。每个节点也就是红黑树的节点，包括left，right，parent，color，value_type成员变量。
  • set的迭代器型别是bidirectional access iterator，实现起来比list的迭代器复杂。
  • set插入操作不会造成迭代器失效，删除操作只会使指向被删除元素的迭代器失效。

multimap

multimap的特性和用法与map基本相同，差别在于它允许键值重复，因此它的插入操作采用的底层机制rb_tree的insert_equal()而非insert_unique()。还有就是multimap不支持operator[]操作。

multiset

multiset的特性和用法与set完全相同，唯一的差别在于它允许键值重复，因此它的插入操作采用的底层机制rb_tree的insert_equal()而非insert_unique()。

    本站是提供个人知识管理的网络存储空间，所有内容均由用户发布，不代表本站观点。请注意甄别内容中的联系方式、诱导购买等信息，谨防诈骗。如发现有害或侵权内容，请点击一键举报。
    转藏 分享 献花（0）

    来自： CodeNutter > 《C/C 》

    举报/认领

    0条评论

    发表

    请遵守用户 评论公约

    类似文章 更多