內容提要

STL

---

?

?

STL

?

首先，拒絕兩個問題：

• 這東西我自己也能寫吖
• 這東西怎么寫吖（比如STL的sort是七八個排序放一塊的...）

?

Pair

#include<utility> using namespace std; pair<typename1,typename2> variablename;pair<int,int> x; pair<double ,double> y; pair<int,double> z; pair<pair<int,int>int>a;

作為需要返回多個量的函數(shù)返回值

作為結構體的代替

比較大小：先比較第一個元素，如果相同再比較第二個，以此類推

String

string a;

#include <string> using namespace std; string a;

作為字符串數(shù)組的替代

可以賦值

a = b,a = "hello word"

a[i]:支持下表訪問

a.size()字符串長度

a+b:字符串拼接

vector

有編號為1到3000*3000的人，每個人都屬于一個隊伍，一共有3000個隊伍，每個隊伍可能有任意多數(shù)人，也可能沒有人，如何存數(shù)？

const int maxN = 3000; const int maxM = 3000 * 3000; int team[maxN][maxM];

?

?

?

?

?

?

vector：不定長數(shù)組：不需要指定數(shù)組元素的數(shù)量，可以直接通過元素的個數(shù)分配內存

#include <vector> using namespace std; vector<TypeName> VariableName; vector<int> a; vector<double> b; vector<vector<int> > c;

?

a[0]：隨機下標訪問

a.push_back():在末尾插入一個元素

a.pop_back:彈出末尾元素

a.front():訪問第一個元素

a.back():訪問最后一個元素

a.clear():清空一個vector

a.empty():返回vector是否為空

a.size():返回vector總元素的個數(shù)

以上的除了清空vector復雜度為O(n)，其他均為O(1)

工作原理:每當你添加第2^n +1個元素時，就開一個連續(xù)的2^(n+1)的內存來存儲

但是由于他每次要分配內存，所以會慢一些

樣例：接受n個整數(shù)的輸入，倒序輸出

#include <iostream> using namespace std; int main() {vector<int> a;int n, x;cin >> n;for (int i = 0; i < n; ++i) {cin >> x;a.push_back(x);}while (!a.empty()) {cout << a.back();a.pop_back();}return 0; }

?

迭代器

vector<int>::iterator it;

迭代器（iterator）的作用類似于指針，是一個指明元素位置的量。什么類型的vector就要用什么位置的迭代器

a.begin()：返回第一個元素的迭代器

a.end():返回最后一個元素的后一個迭代器（因為左閉右開嘛）

*a.begin():等價于a.front()

*it:得到it指向的值

it++:得到下一個位置的迭代器

it+=i:得到下i個位置的迭代器，時間復雜度O(1)

it1 - it2:得到it1和it2之間的元素個數(shù)

遍歷vector:

int main() {for(auto x:a){}//遍歷 }

?

set:

集合：不能有重復元素+有序性

#include <set> using namespace std; set<TypeName> VariableName; set<int> a; set<double> b;

?

set的底層使用紅黑樹這個數(shù)據(jù)結構來維護集合

a.begin():第一個元素的迭代器

a.end():最后一個元素的后一個迭代器

a.insert():插入一個元素 O(log n)

a.erase():刪除一個元素 O(log n)

a.find():尋找一個元素 O(log n)

a.count():查找某個元素的數(shù)量 O(log n)

a.lower_bound():查找大于等于某個值的第一個元素 O(log n)

a.upper_bound():查找大于某個值的第一個元素 O(log n)

a.equal_range():查找等于某個值的左閉右開區(qū)間，返回一個pair O(log n)

#include <set> #include <iostream> using namespace std; int main() {set<int> a;a.insert(1); // a: {1}a.insert(1); // a: {1}a.insert(2);remove: {1, 2}a.erase(1); // a: {2}for (int i = 0; i < 5; ++i) {a.insert(i);} // a: {0, 1, 2, 3, 4}cout << a.size() << endl; // 5cout << a.count(4) << endl; // 1 }

Set 的迭代器和 Vector 的不同。

set<int>::iterator it;

? *it: it 的求值

? ++it: it 的下一個迭代器

? --it: it 的前一個迭代器

? Vector: 隨機訪問迭代器

? Set: 雙向迭代器

它并不滋茲減法

重載運算符：

?

struct Student {int grade;char name[20]; }bool operator <(Student a, Student b) {return a.grade < b.grade; }

或者也可以這么寫

struct Student {int grade;char name[20];bool operator <(Student b) {return grade < b.grade;} }

MultiSet

#include <set> using namespace std; multiset<TypeName> VariableName; multiset<int> s;

multiset 和 set 大部分操作相同，但支持在一個 set 內有多個元素。

注意在 multiset 中，如果 erase 一個數(shù)，仍然會把全部的數(shù)字刪除。

Map

Problem

給出許多學生的名字和成績，要求使用名字找到成績。

比如學生 __debug 的微積分 59 分，我們希望能通過 __debug 找到 59.

a['__debug'] = 59 ?

#include <map> using namespace std; map<TypeName1, TypeName2> VariableName; map<string, int> a;

?map 的本質就是一個元素為 pair 的 set，重載了 [] 運算符。

stack棧

#include <stack> using namespace std; stack<TypeName> VariableName; stack<int> a;

一個“先進后出”結構。

a.size()

a.empty()

a.top(): 訪問棧頂元素

a.pop(): 彈出棧頂

a.push(): 壓入一個元素

queue隊列

#include <queue> using namespace std; queue<TypeName> VariableName; queue<int> a;

一個“先進先出”結構。

一個類似隊列的結構。不同的是，隊列每次出最先進隊的元素，優(yōu)先隊列每次出最大的元素

類似 Set，需要重載 < 運算符

a.size()

a.empty()

a.top(): 訪問堆頂

a.pop(): 彈出堆頂

a.push(): 向堆中加入一個元素

當然也可以不用

priority_queue<int ,vector<int>,less<int> > q;//大根堆 priority_queue<int ,vector<int>,greater<int> > q;//小根堆

或者這樣

struct cmp {bool operator()(int x,int y){return x<y;} } priority_queue<int ,vector<int>,cmp > q;

Algorithm
Sort

#include <algorithm> using namespace std; int a[30]; vector<int> b; int main() {sort(a, a + 30);sort(b.begin(), b.end()); }

Reverse

#include <algorithm> using namespace std; int a[30]; vector<int> b; int main() {reverse(a, a + 30);reverse(b.begin(), b.end()); }

unique
去重（必須要是排序好了的數(shù)列）

fill（把頭到尾覆蓋某個數(shù)）

int main {sort(a,a+10);for(int i=0;i<10;i++)cout<<a[i]<<" ";cout<<endl;fill(unique(a,a+10),a+10,0)for(int i=0;i<10;i++)cout<<a[i]<<" "; }

?

?

Next Permutation

int a[4] = {1, 2, 3, 4};
int main() {do{for(int i=0;i<4;++i)cout<<a[i]<<" ";cout<<endl;}while(next_permutatiom(a,a+4)); }

?

尋找全排列

要求數(shù)組中元素可以比較。

均攤復雜度 O(1)，單次運算交換次數(shù)不超過distance(Ai; Ai+1)/2， Ai; Ai+1 分別為第 i, i + 1 個排列，但是如果列出全排列的話就是O(n!)

?

Nth Element

#include <iostream> #include <vector> #include <algorithm> #include <functional> int main() {std::vector<int> v{5, 6, 4, 3, 2, 6, 7, 9, 3};std::nth_element(v.begin(), v.begin() + v.size()/2, v.end());std::cout << "The median is " << v[v.size()/2] << '\n';std::nth_element(v.begin(), v.begin()+1, v.end(), std::greater<int>());std::cout << "The second largest element is " << v[1] << '\n'; }

復雜度O(n)

只讓中間那個放在正確的位置，比他大的在前面，比他小的在后面

?

Random Shuffle

#include <random> #include <algorithm> #include <iterator> #include <iostream> int main() {std::vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};std::shuffle(v.begin(), v.end(), g); }

?

轉載于:https://www.cnblogs.com/lcezych/p/10804301.html

總結

以上是生活随笔為你收集整理的Day 6 上午的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。