c++ STL容器——deque list map queue set stack vector

Posted on | In , | |
Words count in article: 6.9k | Reading time ≈ 32

stack

1
栈的定义在头文件<stack>中，stack 模板类需要两个模板参数，一个是元素类型，一个容器类型，但只有元素类型是必要的，在不指定容器类型时，默认的容器类型为deque。

定义stack 对象的示例代码如下：

stack<int> s1;
stack<string> s2;

stack的基本操作有：对于stack<int> s

1
2
3
4
5
6
7
8
9
入     栈：      s.push(x);

出      栈：     s.pop();   //出栈只是删除栈顶元素，并不返回该元素

访问栈顶元素：    s.top();

判断栈空：    s.empty();//栈空时，返回true

栈中的元素个数：s.size();

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<iostream>
#include<stack>
using namespace std;
int main()
{
	stack<int> mys;
	mys.push(9);
	mys.push(3);
	mys.push(2);
	cout<<"mys.size: "<<mys.size()<<endl;
	while(!mys.empty())
	{
		cout<<mys.top()<<endl;
		mys.pop();
	}
	return 0;
}

queue

1
2
queue 模板类的定义在<queue>头文件中。
queue 模板类也需要两个模板参数，一个是元素类型，一个容器类型，元素类型是必要的，容器类型是可选的，默认为deque 类型。

定义queue 对象的示例代码如下：
queue<int> q1;
queue<double> q2;

queue 的基本操作有：

1
2
3
4
5
6
   入           队：q.push(x);   // 将x 接到队列的末端。
   出           队：q.pop();      //弹出队列的第一个元素，注意，并不会返回被弹出元素的值。
访问队首元素：q.front();   //即最早被压入队列的元素。
访问队尾元素：q.back();  //即最后被压入队列的元素。
    判断队列空   q.empty(); //当队列空时，返回true。
队列中的元素个数：q.size();

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<iostream>
#include<queue>
using namespace std;
int main()
{
	queue<int> myq;
	myq.push(9);
	myq.push(3);
	myq.push(2);
	cout<<"myq.size: "<<myq.size()<<endl;
	cout<<myq.front()<<endl;
	cout<<myq.back()<<endl;
	return 0;
}

vector

向量（Vector）是一个封装了动态大小数组的顺序容器（Sequence Container）。跟任意其它类型容器一样，它能够存放各种类型的对象。可以简单的认为，向量是一个能够存放任意类型的动态数组。

  1. 顺序序列
  2. 动态数组
  3. 能够感知内存分配器的（Allocator-aware）
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
1.push_back 在数组的最后添加一个数据

2.pop_back 去掉数组的最后一个数据

3.at 得到编号位置的数据

4.begin 得到数组头的指针

5.end 得到数组的最后一个单元+1的指针

6．front 得到数组头的引用

7.back 得到数组的最后一个单元的引用

8.max_size 得到vector最大可以是多大

9.capacity 当前vector分配的大小

10.size 当前使用数据的大小

11.resize 改变当前使用数据的大小，如果它比当前使用的大，者填充默认值

12.reserve 改变当前vecotr所分配空间的大小

13.erase 删除指针指向的数据项

14.clear 清空当前的vector

15.rbegin 将vector反转后的开始指针返回(其实就是原来的end-1)

16.rend 将vector反转构的结束指针返回(其实就是原来的begin-1)

17.empty 判断vector是否为空

18.swap 与另一个vector交换数据

pop_back()&push_back(elem)实例在容器最后移除和插入数据

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
#include <string.h>
#include <vector>
#include <iostream>
using namespace std;
 
int main()
{
    vector<int>obj;//创建一个向量存储容器 int
    for(int i=0;i<10;i++) // push_back(elem)在数组最后添加数据 
    {
        obj.push_back(i);
        cout<<obj[i]<<",";    
    }
 
    for(int i=0;i<5;i++)//去掉数组最后一个数据 
    {
        obj.pop_back();
    }
 
    cout<<"\n"<<endl;
 
    for(int i=0;i<obj.size();i++)//size()容器中实际数据个数 
    {
        cout<<obj[i]<<",";
    }
 
    return 0;
}

clear()清除容器中所有数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <string.h>
#include <vector>
#include <iostream>
using namespace std;
 
int main()
{
    vector<int>obj;
    for(int i=0;i<10;i++)//push_back(elem)在数组最后添加数据 
    {
        obj.push_back(i);
        cout<<obj[i]<<",";
    }
 
    obj.clear();//清除容器中所以数据
    for(int i=0;i<obj.size();i++)
    {
        cout<<obj[i]<<endl;
    }
 
    return 0;
}

排序

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
#include <string.h>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
 
int main()
{
    vector<int>obj;
 
    obj.push_back(1);
    obj.push_back(3);
    obj.push_back(0);
 
    sort(obj.begin(),obj.end());//从小到大
 
    cout<<"从小到大:"<<endl;
    for(int i=0;i<obj.size();i++)
    {
        cout<<obj[i]<<",";  
    } 
 
    cout<<"\n"<<endl;
 
    cout<<"从大到小:"<<endl;
    reverse(obj.begin(),obj.end());//从大到小 
    for(int i=0;i<obj.size();i++)
    {
        cout<<obj[i]<<",";
    }
    return 0;
}

直接数组访问&迭代器访问

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 <string.h>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
 
int main()
{
    //顺序访问
    vector<int>obj;
    for(int i=0;i<10;i++)
    {
        obj.push_back(i);   
    } 
 
    cout<<"直接利用数组："; 
    for(int i=0;i<10;i++)//方法一 
    {
        cout<<obj[i]<<" ";
    }
 
    cout<<endl; 
    cout<<"利用迭代器：" ;
    //方法二，使用迭代器将容器中数据输出 
    vector<int>::iterator it;//声明一个迭代器，来访问vector容器，作用：遍历或者指向vector容器的元素 
    for(it=obj.begin();it!=obj.end();it++)
    {
        cout<<*it<<" ";
    }
    return 0;
}

二维数组两种定义方法

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
#include <string.h>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
 
 
int main()
{
    int N=5, M=6; 
    vector<vector<int> > obj(N); //定义二维动态数组大小5行 
    for(int i =0; i< obj.size(); i++)//动态二维数组为5行6列，值全为0 
    { 
        obj[i].resize(M); 
    } 
 
    for(int i=0; i< obj.size(); i++)//输出二维动态数组 
    {
        for(int j=0;j<obj[i].size();j++)
        {
            cout<<obj[i][j]<<" ";
        }
        cout<<"\n";
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <string.h>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
 
 
int main()
{
    int N=5, M=6; 
    vector<vector<int> > obj(N, vector<int>(M)); //定义二维动态数组5行6列 
 
    for(int i=0; i< obj.size(); i++)//输出二维动态数组 
    {
        for(int j=0;j<obj[i].size();j++)
        {
            cout<<obj[i][j]<<" ";
        }
        cout<<"\n";
    }
    return 0;
}

deque

deque是一种优化了的对序列两端元素进行添加和删除操作的基本序列容器。

deque的特点：

  • 1、支持随机访问，即支持[]以及at()，但是性能没有vector好。

  • 2、可以在内部进行插入和删除操作，但性能不及list。

deque和vector的不同之处：

  • 1、两端都能够快速插入和删除元素。vector只能在尾端进行。

  • 2、deque的元素存取和迭代器操作会稍微慢一些。因为deque的内部结构会多一个间接过程。

  • 3、迭代器是特殊的智能指针，而不是一般指针。它需要在不同的区块之间跳转。

  • 4、deque可以包含更多的元素，其max_size可能更大。因为不止使用一块内存。

  • 5、不支持对容量和内存分配时机的控制。

注意：在除了首尾两端的其他地方插入和删除元素，都将会导致指向deque元素的任何pointers、references、iterators失效。不过，deque的内存重分配优于vector。因为其内部结构显示不需要复制所有元素。

  • 6、deque的内存区块不再被使用时，会被释放。deque的内存大小是可缩减的。不过，是不是这么做以及怎么做由实作版本定义。

deque的各项操作只有一下两点和vector不同：

deque不提供容量操作：capacity()和reverse()。

deque直接提供函数完成首尾元素的插入和删除。

其他均与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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
#include <deque>
#include <string>
#include <algorithm>
 
using namespace std;
 
int main()
{
	deque<string> strDeq;
 
	strDeq.assign(4,string("CHINA"));
	strDeq.push_back("first_string");
	strDeq.push_front("last_string");
 
	copy(strDeq.begin(),strDeq.end(),
		ostream_iterator<string>(cout," "));
	cout << endl;
	cout << endl;
 
	for(int i = 0;i < strDeq.size();++i)
		cout << "strDeq[" << i << "] : " << strDeq[i] << endl;
	cout << endl;
	
	for(int i = 0;i < strDeq.size();++i)
		cout << "strDeq.at(" << i << ") : " << strDeq.at(i) << endl;
	cout << endl;
 
	strDeq.pop_front();
	strDeq.pop_back();
 
	copy(strDeq.begin(),strDeq.end(),
		ostream_iterator<string>(cout," "));
	cout << endl;
	cout << endl;
 
	for(int i = 1;i < strDeq.size();++i)
		strDeq[i] = "pre" + strDeq[i];
	copy(strDeq.begin(),strDeq.end(),
		ostream_iterator<string>(cout," "));
	cout << endl;
	cout << endl;
 
	strDeq.resize(4,"resized string");
 
	copy(strDeq.begin(),strDeq.end(),
		ostream_iterator<string>(cout," "));
	cout << endl;
	cout << endl;
}

list

Lists将元素按顺序储存在链表中. 与 向量(vectors)相比, 它允许快速的插入和删除，但是随机访问却比较慢.

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
assign() 给list赋值 
back() 返回最后一个元素 
begin() 返回指向第一个元素的迭代器 
clear() 删除所有元素 
empty() 如果list是空的则返回true 
end() 返回末尾的迭代器 
erase() 删除一个元素 
front() 返回第一个元素 
get_allocator() 返回list的配置器 
insert() 插入一个元素到list中 
max_size() 返回list能容纳的最大元素数量 
merge() 合并两个list 
pop_back() 删除最后一个元素 
pop_front() 删除第一个元素 
push_back() 在list的末尾添加一个元素 
push_front() 在list的头部添加一个元素 
rbegin() 返回指向第一个元素的逆向迭代器 
remove() 从list删除元素 
remove_if() 按指定条件删除元素 
rend() 指向list末尾的逆向迭代器 
resize() 改变list的大小 
reverse() 把list的元素倒转 
size() 返回list中的元素个数 
sort() 给list排序 
splice() 合并两个list 
swap() 交换两个list 
unique() 删除list中重复的元素
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <iostream> 
#include <list> 
#include <numeric> 
#include <algorithm> 
using namespace std; 
 
//创建一个list容器的实例LISTINT 
typedef list<int> LISTINT; 
//创建一个list容器的实例LISTCHAR 
typedef list<char> LISTCHAR; 
 
void main() 
{ 
    //用list容器处理整型数据  
    //用LISTINT创建一个名为listOne的list对象 
    LISTINT listOne; 
    //声明i为迭代器 
    LISTINT::iterator i; 
    
    //从前面向listOne容器中添加数据 
    listOne.push_front (2); 
    listOne.push_front (1); 
    
    //从后面向listOne容器中添加数据 
    listOne.push_back (3); 
    listOne.push_back (4); 
    
    //从前向后显示listOne中的数据 
    cout<<"listOne.begin()--- listOne.end():"<<endl; 
    for (i = listOne.begin(); i != listOne.end(); ++i) 
        cout << *i << " "; 
    cout << endl; 
    
    //从后向后显示listOne中的数据 
    LISTINT::reverse_iterator ir; 
    cout<<"listOne.rbegin()---listOne.rend():"<<endl; 
    for (ir =listOne.rbegin(); ir!=listOne.rend();ir++) { 
        cout << *ir << " "; 
    } 
    cout << endl; 
    
    //使用STL的accumulate(累加)算法 
    int result = accumulate(listOne.begin(), listOne.end(),0); 
    cout<<"Sum="<<result<<endl; 
    cout<<"------------------"<<endl; 
    
    //-------------------------- 
    //用list容器处理字符型数据 
    //-------------------------- 
    
    //用LISTCHAR创建一个名为listOne的list对象 
    LISTCHAR listTwo; 
    //声明i为迭代器 
    LISTCHAR::iterator j; 
    
    //从前面向listTwo容器中添加数据 
    listTwo.push_front ('A'); 
    listTwo.push_front ('B'); 
    
    //从后面向listTwo容器中添加数据 
    listTwo.push_back ('x'); 
    listTwo.push_back ('y'); 
    
    //从前向后显示listTwo中的数据 
    cout<<"listTwo.begin()---listTwo.end():"<<endl; 
    for (j = listTwo.begin(); j != listTwo.end(); ++j) 
        cout << char(*j) << " "; 
    cout << endl; 
    
    //使用STL的max_element算法求listTwo中的最大元素并显示 
    j=max_element(listTwo.begin(),listTwo.end()); 
    cout << "The maximum element in listTwo is: "<<char(*j)<<endl; 
}
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <iostream> 
#include <list> 
 
using namespace std; 
typedef list<int> INTLIST; 
 
//从前向后显示list队列的全部元素 
void put_list(INTLIST list, char *name) 
{ 
    INTLIST::iterator plist; 
    
    cout << "The contents of " << name << " : "; 
    for(plist = list.begin(); plist != list.end(); plist++) 
        cout << *plist << " "; 
    cout<<endl; 
} 
 
//测试list容器的功能 
void main(void) 
{ 
    //list1对象初始为空 
    INTLIST list1; 
    //list2对象最初有10个值为6的元素 
    INTLIST list2(10,6); 
    //list3对象最初有3个值为6的元素 
    INTLIST list3(list2.begin(),--list2.end()); 
    
    //声明一个名为i的双向迭代器 
    INTLIST::iterator i; 
    
    //从前向后显示各list对象的元素 
    put_list(list1,"list1"); 
    put_list(list2,"list2"); 
    put_list(list3,"list3"); 
    
    //从list1序列后面添加两个元素 
    list1.push_back(2); 
    list1.push_back(4); 
    cout<<"list1.push_back(2) and list1.push_back(4):"<<endl; 
    put_list(list1,"list1"); 
    
    //从list1序列前面添加两个元素 
    list1.push_front(5); 
    list1.push_front(7); 
    cout<<"list1.push_front(5) and list1.push_front(7):"<<endl; 
    put_list(list1,"list1"); 
    
    //在list1序列中间插入数据 
    list1.insert(++list1.begin(),3,9); 
    cout<<"list1.insert(list1.begin()+1,3,9):"<<endl; 
    put_list(list1,"list1"); 
    
    //测试引用类函数 
    cout<<"list1.front()="<<list1.front()<<endl; 
    cout<<"list1.back()="<<list1.back()<<endl; 
    
    //从list1序列的前后各移去一个元素 
    list1.pop_front(); 
    list1.pop_back(); 
    cout<<"list1.pop_front() and list1.pop_back():"<<endl; 
    put_list(list1,"list1"); 
    
    //清除list1中的第2个元素 
    list1.erase(++list1.begin()); 
    cout<<"list1.erase(++list1.begin()):"<<endl; 
    put_list(list1,"list1"); 
    
    //对list2赋值并显示 
    list2.assign(8,1); 
    cout<<"list2.assign(8,1):"<<endl; 
    put_list(list2,"list2"); 
    
    //显示序列的状态信息 
    cout<<"list1.max_size(): "<<list1.max_size()<<endl; 
    cout<<"list1.size(): "<<list1.size()<<endl; 
    cout<<"list1.empty(): "<<list1.empty()<<endl; 
    
    //list序列容器的运算 
    put_list(list1,"list1"); 
    put_list(list3,"list3"); 
    cout<<"list1>list3: "<<(list1>list3)<<endl; 
    cout<<"list1<list3: "<<(list1<list3)<<endl; 
    
    //对list1容器排序 
    list1.sort(); 
    put_list(list1,"list1"); 
    
    //结合处理 
    list1.splice(++list1.begin(), list3); 
    put_list(list1,"list1"); 
    put_list(list3,"list3"); 
}

map

Map是STL的一个关联容器，它提供一对一（其中第一个可以称为关键字，每个关键字只能在map中出现一次，第二个可能称为该关键字的值）的数据 处理能力，由于这个特性，它完成有可能在我们处理一对一数据的时候，在编程上提供快速通道。这里说下map内部数据的组织，map内部自建一颗红黑树(一 种非严格意义上的平衡二叉树)，这颗树具有对数据自动排序的功能，所以在map内部所有的数据都是有序的，后边我们会见识到有序的好处。

  1. map是一类关联式容器。它的特点是增加和删除节点对迭代器的影响很小，除了那个操作节点，对其他的节点都没有什么影响。

  2. 对于迭代器来说，可以修改实值，而不能修改key。

  • 自动建立Key － value的对应。key 和 value可以是任意你需要的类型。

  • 根据key值快速查找记录，查找的复杂度基本是Log(N)，如果有1000个记录，最多查找10次，1,000,000个记录，最多查找20次。

  • 快速插入Key -Value 记录。

  • 快速删除记录

  • 根据Key 修改value记录。

  • 遍历所有记录。

数据的插入

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
//数据的插入--第一种：用insert函数插入pair数据  
#include <map>  
  
#include <string>  
  
#include <iostream>  
  
using namespace std;  
  
int main()  
  
{  
  
    map<int, string> mapStudent;  
  
    mapStudent.insert(pair<int, string>(1, "student_one"));  
  
    mapStudent.insert(pair<int, string>(2, "student_two"));  
  
    mapStudent.insert(pair<int, string>(3, "student_three"));  
  
    map<int, string>::iterator iter;  
  
    for(iter = mapStudent.begin(); iter != mapStudent.end(); iter++)  
  
       cout<<iter->first<<' '<<iter->second<<endl;  
  
}
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
//第二种：用insert函数插入value_type数据，下面举例说明  
  
#include <map>  
  
#include <string>  
  
#include <iostream>  
  
using namespace std;  
  
int main()  
  
{  
  
    map<int, string> mapStudent;  
  
    mapStudent.insert(map<int, string>::value_type (1, "student_one"));  
  
    mapStudent.insert(map<int, string>::value_type (2, "student_two"));  
  
    mapStudent.insert(map<int, string>::value_type (3, "student_three"));  
  
    map<int, string>::iterator iter;  
  
    for(iter = mapStudent.begin(); iter != mapStudent.end(); iter++)  
  
       cout<<iter->first<<' '<<iter->second<<endl;  
  
}
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
//第三种：用数组方式插入数据，下面举例说明  
  
#include <map>  
  
#include <string>  
  
#include <iostream>  
  
using namespace std;  
  
int main()  
  
{  
  
    map<int, string> mapStudent;  
  
    mapStudent[1] = "student_one";  
  
    mapStudent[2] = "student_two";  
  
    mapStudent[3] = "student_three";  
  
    map<int, string>::iterator iter;  
  
    for(iter = mapStudent.begin(); iter != mapStudent.end(); iter++)  
  
        cout<<iter->first<<' '<<iter->second<<endl;  
  
}

以上三种用法，虽然都可以实现数据的插入，但是它们是有区别的，当然了第一种和第二种在效果上是完成一样的，用insert函数插入数据，在数据的 插入上涉及到集合的唯一性这个概念，即当map中有这个关键字时，insert操作是插入数据不了的，但是用数组方式就不同了，它可以覆盖以前该关键字对 应的值

map的大小

Int nSize = mapStudent.size();

数据的遍历

  1. 前向迭代器
  2. 反相迭代器
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
//第二种，利用反向迭代器  
  
#include <map>  
  
#include <string>  
  
#include <iostream>  
  
using namespace std;  
  
int main()  
  
{  
  
    map<int, string> mapStudent;  
  
    mapStudent.insert(pair<int, string>(1, "student_one"));  
  
    mapStudent.insert(pair<int, string>(2, "student_two"));  
  
    mapStudent.insert(pair<int, string>(3, "student_three"));  
  
    map<int, string>::reverse_iterator iter;  
  
    for(iter = mapStudent.rbegin(); iter != mapStudent.rend(); iter++)  
  
        cout<<iter->first<<"  "<<iter->second<<endl;  
  
}
  1. 数组的形式
    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
    //第三种：用数组方式，程序说明如下  
      
    #include <map>  
      
    #include <string>  
      
    #include <iostream>  
      
    using namespace std;  
      
    int main()  
      
    {  
      
        map<int, string> mapStudent;  
      
        mapStudent.insert(pair<int, string>(1, "student_one"));  
      
        mapStudent.insert(pair<int, string>(2, "student_two"));  
      
        mapStudent.insert(pair<int, string>(3, "student_three"));  
      
        int nSize = mapStudent.size();  
      
    //此处应注意，应该是 for(int nindex = 1; nindex <= nSize; nindex++)  
    //而不是 for(int nindex = 0; nindex < nSize; nindex++)  
      
        for(int nindex = 1; nindex <= nSize; nindex++)  
      
            cout<<mapStudent[nindex]<<endl;  
      
    }

查找并获取map中的元素（包括判定这个关键字是否在map中出现）

第一种：用count函数来判定关键字是否出现，其缺点是无法定位数据出现位置,由于map的特性，一对一的映射关系，就决定了count函数的返回值只有两个，要么是0，要么是1，出现的情况，当然是返回1了

第二种：用find函数来定位数据出现位置，它返回的一个迭代器，当数据出现时，它返回数据所在位置的迭代器，如果map中没有要查找的数据，它返回的迭代器等于end函数返回的迭代器。

查找map中是否包含某个关键字条目用find()方法，传入的参数是要查找的key，在这里需要提到的是begin()和end()两个成员，

分别代表map对象中第一个条目和最后一个条目，这两个数据的类型是iterator.

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
#include <map>  
  
#include <string>  
  
#include <iostream>  
  
using namespace std;  
  
int main()  
  
{  
  
    map<int, string> mapStudent;  
  
    mapStudent.insert(pair<int, string>(1, "student_one"));  
  
    mapStudent.insert(pair<int, string>(2, "student_two"));  
  
    mapStudent.insert(pair<int, string>(3, "student_three"));  
  
    map<int, string>::iterator iter;  
  
    iter = mapStudent.find(1);  
  
    if(iter != mapStudent.end())  
  
       cout<<"Find, the value is "<<iter->second<<endl;  
  
    else  
  
       cout<<"Do not Find"<<endl;  
      
    return 0;  
}

通过map对象的方法获取的iterator数据类型是一个std::pair对象，包括两个数据 iterator->first和 iterator->second分别代表关键字和存储的数据。

第三种：lower_bound函数用法，这个函数用来返回要查找关键字的下界(是一个迭代器)

upper_bound函数用法，这个函数用来返回要查找关键字的上界(是一个迭代器)

例如：map中已经插入了1，2，3，4的话，如果lower_bound(2)的话，返回的2，而upper-bound（2）的话，返回的就是3

Equal_range函数返回一个pair，pair里面第一个变量是Lower_bound返回的迭代器，pair里面第二个迭代器是Upper_bound返回的迭代器，如果这两个迭代器相等的话，则说明map中不出现这个关键字，

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <map>  
  
#include <string>  
  
#include <iostream>  
  
using namespace std;  
  
int main()  
  
{  
  
    map<int, string> mapStudent;  
  
    mapStudent[1] = "student_one";  
  
    mapStudent[3] = "student_three";  
  
    mapStudent[5] = "student_five";  
  
    map<int, string>::iterator iter;  
  
    iter = mapStudent.lower_bound(1);  
  
    //返回的是下界1的迭代器  
  
        cout<<iter->second<<endl;  
  
    iter = mapStudent.lower_bound(2);  
  
    //返回的是下界3的迭代器  
  
        cout<<iter->second<<endl;  
  
    iter = mapStudent.lower_bound(3);  
  
    //返回的是下界3的迭代器  
  
        cout<<iter->second<<endl;  
  
    iter = mapStudent.upper_bound(2);  
  
    //返回的是上界3的迭代器  
  
        cout<<iter->second<<endl;  
  
    iter = mapStudent.upper_bound(3);  
  
    //返回的是上界5的迭代器  
  
        cout<<iter->second<<endl;  
  
    pair<map<int, string>::iterator, map<int, string>::iterator> mappair;  
  
    mappair = mapStudent.equal_range(2);  
  
    if(mappair.first == mappair.second)  
  
        cout<<"Do not Find"<<endl;  
  
    else  
  
        cout<<"Find"<<endl;  
  
    mappair = mapStudent.equal_range(3);  
  
    if(mappair.first == mappair.second)  
  
        cout<<"Do not Find"<<endl;  
  
    else  
  
        cout<<"Find"<<endl;  
  
    return 0;  
}

从map中删除元素

移除某个map中某个条目用erase（）

该成员方法的定义如下：

iterator erase（iterator it);//通过一个条目对象删除

iterator erase（iterator first，iterator last）//删除一个范围

size_type erase(const Key&key);//通过关键字删除

clear()就相当于enumMap.erase(enumMap.begin(),enumMap.end());

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
#include <map>  
  
#include <string>  
  
#include <iostream>  
  
using namespace std;  
  
int main()  
  
{  
  
       map<int, string> mapStudent;  
  
       mapStudent.insert(pair<int, string>(1, "student_one"));  
  
       mapStudent.insert(pair<int, string>(2, "student_two"));  
  
       mapStudent.insert(pair<int, string>(3, "student_three"));  
  
        //如果你要演示输出效果，请选择以下的一种，你看到的效果会比较好  
  
       //如果要删除1,用迭代器删除  
  
       map<int, string>::iterator iter;  
  
       iter = mapStudent.find(1);  
  
       mapStudent.erase(iter);  
  
       //如果要删除1，用关键字删除  
  
       int n = mapStudent.erase(1);//如果删除了会返回1，否则返回0  
  
       //用迭代器，成片的删除  
  
       //一下代码把整个map清空  
  
       mapStudent.erase( mapStudent.begin(), mapStudent.end() );  
  
       //成片删除要注意的是，也是STL的特性，删除区间是一个前闭后开的集合  
  
       //自个加上遍历代码，打印输出吧  
  
}

map中的swap用法

map中的swap不是一个容器中的元素交换，而是两个容器所有元素的交换。

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
map的基本操作函数：

     C++ maps是一种关联式容器，包含“关键字/值”对

     begin()         返回指向map头部的迭代器

     clear(）        删除所有元素

     count()         返回指定元素出现的次数

     empty()         如果map为空则返回true

     end()           返回指向map末尾的迭代器

     equal_range()   返回特殊条目的迭代器对

     erase()         删除一个元素

     find()          查找一个元素

     get_allocator() 返回map的配置器

     insert()        插入元素

     key_comp()      返回比较元素key的函数

     lower_bound()   返回键值>=给定元素的第一个位置

     max_size()      返回可以容纳的最大元素个数

     rbegin()        返回一个指向map尾部的逆向迭代器

     rend()          返回一个指向map头部的逆向迭代器

     size()          返回map中元素的个数

     swap()           交换两个map

     upper_bound()    返回键值>给定元素的第一个位置

     value_comp()     返回比较元素value的函数

set

关于set，必须说明的是set关联式容器。set作为一个容器也是用来存储同一数据类型的数据类型，并且能从一个数据集合中取出数据，在set中每个元素的值都唯一，而且系统能根据元素的值自动进行排序。应该注意的是set中数元素的值不能直接被改变。

常用的方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
begin()     　　 ,返回set容器的第一个元素

end() 　　　　 ,返回set容器的最后一个元素

clear()   　　     ,删除set容器中的所有的元素

empty() 　　　,判断set容器是否为空

max_size() 　 ,返回set容器可能包含的元素最大个数

size() 　　　　 ,返回当前set容器中的元素个数

rbegin　　　　 ,返回的值和end()相同

rend()　　　　 ,返回的值和rbegin()相同

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
#include <iostream>
#include <set>

using namespace std;

int main()
{
    set<int> s;
    s.insert(1);
    s.insert(2);
    s.insert(3);
    s.insert(1);
    cout<<"set 的 size 值为 ："<<s.size()<<endl;
    cout<<"set 的 maxsize的值为 ："<<s.max_size()<<endl;
    cout<<"set 中的第一个元素是 ："<<*s.begin()<<endl;
    cout<<"set 中的最后一个元素是:"<<*s.end()<<endl;
    s.clear();
    if(s.empty())
    {
        cout<<"set 为空 ！！！"<<endl;
    }
    cout<<"set 的 size 值为 ："<<s.size()<<endl;
    cout<<"set 的 maxsize的值为 ："<<s.max_size()<<endl;
    return 0;
}

插入3之后虽然插入了一个1，但是我们发现set中最后一个值仍然是3，这就是set 。还要注意begin() 和 end()函数是不检查set是否为空的，使用前最好使用empty()检验一下set是否为空.

count() 用来查找set中某个某个键值出现的次数。这个函数在set并不是很实用，因为一个键值在set只可能出现0或1次，这样就变成了判断某一键值是否在set出现过了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
#include <set>

using namespace std;

int main()
{
    set<int> s;
    s.insert(1);
    s.insert(2);
    s.insert(3);
    s.insert(1);
    cout<<"set 中 1 出现的次数是 ："<<s.count(1)<<endl;
    cout<<"set 中 4 出现的次数是 ："<<s.count(4)<<endl;
    return 0;
}

equal_range() ，返回一对定位器，分别表示第一个大于或等于给定关键值的元素和 第一个大于给定关键值的元素，这个返回值是一个pair类型，如果这一对定位器中哪个返回失败，就会等于end()的值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <set>

using namespace std;

int main()
{
    set<int> s;
    set<int>::iterator iter;
    for(int i = 1 ; i <= 5; ++i)
    {
        s.insert(i);
    }
    for(iter = s.begin() ; iter != s.end() ; ++iter)
    {
        cout<<*iter<<" ";
    }
    cout<<endl;
    pair<set<int>::const_iterator,set<int>::const_iterator> pr;
    pr = s.equal_range(3);
    cout<<"第一个大于等于 3 的数是 ："<<*pr.first<<endl;
    cout<<"第一个大于 3的数是 ： "<<*pr.second<<endl;
    return 0;
}

erase(iterator) ,删除定位器iterator指向的值

erase(first,second),删除定位器first和second之间的值

erase(key_value),删除键值key_value的值

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
#include <iostream>
#include <set>

using namespace std;

int main()
{
    set<int> s;
    set<int>::const_iterator iter;
    set<int>::iterator first;
    set<int>::iterator second;
    for(int i = 1 ; i <= 10 ; ++i)
    {
        s.insert(i);
    }
    //第一种删除
    s.erase(s.begin());
    //第二种删除
    first = s.begin();
    second = s.begin();
    second++;
    second++;
    s.erase(first,second);
    //第三种删除
    s.erase(8);
    cout<<"删除后 set 中元素是 ：";
    for(iter = s.begin() ; iter != s.end() ; ++iter)
    {
        cout<<*iter<<" ";
    }
    cout<<endl;
    return 0;
}

set中的删除操作是不进行任何的错误检查的，比如定位器的是否合法等等，所以用的时候自己一定要注意。

find() ，返回给定值值得定位器，如果没找到则返回end()。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
#include <set>

using namespace std;

int main()
{
    int a[] = {1,2,3};
    set<int> s(a,a+3);
    set<int>::iterator iter;
    if((iter = s.find(2)) != s.end())
    {
        cout<<*iter<<endl;
    }
    return 0;
}
1
2
3
insert(key_value); 将key_value插入到set中 ，返回值是pair<set<int>::iterator,bool>，bool标志着插入是否成功，而iterator代表插入的位置，若key_value已经在set中，则iterator表示的key_value在set中的位置。

inset(first,second);将定位器first到second之间的元素插入到set中，返回值是void.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <set>

using namespace std;

int main()
{
    int a[] = {1,2,3};
    set<int> s;
    set<int>::iterator iter;
    s.insert(a,a+3);
    for(iter = s.begin() ; iter != s.end() ; ++iter)
    {
        cout<<*iter<<" ";
    }
    cout<<endl;
    pair<set<int>::iterator,bool> pr;
    pr = s.insert(5);
    if(pr.second)
    {
        cout<<*pr.first<<endl;
    }
    return 0;
}

lower_bound(key_value) ，返回第一个大于等于key_value的定位器

upper_bound(key_value)，返回最后一个大于等于key_value的定位器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
#include <set>

using namespace std;

int main()
{
    set<int> s;
    s.insert(1);
    s.insert(3);
    s.insert(4);
    cout<<*s.lower_bound(2)<<endl;
    cout<<*s.lower_bound(3)<<endl;
    cout<<*s.upper_bound(3)<<endl;
    return 0;
}
Donate? comment?