C++中map和set的簡介及使用詳解
關(guān)聯(lián)式容器
關(guān)聯(lián)式容器包括序列式容器和關(guān)聯(lián)式容器
序列式容器： 底層為線性序列的數(shù)據(jù)結(jié)構(gòu)，里面存儲的是元素本身，包含vector、list、deque、forward_list(C++11)等。
關(guān)聯(lián)式容器： 里面存儲的是<key, value>結(jié)構(gòu)的鍵值對，在數(shù)據(jù)檢索時比序列式容器效率更高，包含set、map、unordered_set、unordered_map等。
注意： stack、queue和priority_queue屬于容器適配器
鍵值對
用來表示具有一一對應關(guān)系的一種結(jié)構(gòu)，該結(jié)構(gòu)中一般只包含兩個成員變量key和value，key代表鍵值，value表示與key對應的信息。
現(xiàn)在要建立一個英漢互譯的字典，那該字典中必然有英文單詞與其對應的中文含義，而且，英文單詞與其中文含義是一一對應的關(guān)系，即通過該應該單詞，在詞典中就可以找到與其對應的中文含義。
SGI-STL中關(guān)于鍵值對的定義：
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)
{}
};
set
set的介紹
- set是按照一定次序存儲元素的容器。
- 在set中，元素的value必須是唯一的。set中的元素不能在容器中修改(元素總是const)，但是可以從容器中插入或刪除它們。
- 在內(nèi)部，set中的元素總是按照其內(nèi)部比較對象(類型比較)所指示的特定嚴格弱排序準則進行排序。
- set容器通過key訪問單個元素的速度通常比unordered_set容器慢，但它們允許根據(jù)順序?qū)ψ蛹M行直接迭代。
- set在底層是用二叉搜索樹(紅黑樹)實現(xiàn)的。
注意：
- 與map/multimap不同，map/multimap中存儲的是真正的鍵值對<key, value>，set中只放value，但在底層實際存放的是由<value, value>構(gòu)成的鍵值對。
- set中插入元素時，只需要插入value即可，不需要構(gòu)造鍵值對。
- set中的元素不可以重復(因此可以使用set進行去重)。
- 使用set的迭代器遍歷set中的元素，可以得到有序序列
- set中的元素默認按照小于來比較
- set中查找某個元素，時間復雜度為：logN
set的使用
set的模板參數(shù)列表
T: set中存放元素的類型，實際在底層存儲<value, value>的鍵值對。
Compare：set中元素默認按照小于來比較
Alloc：set中元素空間的管理方式，使用STL提供的空間配置器管理
set的構(gòu)造
| 函數(shù)聲明 | 功能介紹 |
|---|---|
| set (const Compare& comp = Compare(), const Allocator& =Allocator()); | 構(gòu)造空的set |
| set (InputIterator first, InputIterator last, const Compare& comp = Compare(), const Allocator& = Allocator() ); | 用[first, last)區(qū)間中的元素構(gòu)造set |
| set ( const set<Key,Compare,Allocator>& x); | set的拷貝構(gòu)造 |
set中常用的成員函數(shù)
| 成員函數(shù) | 功能 |
|---|---|
| insert | 插入元素 |
| erase | 刪除元素 |
| find | 查找元素 |
| size | 獲取容器中元素的個數(shù) |
| clear | 清空容器 |
| empty | 判空 |
| swap | 交換兩個容器中的數(shù)據(jù) |
| count | 獲取某個元素的個數(shù) |
使用示例
int main()
{
set<int> s;
//插入元素(自動去重）
s.insert(1);
s.insert(4);
s.insert(3);
s.insert(3);
s.insert(2);
s.insert(2);
s.insert(3);
//遍歷容器
for (auto e : s)
{
cout << e << " ";
}
cout << endl;
//查找元素
set<int>::iterator pos = s.find(3);
//刪除元素
s.erase(pos);// 刪除元素3
s.erase(4);
//容器大小
cout << s.size() << endl;
//清空容器
s.clear();
//容器判空
cout << s.empty() << endl;
//交換兩個容器的數(shù)據(jù)
set<int> tmp{ 10, 20, 30, 40 };
s.swap(tmp);
//容器中值為2的元素個數(shù)
cout << s.count(2) << endl;
cout << endl;
}
運行結(jié)果如下
set中迭代器相關(guān)函數(shù)
| 成員函數(shù) | 功能 |
|---|---|
| begin | 返回set中起始位置元素的迭代器 |
| end | 返回set中最后一個元素后面的迭代器 |
| rbegin | 返回set第一個元素的反向迭代器 |
| rend | 返回set最后一個元素下一個位置的反向迭代器 |
使用示例
void test_set()
{
set<int> s;
//插入元素
s.insert(1);
s.insert(4);
s.insert(3);
s.insert(3);
s.insert(2);
s.insert(2);
s.insert(3);
//遍歷容器（正向迭代器）
set<int>::iterator it = s.begin();
while (it != s.end())
{
cout << *it << " ";
it++;
}
cout << endl;
//反向迭代器
set<int>::reverse_iterator rit = s.rbegin();
while (rit != s.rend())
{
cout << *rit << " ";
rit++;
}
cout << endl;
}
運行結(jié)果如下
multiset
multiset和set的區(qū)別是multiset允許數(shù)據(jù)冗余，即multiset中允許存在數(shù)據(jù)相同的元素，而set不能。
void test_set()
{
set<int> s;
s.insert(1);
s.insert(3);
s.insert(4);
s.insert(2);
s.insert(2);
for (auto e : s)
{
cout << e << " ";
}
cout << endl;
multiset<int> ms;
ms.insert(1);
ms.insert(3);
ms.insert(4);
ms.insert(2);
ms.insert(2);
for (auto e : ms)
{
cout << e << " ";
}
cout << endl;
}
運行結(jié)果如下
兩個容器中成員函數(shù)find意義也有區(qū)別：
set中的find是返回值為val的迭代器，而multiset中的find是返回第一個值為val的迭代器。
map
map的介紹
- map是關(guān)聯(lián)容器，它按照特定的次序(按照key來比較)存儲由鍵值key和值value組合而成的元素。
- 在map中，鍵值key通常用于排序和惟一地標識元素，而值value中存儲與此鍵值key關(guān)聯(lián)的內(nèi)容。鍵值key和值value的類型可能不同，并且在map的內(nèi)部，key與value通過成員類型value_type綁定在一起，為其取別名稱為pair。
- 在內(nèi)部，map中的元素總是按照鍵值key進行比較排序的。
- map中通過鍵值訪問單個元素的速度通常比unordered_map容器慢，但map允許根據(jù)順序?qū)υ剡M行直接迭代(即對map中的元素進行迭代時，可以得到一個有序的序列)。
- map支持下標訪問符，即在[]中放入key，就可以找到與key對應的value。
- map通常被實現(xiàn)為二叉搜索樹(更準確的說：平衡二叉搜索樹(紅黑樹))。
map的使用
map的模板參數(shù)說明
key: 鍵值對中key的類型
T： 鍵值對中value的類型
Compare: 比較器的類型，map中的元素是按照key來比較的，缺省情況下按照小于來比較，一般情況下(內(nèi)置類型元素)該參數(shù)不需要傳遞，如果無法比較時(自定義類型)，需要用戶自己顯式傳遞比較規(guī)則(一般情況下按照函數(shù)指針或者仿函數(shù)來傳遞)
Alloc：通過空間配置器來申請底層空間，不需要用戶傳遞，除非用戶不想使用標準庫提供的空間配置器
map構(gòu)造
void test_map()
{
map<int, double> m1; //構(gòu)造一個key為int類型，value為double類型的空容器
map<int, double> m2(m1); //拷貝構(gòu)造
map<int, double> m3(m2.begin(), m2.end()); //利用迭代器拷貝構(gòu)造
map<int, double, greater<int>> m4; //按int降序排序
}
map的插入
插入函數(shù)原型
pair<iterator,bool> insert (const value_type& val);
這里的value_type是pair的重命名
typedef pair<const Key, T> value_type;
方式一： 構(gòu)造匿名對象插入。
int main()
{
map<int, string> m;
// 構(gòu)造一個匿名對象插入
m.insert(pair<int, string>(2, "two"));
m.insert(pair<int, string>(1, "one"));
m.insert(pair<int, string>(3, "three"));
for (auto e : m)
{
cout << e.first << "-" << e.second << endl;
}
cout << endl;
return 0;
}
運行結(jié)果如下
方式二： 調(diào)用make_pair函數(shù)模板
make_pair函數(shù)模板如下
template <class T1, class T2>
pair<T1, T2> make_pair(T1 x, T2 y)
{
return (pair<T1, T2>(x, y));
}
make_pair可以根據(jù)傳入?yún)?shù)類型自行推導模板類型
上述代碼可改為
int main()
{
map<int, string> m;
// 構(gòu)造一個匿名對象插入
m.insert(make_pair(2, "two"));
m.insert(make_pair(1, "one"));
m.insert(make_pair(3, "three"));
for (auto e : m)
{
cout << e.first << "-" << e.second << endl;
}
cout << endl;
return 0;
}
運行結(jié)果相同
insert的返回值也是一個pair對象，pair中第一個成員類型是插入的map的迭代器類型，第二個成員類型是bool類型
bool類型的作用如下
- 若待插入元素的鍵值key在map當中不存在，則insert函數(shù)插入成功，并返回插入后元素的迭代器和true。
- 若待插入元素的鍵值key在map當中已經(jīng)存在，則insert函數(shù)插入失敗，并返回map當中鍵值為key的元素的迭代器和false。
map的[ ]運算符重載
函數(shù)原型：
mapped_type& operator[] (const key_type& k);
函數(shù)的返回值如下：
(*((this->insert(make_pair(k, mapped_type()))).first)).second
乍一看很是復雜，把括號分清后便明朗許多
原代碼可分解為
mapped_type& operator[] (const key_type& k)
{
//調(diào)用insert函數(shù)插入鍵值對
pair<iterator, bool> ret = insert(make_pair(k, mapped_type()));
//拿出從insert函數(shù)獲返回的迭代器
iterator it = ret.first;
//返回該迭代器位置元素的值value
return it->second;
}
應用場景：
void test_map1()
{
string str[] = { "sort", "sort", "tree", "insert", "sort", "tree", "sort", "test", "sort" };
map<string, int> countMap;
for (auto& e : str)
{
countMap[e]++;
}
for (auto& e : countMap)
{
cout << e.first << "-" << e.second << endl;
}
cout << endl;
}
運行結(jié)果
map其他常用成員函數(shù)
| 成員函數(shù) | 功能 |
|---|---|
| void erase ( iterator position ) | 利用迭代器刪除元素 |
| size_type erase ( const key_type& x ) | 刪除鍵值為x的元素 |
| void erase ( iterator first,iterator last ) | 刪除[first, last)區(qū)間中的元素 |
| iterator find ( const key_type& x) | 找到返回該元素的位置的迭代器，否則返回end |
| size | 獲取容器中元素的個數(shù) |
| empty | 判空 |
| clear | 清空容器 |
| swap | 交換兩個容器中的數(shù)據(jù) |
| count | 獲取某個元素的個數(shù) |
使用示例
int main()
{
map<int, string> m;
m.insert(make_pair(2, "two"));
m.insert(make_pair(1, "one"));
m.insert(make_pair(3, "three"));
m.insert(make_pair(4, "four"));
//根據(jù)key值進行刪除
m.erase(3);
//根據(jù)迭代器進行刪除
map<int, string>::iterator pos = m.find(4);
if (pos != m.end())
{
m.erase(pos);
}
// 獲取元素為2的迭代器
pos = m.find(2);
if (pos != m.end())
{
cout << pos->first<<"-"<<pos->second << endl;
}
//獲取容器中元素的個數(shù)
cout << m.size() << endl;
//容器中key值為2的元素個數(shù)
cout << m.count(2) << endl;
//清空容器
m.clear();
//容器判空
cout << m.empty() << endl;
//交換兩個容器中的數(shù)據(jù)
map<int, string> tmp;
m.swap(tmp);
return 0;
}
map的迭代器相關(guān)函數(shù)
| 成員函數(shù) | 功能 |
|---|---|
| begin | 返回map中起始位置元素的迭代器 |
| end | 返回map中最后一個元素后面的迭代器 |
| rbegin | 返回map第一個元素的反向迭代器 |
| rend | 返回map最后一個元素下一個位置的反向迭代器 |
操作演示
int main()
{
map<int, string> m;
m.insert(make_pair(2, "two"));
m.insert(make_pair(1, "one"));
m.insert(make_pair(3, "three"));
// 正向迭代器遍歷
map<int, string>::iterator it = m.begin();
while (it != m.end())
{
cout << it->first << "-" << it->second << endl;
it++;
}
cout << endl;
// 反向迭代器遍歷
map<int, string>::reverse_iterator it2 = m.rbegin();
while (it2 != m.rend())
{
cout << it2->first << "-" << it2->second << endl;
it2++;
}
cout << endl;
return 0;
}
multiset
multimap容器和map容器的區(qū)別與multiset容器和set容器的區(qū)別一樣，multimap允許鍵值冗余，即multimap容器當中存儲的元素是可以重復的。
int main()
{
multimap<int, string> mt;
//插入元素（允許重復）
mt.insert(make_pair(2, "two"));
mt.insert(make_pair(2, "two"));
mt.insert(make_pair(1, "one"));
mt.insert(make_pair(3, "three"));
for (auto e : mt)
{
cout << e.first << "-" << e.second << endl;
}
cout << endl;
return 0;
}
注意： 由于multimap容器允許鍵值冗余，調(diào)用[ ]運算符重載函數(shù)時，應該返回鍵值為key的哪一個元素的value的引用存在歧義，因此在multimap容器不支持[ ]運算符重載函數(shù)。
到此這篇關(guān)于C++中map和set的簡介及使用詳解的文章就介紹到這了,更多相關(guān)C++ map和set內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
本文主要介紹了C++中將string類型轉(zhuǎn)化為int類型的方法。具有很好的參考價值，下面跟著小編一起來看下吧2017-02-02
C++中關(guān)于多態(tài)實現(xiàn)和使用方法
這篇文章主要介紹了C++中關(guān)于多態(tài)實現(xiàn)和使用方法，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-07-07
這篇文章主要介紹了C語言之實現(xiàn)單鏈表指定結(jié)點的插入方式，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-07-07
這篇文章主要介紹了C語言如何計算兩個數(shù)的最小公倍數(shù)，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-11-11
這篇文章主要為大家詳細介紹了C語言鏈表實現(xiàn)銷售管理系統(tǒng)，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-02-02
這篇文章主要為大家詳細介紹了QT實現(xiàn)簡單時鐘效果，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-05-05
本篇文章是對生成隨機數(shù)rand函數(shù)的用法進行了詳細的分析介紹，需要的朋友參考下2013-05-05
通過不同的方法，實現(xiàn)對所輸入字符串的反轉(zhuǎn)，有需要的朋友可以參考一下2013-09-09
這篇文章主要介紹了C++循環(huán)隊列實現(xiàn)模型,較為詳細的分析了循環(huán)隊列算法的原理與實現(xiàn)方法,具有一定的參考借鑒價值,需要的朋友可以參考下2014-12-12
這篇文章主要為大家詳細介紹了C++學習心得之掃雷游戲，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-03-03