C++中map和set的使用及示例
一、set
1.1 set特點(diǎn)介紹
set的介紹C++中的set是一個STL容器，它是一個自動排序的集合（即將數(shù)據(jù)存入set，我們通過迭代器順序訪問出來時，數(shù)據(jù)是有序的），內(nèi)部使用紅黑樹（后面會講解）來實(shí)現(xiàn)。它的特點(diǎn)是不允許重復(fù)元素，而且插入元素時自動進(jìn)行排序。
set容器的特點(diǎn)
- 存入set后數(shù)據(jù)有序：
set是按照一定次序存儲元素的容器，迭代器迭代出來的數(shù)據(jù)是有序的。 - 數(shù)據(jù)唯一（可以用于去重）：每個
value必須是唯一的。set中的元素不能在容器中修改(元素總是const)，但是可以從容器中插入或刪除它們。 set在底層是用二叉搜索樹(紅黑樹)實(shí)現(xiàn)的。
注意：set中查找某個元素，時間復(fù)雜度為： log2?n，因?yàn)榈讓邮羌t黑樹。
1.2 set使用
1.21 構(gòu)造函數(shù)
（來源于：官方文檔）
測試構(gòu)造：
//測試構(gòu)造
void test_Construct() {
set<int> s1;//普通構(gòu)造
//迭代器構(gòu)造
//數(shù)組
int arr[] = { 2,2,1,1,5,5,5,1,7,9,8,10 };
set<int> s2(arr,arr+sizeof(arr)/sizeof(int)); //默認(rèn)就是升序
cout << "s2: ";
for (auto it : s2) {
cout << it << " ";
}
cout << endl;
//vector
vector<int> v = { 2,2,1,1,5,5,5,1,7,9,8,10 };
set<int> s3(v.begin(), v.end()); //默認(rèn)就是升序
cout << "s3: ";
for (auto it : s3) {
cout << it << " ";
}
cout << endl;
//拷貝構(gòu)造
set<int> s4(s3);
cout << "s4: ";
for (auto it : s3) {
cout << it << " ";
}
cout << endl;
}
運(yùn)行結(jié)果：
s2: 1 2 5 7 8 9 10
s3: 1 2 5 7 8 9 10
s4: 1 2 5 7 8 9 10
1.22 升/降序
void test_cmp() {
//set 降序
set<int, less<int>> s1;
s1.insert(3);
s1.insert(5);
s1.insert(2);
s1.insert(6);
s1.insert(7);
s1.insert(10);
s1.insert(9);
s1.insert(1);
s1.insert(4);
s1.insert(8);
cout << "升序：s1: ";
for (auto it : s1) {
cout << it << " ";
}
cout << endl;
//set升序
set<int, greater<int>> s2;
s2.insert({3,5,2,6,7,10,9,1,4,8});
cout << "降序：s2: ";
for (auto it : s2) {
cout << it << " ";
}
cout << endl;
}
運(yùn)行結(jié)果：
升序：s1: 1 2 3 4 5 6 7 8 9 10
降序：s2: 10 9 8 7 6 5 4 3 2 1
1.23 其他接口
（1） 容量（capacity）相關(guān)：
| 接口名 | 介紹 |
|---|---|
| empty( ) | 檢測set是否為空，空返回true，否則返回false |
| size（） | 獲取set中有效數(shù)據(jù)的個數(shù) |
（2）Modifiers（修改）
| 接口名 | 解釋 |
|---|---|
| insert | 向set中插入數(shù)據(jù)，可以是迭代器區(qū)間們也可以是單個的值 |
| erase | 刪除指定位置的數(shù)據(jù)（可以提供迭代器，也可以是元素值） |
| void swap (set& x); | 交換兩個set |
| void clear(); | 清除set中的數(shù)據(jù) |
（3）查找
| 接口名 | 解釋 |
|---|---|
| iterator find (const value_type& val) const; | 查找元素 ，返回該元素的迭代器 |
| size_type count (const value_type& val) const; | 返回目標(biāo)元素在set中出現(xiàn)的次數(shù)（由于set是不予訊重復(fù)元素的，所以這個接口意義不大） |
void test() {
set<int, greater<int>> s1;
s1.insert({ 3,5,2,6,7,10,9,1,4,8 });
cout << "有效數(shù)據(jù)的個數(shù)： " << s1.size() << endl;
cout << "是否為空容器： " << s1.empty() << endl;
//在set中意義不大的函數(shù)
cout << "容器中元素3出現(xiàn)了： " << s1.count(3) << endl;
set<int>:: iterator it = s1.find(2); //找到則返回這個元素的迭代器，沒找到，則返回end（）
cout <<"find(2): "<< * it << endl;
set<int, greater<int>> s2;
s2.insert({ 1,5,8 });
cout << "交換前："<<endl;
cout << "s1: ";
for (auto it : s1) {
cout << it << " ";
}
cout << endl;
cout << "s2: ";
for (auto it : s2) {
cout << it << " ";
}
cout << endl;
swap(s1, s2);
cout << "交換后：" << endl;
cout << "s1: ";
for (auto it : s1) {
cout << it << " ";
}
cout << endl;
cout << "s2: ";
for (auto it : s2) {
cout << it << " ";
}
cout << endl;
s1.clear();
cout << "清除：s1: ";
for (auto it : s1) {
cout << it << " ";
}
cout << endl;
}
運(yùn)行結(jié)果：
有效數(shù)據(jù)的個數(shù)： 10
是否為空容器： 0
容器中元素3出現(xiàn)了： 1
find(2): 2
交換前：
s1: 10 9 8 7 6 5 4 3 2 1
s2: 8 5 1
交換后：
s1: 8 5 1
s2: 10 9 8 7 6 5 4 3 2 1
清除：s1:
二、map
2.1 map的特點(diǎn)介紹
map是一個關(guān)聯(lián)容器，它提供了一種存儲鍵值對的方法。它是按照鍵（key）進(jìn)行排序和存儲的，鍵必須是唯一的，而值（value）可以重復(fù)。map通常使用紅黑樹實(shí)現(xiàn)，所以它的查找、插入和刪除操作的時間復(fù)雜度都是O(log n)。
那么何為鍵值對？
鍵值對是一種常用的數(shù)據(jù)存儲結(jié)構(gòu)，由“鍵”和“值”兩部分組成。其中，“鍵”是唯一的，用于標(biāo)識數(shù)據(jù)，而“值”則是與鍵相關(guān)聯(lián)的數(shù)據(jù)。
其實(shí)很簡單，例如： {“apple”, “蘋果”}
下面是pair大概實(shí)現(xiàn)：
template <typename T1, typename T2>
struct pair {
T1 first; //鍵
T2 second; //值
pair() : first(), second() {}
pair(const T1& x, const T2& y): first(x), second(y) {}
template <typename U1, typename U2>
pair(const pair<U1, U2>& p) : first(p.first), second(p.second) {}
pair& operator=(const pair& rhs) {
if (this != &rhs) {
first = rhs.first;
second = rhs.second;
}
return *this;
}
};
2.2 map的使用
map和set的用法基本相同，只不過一個是鍵值對，一個是單個的值。
這里對于map就不過多介紹了。
?構(gòu)造函數(shù)
void test_map() {
// 構(gòu)造空的map
map<string, int> map1;
cout << "map1:" << endl;
for (auto it : map1) {
cout << it.first << it.second << endl;
}
cout << endl;
// 使用初始化列表構(gòu)造
map<string, string> map2{
{"apple", "蘋果"},
{"banana", "香蕉"},
{"orange", "橘子"}
};
cout << "map2:" << endl;
for (auto it : map2) {
cout << it.first << it.second << endl;
}
cout << endl;
// 構(gòu)造map并插入元素
map<string, int> map3;
map3.insert(pair<string, int>("panda", 1));
map3.insert(make_pair("", 2));
map3.insert(map<string, int>::value_type("monkey", 3));
cout << "map3:" << endl;
for (auto it : map3) {
cout << it.first << it.second << endl;
}
cout << endl;
cout << "空格對應(yīng)的值:" << map3[""];
}
運(yùn)行結(jié)果：
map1:
map2:
apple蘋果
banana香蕉
orange橘子
map3:
2
monkey3
panda1
空格對應(yīng)的值:2
??[ ]的作用
在 C++ 中，map 中的 [] 運(yùn)算符可以用于訪問和修改 map 中的元素，其作用如下：
- 若鍵值存在，返回對應(yīng)的值；
- 若鍵值不存在，會與這個不存在的key和默認(rèn)值構(gòu)成一個鍵值對，自動插入默，并返回該默認(rèn)值的引用。
void test() {
std::map<std::string, int> my_map;
my_map["apple"] = 2;
my_map["banana"] = 3;
cout << "my_map 變化前" << endl;
for (auto it : my_map) {
cout << it.first << " : " << it.second << endl;
}
cout << endl;
std::cout << my_map["apple"] << std::endl; // 輸出 2
std::cout << my_map["pear"] << std::endl; // 輸出默認(rèn)值 0
cout << "my_map 變化后" << endl;
for (auto it : my_map) {
cout << it.first << " : " << it.second << endl;
}
cout << endl;
}
運(yùn)行結(jié)果：
my_map 變化前
apple : 2
banana : 3
2
0
my_map 變化后
apple : 2
banana : 3
pear : 0
注意map可以通過[key]訪問對應(yīng)的value。
關(guān)于map，本篇就主要介紹這[ ]接口了。
三、實(shí)例
??兩個數(shù)組的交集
（1）關(guān)于set的示例使用：
set在oj題中的應(yīng)用
題目名稱：兩個數(shù)組的交集
題目鏈接： 傳送門（聲明：題目來源于“力扣”）
題目描述
給定兩個數(shù)組 nums1 和 nums2 ，返回 它們的交集 。輸出結(jié)果中的每個元素一定是 唯一 的。我們可以 不考慮輸出結(jié)果的順序 。
解題思路：
將兩個數(shù)組分別進(jìn)set中去重得到s1和s2，然后將其中一個與另一個比較，判斷是否存在則是交集。
示例代碼：
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
vector<int> ret; //用于返回結(jié)構(gòu)的數(shù)組
//先通過set去重
set<int> s1;
for(int& it:nums1){
s1.insert(it);
}
set<int> s2;
for(int& it:nums2){
s2.insert(it);
}
for(auto& it:s1){
if(s2.count(it)){ //表示s1中的值在s2中可以找到
ret.push_back(it);
}
}
return ret;
}
};
??單詞識別
（2）關(guān)于map的使用
題目描述：
輸入一個英文句子，把句子中的單詞(不區(qū)分大小寫)按出現(xiàn)次數(shù)按從多到少把單詞和次數(shù)在屏幕上輸出來，次數(shù)一樣的按照單詞小寫的字典序排序輸出，要求能識別英文單詞和句號。
- 由于不區(qū)分大小寫，可以先將字符串中所有的字母轉(zhuǎn)化為小寫。
- 將字符串按照空格劃分，劃分為一個個單詞word。
- 將單詞存入map，沒出現(xiàn)一次單詞，該單詞的次數(shù)就+1；
- 最后按迭代器跑一遍即可。
示例代碼：
#include <iostream>
#include <vector>
#include <map>
#include <string>
using namespace std;
int main() {
string sentence;
getline(cin, sentence);
//全部轉(zhuǎn)化為小寫
for (auto& it : sentence) {
if (it >= 'A' && it <= 'Z') {
it += 32;
}
}
auto left = sentence.begin();
auto right = left;
map<string, int, less<string>> m;
for (int i = 0; i < sentence.size(); i++) {
right = sentence.begin();
if (sentence[i] == ' ' || sentence[i] == '.')
{
right += i;
string word(left, right);
left = right + 1;
m[word]++;
}
}
for (auto& it : m) {
cout << it.first << ":" << it.second << endl;
}
return 0;
}
到此這篇關(guān)于C++中map和set的使用小結(jié)的文章就介紹到這了,更多相關(guān)C++ map set內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
本篇文章主要介紹了 C語言的選擇排序,這里提供代碼實(shí)例以便大家理解,通過本文,更好的理解排序算法2021-11-11
這篇文章介紹了在一定的周期范圍內(nèi)去抓取新浪中行情數(shù)據(jù)，通過更新數(shù)據(jù)來緩解構(gòu)造模擬數(shù)據(jù)與真實(shí)數(shù)據(jù)差異性，感興趣的朋友可以了解一下2015-07-07
本文詳細(xì)講解了C++趣味算法之偵探推理，文中通過示例代碼介紹的非常詳細(xì)。對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-12-12
C++中實(shí)現(xiàn)線程安全和延遲執(zhí)行詳解
這篇文章主要為大家詳細(xì)介紹了C++中實(shí)現(xiàn)線程安全和延遲執(zhí)行的相關(guān)知識，文中的示例代碼講解詳細(xì)，具有一定的借鑒價值，需要的小伙伴可以了解下2024-01-01
這篇文章主要介紹了C語言中的malloc的使用,包括用其動態(tài)申請二維數(shù)組等功能,需要的朋友可以參考下2015-08-08
本文介紹了兩種自動分配地址的方法,包括通過宏定義實(shí)現(xiàn)地址分配和將EE地址作為一個結(jié)構(gòu)體,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2024-11-11
這篇文章主要介紹了如何利用OpenCV實(shí)現(xiàn)綠幕視頻背景替換功能，文中的示例代碼講解詳細(xì)，對我們學(xué)習(xí)OpenCV有一定的幫助，感興趣的可以學(xué)習(xí)一下2022-01-01
這篇文章主要介紹了關(guān)于C語言位運(yùn)算的簡單示例，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-12-12
三子棋是黑白棋的一種。三子棋是一種民間傳統(tǒng)游戲，又叫九宮棋、圈圈叉叉、一條龍、井字棋等。這篇文章就教你如何用C語言實(shí)現(xiàn)三子棋的功能2021-08-08
本文介紹利用QProcess獲取計(jì)算機(jī)的CPU、主板、硬盤等電腦相關(guān)硬件信息。文中的示例代碼講解詳細(xì)，對我們學(xué)習(xí)QT有一定的幫助，感興趣的可以了解一下2022-06-06