STL初学笔记一(vector与list)

前言

      STL是Standard Template Library的简称,中文名标准模板库,惠普实验室开发的一系列软件的统称。从根本上说,STL是一些“容器”的集合,这些“容器”有list,vector,set,map等,STL也是算法和其他一些组件的集合。STL的目的是标准化组件,这样就不用重新开发,可以使用现成的组件。STL现在是C++的一部分,因此不用安装额外的库文件。
      在学习STL的过程中主要需要掌握容器的相关算法,以及配合迭代器的用法(迭代器的功能类似于指针,但仍有些许区别)。各种容器都可能需要引入的头文件有<lterator>和<algorithm>


容器类型

序列式容器

  • 向量(vector) 连续存储的元素; #include <vector>
  • 列表(list) 由节点组成的双向链表,每个结点包含着一个元素; <list>
  • 双端队列(deque) 连续存储的指向不同元素的指针所组成的数组;<deque>

适配器容器

  • 栈(stack) 后进先出的值的排列;<stack>
  • 队列(queue) 先进先出的值的排列;<queue>
  • 优先队列(priority_queue) 元素的次序是由作用于所存储的值对上的某种谓词决定的的一种队列; <queue>

关联式容器

  • 集合(set) 由节点组成的红黑树,每个节点都包含着一个元素,节点之间以某种作用于元素对的谓词排列,没有两个不同的元素能够拥有相同的次序;<set>
  • 多重集合(multiset) 允许存在两个次序相等的元素的集合 <set>
  • 映射(map) 由{键,值}对组成的集合;<map>
  • 多重映射(multimap) 允许键对有相等的次序的映射;<map>

vector

      vector类似于支持大小动态增长的数组结构

初始化

vector va;
for(int i=0;i<5;i++)
va.push_back(i);//放5个元素进去

vector vb(va);//用va初始化vb,此种用法要求va与vb必须是同一种容器,且类型相同
vector vc{1,2,3,4};//初始化列表
vector vc2={1,2,3,4};//同上,C++11新标准
vector vd(va.begin(),va.end());//用迭代器指定的范围初始化

list li={2,3,4};
vector vli(li.begin(),li.end())//使用迭代器可以把不同容器,类型相同的元素用来初始化
vector ve(10);//包含10初始化值的元素,限制大小
vector vf(10,1);//在vf里面塞进10个1

配合数组使用int v1[10]
vector v3(&v1[0],&v1[9]);//原始数组的元素指针可以作为迭代器来使用

相关函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
vector<int> c  
c.clear() 移除容器中所有数据。
c.empty() 判断容器是否为空。
c.erase(pos) 删除pos位置的数据
c.erase(beg,end) 删除[beg,end)区间的数据
c.remove(value) 关于remove和erase之后细讲
c.remove_if(bool())
c.front() 传回第一个数据。
c.back() 传回末尾数据。
c.insert(pos,elem)在pos位置插入一个elem拷贝
c.pop_back() 删除最后一个数据。
c.push_back(elem) 在尾部加入一个数据。
sort(beg,end) 对[beg,end)区域排序
c.resize(num) 重新设置该容器的大小。
list<int>list{1,2,3};
list1.resize(5); // list1 (1,2,3,0,0)用默认值填补
list1.resize(5,4); // list1 (1,2,3,4,4)用指定值填补
c.size() 回容器中实际数据的个数。
c.begin() 返回指向容器第一个元素的迭代器
c.end() 返回指向容器最后一个元素后面一个位置的迭代器

关于remove与erase函数的具体区别是:remove(remove_if)算法描述————查找得到第一个元素的位置,然后从此位置开始遍历容器,将后面的元素依次前移,跳过和value相同值的元素,也就是说,所有和value相同值的元素都会被覆盖,而其他的元素都会依次前移。最后remove返回指向最后一个”有用”元素的iterator,但是在remove算法过程中,并没有修改原容器的size,以及end()。关于这个问题我们在最后细讲。

关于为什么end()这个迭代器指向的是最后一个指针后面一个位置,是因为这时候正好c.end()-c.begin()为整个vector的空间长度。

代码样例

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
#include <iostream>
#include <vector>
using namespace std;

vector<int> solution(vector<int>& nums,int target)
{
int size = nums.size();
vector<int> solution;
for(int i=0;i<size-1;i++)
for(int j=i+1;j<size;j++)
if(nums[i]+nums[j]==target)
{
solution.push_back(i);
solution.push_back(j);
}
return solution;
}

int main()
{
int arr[]={2,5,11,7};
vector<int> nums(arr,arr+4);
int target=13;
vector<int> ans;
ans=solution(nums,target);
if(ans.size()==0)
cout<<"error"<<endl;
else
cout<<ans[0]<<ans[1]<<endl;
return 0;
}

关于vector的功能

对于STL里的容器,可以用#include <algorithm>里面的通用的sort()和find()等函数。

排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
  //对于vector,用得最多的当然是排序功能
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
vector<int> v;
v.push_back(10);
v.push_back(20);
v.push_back(3);
v.push_back(213);
v.push_back(113);
sort(v.begin(),v.end());
int i=0;
for(i=0;i<5;i++)
{
cout<<v[i]<<endl;
}
return 0;
}

结果如下

默认是从小到大排序,那么如果我们需要从大到小呢?或者vector里面存储的是结构体,排序是根据结构体里的某个元素为依据呢?

1
2
3
4
5
6
//这时候可以加入comp函数,sort的格式变为sort(a.begin(),a.end(),comp);  
补充上即可
bool comp(const int &a,const int &b)
{
return a>b;
}
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
//对于如果是结构体里的一部分作为参照值,也是改写comp函数来实现
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

struct test
{
int a;
int b;
};
bool comp(const test &t1,const test &t2)
{
return t1.a<t2.a;
}

int main()
{
vector<test>v;
test t1,t2,t3;
t1.a=3;t1.b=245;
t2.a=1;t2.b=99;
t3.a=2;t3.b=33;
v.push_back(t1);
v.push_back(t2);
v.push_back(t3);
sort(v.begin(),v.end(),comp);
for(int i=0;i<3;i++)
{
cout<<v[i].a<<" "<<v[i].b<<endl;
}
return 0;
}

排序结果如下

查找
1
2
3
4
vector<int> temp = { 1,3,2,4,5,0 };
//find(temp.begin(),temp.end(),value);//value为要查找的值,该函数返回一个指向对应元素的迭代器
location_index=find(temp.begin(),temp.end(),2); //find函数
cout<<"数字2的下标是:"<<(location_index-temp.begin())<<endl;

list

      如果说vector容器在实际使用上比起数组的话只是在安全性上面更加效果出众,没有减少多少代码量。那么list对应的双向链表的数据结构在插入和删除链表项方面都给我们提供了非常方便的操作,而不用在指针的操作上费神。
      这两个结构由于都是序列式容器,所以比较类似。相比较的话vector继承了数组的优点,能非常好的支持随即存取,即[]操作符,所以vector的读取,用cout<<a[i]这种形式就行。list继承了双向链表删除插入操作更加方便的特性,但不支持随机访问,只能借助迭代器。
      list的很多可调用函数和vector几乎一致,但也有list独有的函数功能,下面补充几个刚刚vector里没有提到的几个函数功能。

1.assign()//该功能vector里也有

1
2
3
4
5
6
7
8
9
10
11
12
a.assign(n,val);//将a中的所有元素替换成n个val元素
ex1:
list<int>a{1,2,3,4};
a.assign(4,10);
则a中元素变为4个10.

a.assign(b.begin(),b.end())
ex2:
list<int>a{1,2,3,4,5};
list<int>b{6,7,8};
a.assign(b.begin(),b.end());
则a中元素变为6,7,8.

2.swap()//该功能vector里也有

1
2
3
4
5
6
a.swap(b)或者swap(a,b),将a,b两个list对换。
ex:
list<int>a{6,7,8,9};
list<int>b{1,2,3,4,5};
swap(a, b); //或a.swap(b)
a中元素变1,2,3,4,5 b中变6,7,8,9

3.reverse()//该功能vector里面也有
可以实现list的逆置

1
2
3
ex:list<int>a{1,2,3,4,5};
reverse(a.begin(),a.end());
a中元素变为5,4,3,2,1

4.sort()

1
2
list<int>a{1,2,3,4,5};
a.sort();//默认的sort()是增序排序,如果需要降序排序,用a.sort(greater<int>());

5.merge()
a.merge(b)b变为空,a中的元素包含原来b和a的合集
值得注意的点:
1)merge()是将两个有序的链表合并成另一个有序的链表,如果有一个
链表不是有序的那么在执行代码时会报错:说链表不是有序的。
2)还有,两个链表中的内容排序顺序与合并时采用的排序顺序必须一致,
如果不一致,也会报错,说链表不是有序的。如想要降序合并两个链表,
那么合并前的两个链表也必须是按降序排列的。

6.push_front()和pop_front()
这两个算是list双向链表形式独有的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <list>
#include <algorithm>
using namespace std;

int main()
{
list<int>a {11,13,3,5,9};
a.sort();
list<int>::iterator iter=a.begin();
for(int i=0;i<5;i++)
{
++iter;
cout<<*iter<<" ";
}
return 0;

}
  • 最后对于list和vector聊一聊erase和remove
    对于vector来说如果你想真正从容器中按条件剔除部分元素,remove函数一般是配合erase函数一起使用的。因为erase函数只能根据迭代器的位置删除东西而不具备remove函数的查找和判断能力。remove函数将有用的元素全部调到前面,把要剔除的全部放容器尾部。erase再把remove返回的对应第一个要删除的迭代器的位置到容器末尾的迭代器位置之间的元素全部消除。
1
2
3
vector<int> v;
v.erase(remove(v.begin(), v.end(), 10), v.end();//除去所有等于10的元素
cout << v.size();

但对于list来讲按条件删除元素,只用remove函数就可以了,一是因为链式结构的特殊性,二是实际上list的remove封装了两个函数的功能。

1
2
list<int> a;
a.remove(10);//除去所以等于10的元素

由于STL库的内容实在很多,第一部分关于序列式容器的使用就先总结到这。之后再补充适配器容器和关联式容器的内容。

相关链接

STL初学笔记(二)

STL初学笔记(三)

STL初学笔记(四)