有用node.js做的網(wǎng)站嗎哪家培訓(xùn)機(jī)構(gòu)學(xué)校好
set和map
- set
- 什么是set
- set的使用
- 關(guān)聯(lián)式容器
- 鍵值對(duì)
- map
- 什么是map
- map的使用
- map的插入方式
- 常用功能
- map[] 的靈活使用
set
什么是set
set是STL中一個(gè)底層為二叉搜索樹來實(shí)現(xiàn)的容器
- 若要使用set需要包含頭文件
#include<set>
- set中的元素具有唯一性(因此可以用set去重)
- 若用set的迭代器遍歷,默認(rèn)得到升序序列
- set查找某個(gè)元素默認(rèn)復(fù)雜度為 l o g 2 N log_2 N log2?N
- set中的元素不能被修改
set的使用
set<int> s; //默認(rèn)升序
set<int , greater<int>> us; //降序
int i;s.insert(i); //插入值 若成功,則返回i所在迭代器,若失敗,則返回已存在的i的迭代器s.erase(i); //刪除某個(gè)值 并 返回所刪除的個(gè)數(shù)s.clear(); //清空ss.begin(); //begin迭代器s.end(); //end()迭代器s.find(i); //查找i,若找到了,則返回i的迭代器,若沒找到,返回尾部迭代器 s.end();s.empty(); //返回s是否為空s.size(); //返回s內(nèi)元素個(gè)數(shù)
用例:
#include<iostream>
#include<set>using namespace std;int main()
{set<int> s;s.insert(1);s.insert(3);s.insert(2);s.insert(4);s.insert(5);s.insert(1); //插入第二個(gè)1//這里用了范圍for ,因?yàn)橛业?因此自動(dòng)遍歷for (auto& e : s){cout << e << " ";}cout << endl; //遍歷結(jié)果: 1 2 3 4 5//刪除3再遍歷 set會(huì)自動(dòng)調(diào)整s.erase(3);for (auto& e : s){cout << e << " ";}cout << endl; //遍歷結(jié)果: 1 2 4 5//清理ss.clear();for (auto& e : s){cout << e << " ";}cout << endl; //空值set<int, greater<int>> us; //降序set//插入:us.insert(1);us.insert(2);us.insert(3);us.insert(4);us.insert(5);//遍歷for (auto& e : us){cout << e << " ";}cout << endl; //遍歷結(jié)果為降序: 5 4 3 2 1return 0;
}
關(guān)聯(lián)式容器
之前學(xué)習(xí)的容器中,基本都是單元素存儲(chǔ),比如:vector、list、deque、等,這些容器統(tǒng)稱為序列式容器,因?yàn)槠涞讓訛榫€性序列的數(shù)據(jù)結(jié)構(gòu),里面存儲(chǔ)的是元素本身。即 K 模型 的容器
關(guān)聯(lián)式容器也是用來存儲(chǔ)數(shù)據(jù)的,與序列式容器不同的是,其里面存儲(chǔ)的是<key, value>結(jié)構(gòu)的鍵值對(duì),在數(shù)據(jù)檢索時(shí)比序列式容器效率更高
例如上面的set也是關(guān)聯(lián)式容器,set中只放value,但在底層實(shí)際存放的是由<value, value>構(gòu)成的鍵值對(duì)
鍵值對(duì)
用來表示具有一一對(duì)應(yīng)關(guān)系的一種結(jié)構(gòu),該結(jié)構(gòu)中一般只包含兩個(gè)成員變量key和value,key代表鍵值,value表示與key對(duì)應(yīng)的信息.即 KV 模型 的容器
STL中鍵值對(duì)的定義:
template <class T1, class T2>
struct pair
{
typedef T1 first_type;
typedef T2 second_type;
T1 first;
T2 second;
pair(): first(T1()), second(T2())
{}
pair(const T1& a, const T2& b): first(a), second(b)
{}
};
map
什么是map
一種存儲(chǔ)鍵值對(duì),底層為二叉搜索樹的數(shù)據(jù)結(jié)構(gòu)
- 需要包含頭文件
#include<map>
- map是關(guān)聯(lián)容器,它按照特定的次序(按照key來比較)存儲(chǔ)由鍵值key和值value組合而成的元素。
即 KV 模型
- 在map中,鍵值key通常用于排序和惟一地標(biāo)識(shí)元素,而值value中存儲(chǔ)與此鍵值key關(guān)聯(lián)的內(nèi)容。鍵值key和值value的類型可能不同,并且在map的內(nèi)部,key與value通過成員類型value_type綁定在一起,為其取別名稱為pair:
typedef pair<const key, T> value_type
其中,key為const,因此是不能修改的,而T是可以修改的 - map中的元素
按照鍵值key進(jìn)行比較排序
。 - map支持下標(biāo)訪問,即在[]中放入key,就可以找到與key對(duì)應(yīng)的value。
- map底層實(shí)際上就是二叉搜索樹(更準(zhǔn)確的說:平衡二叉搜索樹(紅黑樹))。
map的使用
先創(chuàng)建一個(gè)map對(duì)象:
map<string, string> m;
map的插入方式
幾種常見的map插入方式:
m.insert(make_pair("left", "左邊"));m.insert(pair<string, string>("right", "右邊"));m["insert"] = "插入";
-
因?yàn)閙ap中存儲(chǔ)的是鍵值對(duì)元素,因此每次插入的時(shí)候應(yīng)該使用pair函數(shù)
m.insert(pair<string, string>("right", "右邊"));
但是這種方法有點(diǎn)麻煩,因此引用了make_pair函數(shù) -
make_pair是一個(gè)仿函數(shù),定義如下:
返回值還是一個(gè)pair鍵值對(duì):
因此當(dāng)map插入值的時(shí)候可以使用以下方法:
m.insert(make_pair("left", "左邊"));
這種方式是最常用的 -
因?yàn)閙ap重載了[],因此可以直接使用[]來進(jìn)行插入
map中operator[]的原理是:
- 用<key, T()>構(gòu)造一個(gè)鍵值對(duì),然后調(diào)用insert()函數(shù)將該鍵值對(duì)插入到map中
- 如果key已經(jīng)存在,插入失敗,insert函數(shù)返回該key所在位置的迭代器
- 如果key不存在,插入成功,insert函數(shù)返回新插入元素所在位置的迭代器
- operator[]函數(shù)最后將insert返回值鍵值對(duì)中的value返回
m["insert"] = "插入";
其中,[]內(nèi)為 K 值, 返回的V被 = 后的內(nèi)容賦值;
常用功能
m.insert(make_pair("erase", "刪除")); //插入值 若已存在,則返回該值的迭代器m.erase("erase"); //刪除值m.clear(); //清除mapm.size(); //返回 K 元素的數(shù)量m.begin(); //begin迭代器m.end(); //end迭代器m.find("erase"); //查找 K 值,若找到了,則返回迭代器, 若沒找到,則返回迭代器m.end()m["find"]; //插入K ,若有m.swap(m2); //交換兩個(gè)map對(duì)象 其中m2 為另一個(gè)與m對(duì)象同類型的對(duì)象
map[] 的靈活使用
map因?yàn)橹剌d了[] ,因此變得非常靈活,例如,統(tǒng)計(jì)下列數(shù)組中相同的值出現(xiàn)的次數(shù):
#include<iostream>
#include<string>
#include<map>using namespace std;int main()
{string arr[] = { "西瓜","西瓜", "西瓜", "西瓜","蘋果","蘋果","蘋果","蘋果","蘋果","蘋果","香蕉","香蕉","香蕉","香蕉","草莓","草莓","草莓","草莓","草莓","草莓","草莓", };map<string, int> m;for (auto& e : arr){m[e]++; //這里直接利用[]對(duì)m進(jìn)行插入,并通過++ 對(duì)V值進(jìn)行控制}for (auto& e : m){cout << e.first << ":" << e.second << endl;}return 0;
}
輸出結(jié)果: