set

什么是set

set是STL中一個底層為二叉搜索樹來實現的容器

• 若要使用set需要包含頭文件 #include<set>
• set中的元素具有唯一性(因此可以用set去重)
• 若用set的迭代器遍歷,默認得到升序序列
• set查找某個元素默認復雜度為$lo{g}_{2}N$
• set中的元素不能被修改

set的使用

set<int> s; //默認升序
set<int , greater<int>>  us; //降序
int i;s.insert(i);  //插入值 若成功,則返回i所在迭代器,若失敗,則返回已存在的i的迭代器s.erase(i);  //刪除某個值 并 返回所刪除的個數s.clear();  //清空ss.begin();  //begin迭代器s.end();  //end()迭代器s.find(i);  //查找i,若找到了,則返回i的迭代器,若沒找到,返回尾部迭代器 s.end();s.empty();  //返回s是否為空s.size();  //返回s內元素個數

用例:

#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);  //插入第二個1//這里用了范圍for ,因為右迭代器,因此自動遍歷for (auto& e : s){cout << e << " ";}cout << endl;   //遍歷結果: 1 2 3 4 5//刪除3再遍歷  set會自動調整s.erase(3);for (auto& e : s){cout << e << " ";}cout << endl;   //遍歷結果: 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;  //遍歷結果為降序: 5 4 3 2 1return 0;
}

關聯式容器

之前學習的容器中,基本都是單元素存儲,比如：vector、list、deque、等，這些容器統稱為序列式容器，因為其底層為線性序列的數據結構，里面存儲的是元素本身。即 K 模型 的容器
關聯式容器也是用來存儲數據的，與序列式容器不同的是，其里面存儲的是<key, value>結構的鍵值對，在數據檢索時比序列式容器效率更高
例如上面的set也是關聯式容器,set中只放value，但在底層實際存放的是由<value, value>構成的鍵值對

鍵值對

用來表示具有一一對應關系的一種結構，該結構中一般只包含兩個成員變量key和value，key代表鍵值，value表示與key對應的信息.即 KV 模型 的容器

STL中鍵值對的定義:

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

一種存儲鍵值對,底層為二叉搜索樹的數據結構

• 需要包含頭文件#include<map>
• map是關聯容器，它按照特定的次序(按照key來比較)存儲由鍵值key和值value組合而成的元素。即 KV 模型
• 在map中，鍵值key通常用于排序和惟一地標識元素，而值value中存儲與此鍵值key關聯的內容。鍵值key和值value的類型可能不同，并且在map的內部，key與value通過成員類型value_type綁定在一起，為其取別名稱為pair:
  typedef pair<const key, T> value_type 其中,key為const,因此是不能修改的,而T是可以修改的
• map中的元素按照鍵值key進行比較排序。
• map支持下標訪問，即在[]中放入key，就可以找到與key對應的value。
• map底層實際上就是二叉搜索樹(更準確的說：平衡二叉搜索樹(紅黑樹))。

map的使用

先創建一個map對象:

map<string, string> m;

map的插入方式

幾種常見的map插入方式:

    m.insert(make_pair("left", "左邊"));m.insert(pair<string, string>("right", "右邊"));m["insert"] = "插入";

1. 因為map中存儲的是鍵值對元素,因此每次插入的時候應該使用pair函數
   m.insert(pair<string, string>("right", "右邊"));
   但是這種方法有點麻煩,因此引用了make_pair函數

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

3. 因為map重載了[],因此可以直接使用[]來進行插入
   map中operator[]的原理是：

• 用<key, T()>構造一個鍵值對，然后調用insert()函數將該鍵值對插入到map中
• 如果key已經存在，插入失敗，insert函數返回該key所在位置的迭代器
• 如果key不存在，插入成功，insert函數返回新插入元素所在位置的迭代器
• operator[]函數最后將insert返回值鍵值對中的value返回
  m["insert"] = "插入";
  其中,[]內為 K 值, 返回的V被 = 后的內容賦值;

常用功能

    m.insert(make_pair("erase", "刪除"));  //插入值 若已存在,則返回該值的迭代器m.erase("erase");  //刪除值m.clear();  //清除mapm.size();  //返回 K 元素的數量m.begin();  //begin迭代器m.end();  //end迭代器m.find("erase");  //查找 K 值,若找到了,則返回迭代器, 若沒找到,則返回迭代器m.end()m["find"];  //插入K ,若有m.swap(m2);  //交換兩個map對象 其中m2 為另一個與m對象同類型的對象

map[] 的靈活使用

map因為重載了[] ,因此變得非常靈活,例如,統計下列數組中相同的值出現的次數:

#include<iostream>
#include<string>
#include<map>using namespace std;int main()
{string arr[] = { "西瓜","西瓜", "西瓜", "西瓜","蘋果","蘋果","蘋果","蘋果","蘋果","蘋果","香蕉","香蕉","香蕉","香蕉","草莓","草莓","草莓","草莓","草莓","草莓","草莓", };map<string, int> m;for (auto& e : arr){m[e]++; //這里直接利用[]對m進行插入,并通過++ 對V值進行控制}for (auto& e : m){cout << e.first << ":" << e.second << endl;}return 0;
}

輸出結果: