set

什么是set

set是STL中一個(gè)底層為二叉搜索樹來實(shí)現(xiàn)的容器

• 若要使用set需要包含頭文件 #include<set>
• set中的元素具有唯一性(因此可以用set去重)
• 若用set的迭代器遍歷,默認(rèn)得到升序序列
• set查找某個(gè)元素默認(rèn)復(fù)雜度為$lo{g}_{2}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"] = "插入";

1. 因?yàn)閙ap中存儲(chǔ)的是鍵值對(duì)元素,因此每次插入的時(shí)候應(yīng)該使用pair函數(shù)
   m.insert(pair<string, string>("right", "右邊"));
   但是這種方法有點(diǎn)麻煩,因此引用了make_pair函數(shù)

2. make_pair是一個(gè)仿函數(shù),定義如下:
   返回值還是一個(gè)pair鍵值對(duì):
   
   因此當(dāng)map插入值的時(shí)候可以使用以下方法:
   m.insert(make_pair("left", "左邊"));
   這種方式是最常用的

3. 因?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é)果: