Loading [MathJax]/extensions/tex2jax.js
STL 常用操作
liyusendesu
|
ALGORITHM,Basic Algorithm
|
|
1188 人看过
|
0

2014 字
|
19 分钟
本文最后更新于 665 天前，其中的信息可能已经有所发展或是发生改变。

STL 常用操作

1. vector

1.1 声明

#include <vector>   // 头文件
vector<int> a;      // 相当于一个长度动态变化的int数组
vector<int> b[233]; // 相当于第一维长233，第二位长度动态变化的int数组
struct rec{…};
vector<rec> c;      // 自定义的结构体类型也可以保存在vector中

1.2 插入和删除

a.push_back(x)把元素x插入到vector a的尾部。
a.pop_back()删除vector a的最后一个元素。

vector<int> a;
a.push_back(1);
a.push_back(2);
a.pop_back();

1.3 大小和判空

size函数返回vector的实际长度（包含的元素个数），empty函数返回一个bool类型，表明vector是否为空。二者的时间复杂度都是 O(1)\mathcal{O}(1)。

    vector<int> a;
    a.push_back(1);
    a.push_back(2);
 
    cout << a.size() << endl;
 
    a.pop_back();
    if(a.empty()) cout << "a is empty !" << endl; 
 
    a.pop_back();
    if(a.empty()) cout << "a is empty !" << endl;

Tips：

  • 所有的STL容器都支持这两个方法，含义也相同。

1.3 清空

利用clear函数把vector清空。

    vector<int> a;
    a.push_back(1);
    a.push_back(2);
 
    cout << a.size() << endl;
 
    a.clear();
    if(a.empty()) cout << "a is empty !" << endl;

1.4 迭代器

迭代器就像STL容器的“指针”，可以用星号*操作符解除引用。

一个保存int的vector的迭代器声明方法为：

vector<int>::iterator it;

vector的迭代器是“随机访问迭代器”，可以把vector的迭代器与一个整数相加减，其行为和指针的移动类似。可以把vector的两个迭代器相减，其结果也和指针相减类似，得到两个迭代器对应下标之间的距离。

接下来引入两个迭代器 begin/end，begin函数返回指向vector中第一个元素的迭代器。例如a是一个非空的vector，则*a.begin()与a[0]的作用相同。

vector<int> a;
for(int i = 1; i <= 10; i ++) a.push_back(i);
vector<int>::iterator it = a.begin();
cout << *it << endl;

所有的容器都可以视作一个“前闭后开”的结构，end函数返回vector的尾部，即第 n个元素再往后的“边界”。*a.end()与a[n]都是越界访问，其中n = a.size()。

vector<int> a;
for(int i = 1; i <= 10; i ++) a.push_back(i);
// vector<int>::iterator it = a.end();  //越界
vector<int>::iterator it = a.end() - 1;
cout << *it << endl;

此外 vector 支持利用 [] 直接访问元素。

vector<int> a;
for(int i = 1; i <= 10; i ++) a.push_back(i);
//迭代器访问
// for(vector<int>::iterator it = a.begin(); it != a.end(); it ++) cout << *it << ' ';
//[] 访问
for(int i = 0; i < a.size(); i ++) cout << a[i] << ' ';

特别地，可以利用front函数返回vector的第一个元素，等价于*a.begin()和a[0]。利用back函数返回vector的最后一个元素，等价于*--a.end()和a[a.size() – 1]。

vector<int> a;
for(int i = 1; i <= 10; i ++) a.push_back(i);
 
cout << a.front() << endl;
cout << *a.begin() << endl;
cout << a[0] << endl;
 
cout << a.back() << endl;
cout << *-- a.end() << endl;
cout << a[a.size() - 1] << endl;

2. queue

2.1 声明

#include <queue>  //头文件，包含 queue 和 priority_queue
queue<int> q;
struct rec{…}; queue<rec> q;                        //结构体rec中必须定义小于号
priority_queue<int> q;                              // 大根堆
priority_queue<int, vector<int>, greater<int>> q;   // 小根堆
priority_queue<pair<int, int>> q;

2.2 插入和删除

循环队列queue

push 将元素插入到队尾，pop 将元素从队头弹出。

queue<int> a;
a.push(1);
a.push(2);
a.pop();

优先队列priority_queue

push 将元素插入堆，pop 删除堆顶元素。

priority_queue<int> a;
a.push(1);
a.push(2);
a.pop();

2.3 访问

queue 和 priority_queue 不支持随机访问迭代器。

循环队列queue

queue<int> a;
for(int i = 1; i <= 10; i ++) a.push(i);
 
cout << a.front() << endl;  //队头元素
cout << a.back() << endl;   //队尾元素

优先队列priority_queue

priority_queue<int> a;
for(int i = 1; i <= 10; i ++) a.push(i);
 
cout << a.top() << endl;  //仅支持访问堆顶元素

3. dequeue

3.1 声明及操作

#include <dequeue>
[]              // 随机访问
begin/end       // 返回deque的头/尾迭代器
front/back      // 队头/队尾元素
push_back       // 从队尾入队
push_front      // 从队头入队
pop_back        // 从队尾出队
pop_front       // 从队头出队
clear           // 清空队列

双端队列deque是一个支持在两端高效插入或删除元素的连续线性存储空间。它就像是vector和queue的结合。与vector相比，deque在头部增删元素仅需要 O(1)\mathcal{O}(1) 的时间；与queue相比，deque像数组一样支持随机访问。

用的不多，对应操作的效率不如 vector 和 queue。

4. set

4.1 声明

#include <set>  //头文件包括 set 和 multiset
set<int> s;
struct rec{…}; set<rec> s;  // 结构体rec中必须定义小于号
multiset<double> s;

头文件set主要包括set和multiset两个容器，分别是“有序集合”和“有序多重集合”，即前者的元素不能重复，而后者可以包含若干个相等的元素。set和multiset的内部实现是一棵红黑树，它们支持的函数基本相同。

4.2 插入

a.insert(x)把一个元素x插入到集合a中，时间复杂度为 O(logn)\mathcal{O}(logn)。

在set中，若元素已存在，则不会重复插入该元素，对集合的状态无影响。

4.3 迭代器

set和multiset的迭代器称为“双向访问迭代器”，不支持“随机访问”，支持星号*解除引用，仅支持++和--两个与算术相关的操作。

一个保存int的set的迭代器声明方法为：

set<int>::iterator it;

接下来亦引入 begin/end 这俩个特殊的迭代器，分别返回集合的首、尾迭代器，时间复杂度均为 O(1)\mathcal{O}(1)。

a.begin()是指向集合中最小元素的迭代器。a.end()是指向集合中最大元素的下一个位置的迭代器。换言之，就像vector一样，是一个“前闭后开”的形式。因此-- a.end()是指向集合中最大元素的迭代器。

set<int> a;
for(int i = 10; i >= 1; i --) a.insert(i);
 
cout << *a.begin() << endl;
cout << * -- a.end() << endl;
 
//利用迭代器遍历
for(set<int>::iterator it = a.begin(); it != a.end(); it ++) cout << *it << endl;

4.4 查找

利用a.find(x)在集合a中查找等于x的元素，并返回指向该元素的迭代器。若不存在，则返回a.end()。时间复杂度为 O(1)\mathcal{O}(1)。

set<int> a;
 
for(int i = 10; i >= 1; i --) a.insert(i);
 
set<int>::iterator it = a.find(11);
if(it != a.end()) cout << "YES" << endl;
else cout << "NO" << endl;

另外提供a.count(x)返回集合a中等于x的元素个数，时间复杂度为 O(k+logn)\mathcal{O}(k+logn)，其中 k 为元素x的个数。

set<int> a;
 
for(int i = 10; i >= 1; i --) a.insert(i);
 
cout << a.count(11) << endl;

4.5 删除

提供erase 方法进行删除操作。

设it是一个迭代器，a.erase(it)从a中删除迭代器it指向的元素，时间复杂度为 O(logn)\mathcal{O}(logn)。

设x是一个元素，a.erase(x)从a中删除所有等于x的元素，时间复杂度为 O(k+logn)\mathcal{O}(k+logn)，其中 k 是被删除的元素个数。

5. map

5.1 声明

#include <map>  //头文件
map<key_type, value_type> name;
 
//例如：
map<long long, bool> vis;
map<string, int> hash;
map<pair<int, int>, vector<int>> test;

map容器是一个键值对key-value的映射，其内部实现是一棵以key为关键码的红黑树。map的key和value可以是任意类型，其中key必须定义小于号运算符。

5.2 常用操作

size/empty/clear/begin/end 均于 set 类似，但对于 insert/erase 的参数为 pair<key_type, value_type>。

map<int, int> a;
a.insert({1, 1});
a.insert({2, 1});

特别的，对于 find，a.find(x) 在变量名为 a 的 map 种，查找 key 为 x 的二元组。

map<int, int> a;
a.insert({1, 1});
a.insert({2, 1});
 
map<int, int>::iterator it = a.find(2);
if(it != a.end()){
    cout << "YES" << endl;
    cout << (*it).first << ' ' << (*it).second << endl;
}
else cout << "NO" << endl;

5.3 访问

除了和 set 一样利用迭代器进行访问，map也支持 [] 操作符进行访问。我们可以很方便地通过 a[key] 来得到key对应的value，还可以对a[key]进行赋值操作，改变key对应的value。

    map<int, int> a;
    a.insert({1, 1});
    a.insert({2, 1});
 
    cout << a[2] << endl;
    a[2] = 100;  //修改key = 2 的 value 为 100
    cout << a[2] << endl;
 
    //利用迭代器遍历
    for(map<int, int>::iterator it = a.begin(); it != a.end(); it ++) cout << (*it).first << ' ' << (*it).second << endl;

此外，C++11 提供了更方便的遍历 set/map 的方式：

    map<int, int> a;
    a.insert({1, 1});
    a.insert({2, 1});
 
    for(auto &p : a) cout << p.first << ' ' << p.second << endl;
 
    set<int> b;
    b.insert(1);
    b.insert(2);
 
    for(auto &p : b) cout << p << endl;

6. string

6.1 声明

#include <string>  //头文件
string(const char* s); //使用字符串s初始化
string(const string& str); //使用一个string对象初始化另一个string对象
string(int n, char c); //使用n个字符c初始化

string 可以视为一个动态字符数组使用。

6.2 常用操作

string str1 = "abcdefghigklmn" ;
 
string str2 = str1.substr(2,5) ;  //将str1从下标2开始的5个字符赋值给str2
 
str1.reverse(s.begin(), s.end());  //将str1 翻转
 
int p1 = str1.find(str); //从最左边开始返回str1中首次出现str首字母的下标，没有时返回-1
 
int p2 = str1.find(str,3); //从下标3开始(包括s1[3])返回str1中首次出现str首字母的下标，没有时返回-1
 
int p3 = str1.rfind(str);  //从最右边开始返回str1中首次出现str首字母的下标，没有时返回-1
 
int p4 = str1.rfind(str,3);  //下标3开始(包括s1[3])返回str1中首次出现str首字母的下标，没有时返回-1
 
string str3 = "1234.567" ;
 
double nums = atof(str3.c_str());  //将str3转换为float类型
 
int nums = atoi(str3.c_str());  //将str3转换为int类型

6.3 迭代器

string s = "abcd";
cout << s[0] << endl;
cout << s.front() << endl;
cout << *s.begin() << endl;
 
cout << s[s.size() - 1] << endl;
cout << s.back() << endl;
cout << * -- s.end() << endl;

7. pair

7.1 声明

pair 是标准库中定义的一个类模板。用于将两个变量关联在一起，组成一个“对”，而且两个变量的数据类型可以是不同的。

pair<int, int> a;
pair<int, int> b = {1, 2};
pair<int, double> c; c.first = 1, c.second = 2.333;
pair<int, int> d[100];

7.2 常用操作

在 pair 里已经预先定义了所有的比较运算符，包括 <、>、<=、>=、==、!=。当然，这需要组成 pair 的两个变量所属的数据类型定义了 == 和/或 < 运算符。

其中，<、>、<=、>= 四个运算符会先比较两个 pair 中的第一个变量，在第一个变量相等的情况下再比较第二个变量。

pair<int, string> name[10];
 
    name[0] = {3, "lys"};
    name[1] = {2, "hfcj"};
    name[2] = {3, "wjq"};
 
    sort(name, name + 3);
 
    for(int i = 0; i < 3; i ++){
        cout << name[i].first << ' ' << name[i].second << endl;
    }

Tips:

很多情况下，map 中存储的键值对通过 pair 向外暴露。

8. lower_bound/upper_bound

int a[100] = {0};
for(int i = 0; i < 10; i ++) a[i] = i + 1; 
 
sort(a, a + 10);                             //按从小到大排序 
 
int pos1 = lower_bound(a, a + 10, 7) - a;    //返回数组中第一个大于或等于被查数的值的下标 
int pos2 = upper_bound(a, a + 10, 7) - a;    //返回数组中第一个大于被查数的值的下标
 
cout << pos1 << ' ' << a[pos1] << endl;
cout << pos2 << ' ' << a[pos2] << endl;
 
sort(a, a + 10, greater<int>());                           //按从大到小排序
 
int pos3 = lower_bound(a, a + 10, 7, greater<int>()) - a;  //返回数组中第一个小于或等于被查数的值的下标 
int pos4 = upper_bound(a, a + 10, 7, greater<int>()) - a;  //返回数组中第一个小于被查数的值的下标
 
cout << pos3 << ' ' << a[pos3] <<endl;
cout << pos4 << ' ' << a[pos4] <<endl;

Tips：

  • 适用 vector 返回对应元素的迭代器。
  • 适用 map 返回对应 key 的迭代器。
  • 在一般的数组和 vector 里，这两个函数的时间复杂度均为 O(log⁡n)\mathcal{O}(\log n)，但在 set/map 等关联式容器中，直接调用 lower_bound(s.begin(),s.end(),val) 的时间复杂度是 O(n)\mathcal{O}(n) 的。
  • 为此 set/map 等关联式容器中已经封装了 lower_bound 等函数（像 s.lower_bound(val) 这样），这样调用的时间复杂度是 O(log⁡n)\mathcal{O}(\log n) 的。

9. next_permutation

作用：

  • 将当前排列更改为全排列中的下一个排列。
  • 如果当前排列已经是全排列中的最后一个排列（元素完全从大到小排列），函数返回 false 并将排列更改为全排列中的第一个排列（元素完全从小到大排列）；否则，函数返回 true。
int a[] = {1, 2, 3, 4, 5};
    do{
      for(int i = 0; i < 5; i ++) cout << a[i] << " ";
      cout << endl;
    }while(next_permutation(a, a + 5));

				

					
				

				

					
				

				

					
				

				

					
				

			
vector<int> a = {1, 2, 3, 4, 5};
    do{
      for(int i = 0; i < a.size(); i ++) cout << a[i] << " ";
      cout << endl;
    }while(next_permutation(a.begin(), a.end()));

10. 参考资料&了解更多

暂无评论

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																

							
							
						

																

							
							
						

										
					
											
						

	

		
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
	

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇
下一篇 

            

            
            推荐文章
            

            

                    
河南工程学院第六届程序设计竞赛-A组-题解

                    
                    

                    
AtCoder Beginner Contest 284（A~F）

                    
                    

                    
3493. 最大的和 (滑动窗口)

                    
                    

                    
线性代数（持续更新中）

                    
                    

                    
AtCoder Beginner Contest 260 (A·B·C)

                    
                    

                    
822. 走方格 (递归搜索树 · 二维)