快捷導(dǎo)航

C++?set的使用示例詳解

更新時(shí)間：2024年10月10日 10:15:16 作者：鱷魚皮坡

序列式容器如vector、list等存儲(chǔ)數(shù)據(jù)的邏輯結(jié)構(gòu)為線性序列,元素的存儲(chǔ)和訪問是按位置順序進(jìn)行的,而關(guān)聯(lián)式容器如set、map等,本文給大家介紹C++?set的使用示例詳解,感興趣的朋友一起看看吧

1. 序列式容器和關(guān)聯(lián)式容器

前面，我們已經(jīng)接觸過STL中的部分容器如：string、vector、list、deque、array、forward_list等，這些容器統(tǒng)稱為序列式容器，因?yàn)檫壿嫿Y(jié)構(gòu)為線性序列的數(shù)據(jù)結(jié)構(gòu)，兩個(gè)位置存儲(chǔ)的值之間?般沒有緊密的關(guān)聯(lián)關(guān)系，?如交換?下，他依舊是序列式容器。順序容器中的元素是按他們?cè)谌萜髦械拇鎯?chǔ)位置來順序保存和訪問的。

關(guān)聯(lián)式容器也是用來存儲(chǔ)數(shù)據(jù)的，與序列式容器不同的是，關(guān)聯(lián)式容器邏輯結(jié)構(gòu)通常是非線性結(jié)構(gòu)，兩個(gè)位置有緊密的關(guān)聯(lián)關(guān)系，交換?下，他的存儲(chǔ)結(jié)構(gòu)就被破壞了。順序容器中的元素是按關(guān)鍵字來保存和訪問的。關(guān)聯(lián)式容器有map/set系列和unordered_map/unordered_set系列。

本章節(jié)講解的map底層是紅黑樹，紅黑樹是?顆平衡?叉搜索樹。set是key搜索場景的結(jié)構(gòu)， map是key/value搜索場景的結(jié)構(gòu)。

2. set系列的使用

2.1 set和multiset參考文檔

https://legacy.cplusplus.com/reference/set/

2.2 set類的介紹

set的聲明如下，T就是set底層關(guān)鍵字的類型
set默認(rèn)要求T?持?于?較，如果不?持或者想按??的需求?可以??實(shí)現(xiàn)仿函數(shù)傳給第?個(gè)模版參數(shù)
set底層存儲(chǔ)數(shù)據(jù)的內(nèi)存是從空間配置器申請(qǐng)的，如果需要可以??實(shí)現(xiàn)內(nèi)存池，傳給第三個(gè)參數(shù)
?般情況下，我們都不需要傳后兩個(gè)模版參數(shù)。
set底層是?紅?樹實(shí)現(xiàn)，增刪查效率是，迭代器遍歷是?的搜索樹的中序，所以是有序的 O(logN)
前?部分我們已經(jīng)學(xué)習(xí)了vector/list等容器的使用，STL容器接口設(shè)計(jì)，高度相似，所以這里我們就不再?個(gè)接口?個(gè)接口的介紹，而是直接帶著大家看文檔，挑?較重要的接口進(jìn)?介紹

template < class T, // set::key_type/value_type
            class Compare = less<T>, // set::key_compare/value_compare
            class Alloc = allocator<T> // set::allocator_type
            > class set;

2.3 set的構(gòu)造和迭代器

set的構(gòu)造我們關(guān)注以下幾個(gè)接口即可。

set的?持正向和反向迭代遍歷，遍歷默認(rèn)按升序順序，因?yàn)榈讓邮?叉搜索樹，迭代器遍歷?的中序；?持迭代器就意味著?持范圍for，set的iterator和const_iterator都不?持迭代器修改數(shù)據(jù)，修改關(guān)鍵字?jǐn)?shù)據(jù)，破壞了底層搜索樹的結(jié)構(gòu)。

// empty (1) ?參默認(rèn)構(gòu)造
explicit set (const key_compare& comp = key_compare(),
const allocator_type& alloc = allocator_type());
// range (2) 迭代器區(qū)間構(gòu)造
template <class InputIterator>
set (InputIterator first, InputIterator last,
const key_compare& comp = key_compare(),
const allocator_type& = allocator_type());
// copy (3) 拷?構(gòu)造
set (const set& x);
// initializer list (5) initializer 列表構(gòu)造
set (initializer_list<value_type> il,
const key_compare& comp = key_compare(),
const allocator_type& alloc = allocator_type());
// 迭代器是?個(gè)雙向迭代器
iterator -> a bidirectional iterator to const value_type
// 正向迭代器
iterator begin();
iterator end();
// 反向迭代器
reverse_iterator rbegin();
reverse_iterator rend();

2.4 set的增刪查

set的增刪查關(guān)注以下?個(gè)接?即可：

Member types
key_type -> The first template parameter (T)
value_type -> The first template parameter (T)
// 單個(gè)數(shù)據(jù)插?，如果已經(jīng)存在則插?失敗
pair<iterator,bool> insert (const value_type& val);
// 列表插?，已經(jīng)在容器中存在的值不會(huì)插?
void insert (initializer_list<value_type> il);
// 迭代器區(qū)間插?，已經(jīng)在容器中存在的值不會(huì)插?
template <class InputIterator>
void insert (InputIterator first, InputIterator last);
// 查找val，返回val所在的迭代器，沒有找到返回end()
iterator find (const value_type& val);
// 查找val，返回Val的個(gè)數(shù)
size_type count (const value_type& val) const;
// 刪除?個(gè)迭代器位置的值
iterator erase (const_iterator position);
// 刪除val，val不存在返回0，存在返回1
size_type erase (const value_type& val);
// 刪除?段迭代器區(qū)間的值
iterator erase (const_iterator first, const_iterator last);
// 返回?于等val位置的迭代器
iterator lower_bound (const value_type& val) const;
// 返回?于val位置的迭代器
iterator upper_bound (const value_type& val) const;

2.5 insert和迭代器遍歷使用樣例：

#include<iostream>
#include<set>
using namespace std;
int main()
{
    // 去重+升序排序
    set<int> s;
    // 去重+降序排序（給?個(gè)?于的仿函數(shù)）
    //set<int, greater<int>> s;
    s.insert(5);
    s.insert(2);
    s.insert(7);
    s.insert(5);
    //set<int>::iterator it = s.begin();
    auto it = s.begin();
    while (it != s.end())
    {
        // error C3892: “it”: 不能給常量賦值
        // *it = 1;
        cout << *it << " ";
        ++it;
    }
    cout << endl;
    // 插??段initializer_list列表值，已經(jīng)存在的值插?失敗
    s.insert({ 2,8,3,9 });
    for (auto e : s)
    {
        cout << e << " ";
    }
    cout << endl;
    set<string> strset = { "sort", "insert", "add" };
    // 遍歷string?較ascll碼??順序遍歷的
    for (auto& e : strset)
    {
        cout << e << " ";
    }
    cout << endl;
}

2.6 find和erase使用樣例：

#include<iostream>
#include<set>
using namespace std;
int main()
{
    set<int> s = { 4,2,7,2,8,5,9 };
    for (auto e : s)
    {
        cout << e << " ";
    }
    cout << endl;
    // 刪除最?值
    s.erase(s.begin());
    for (auto e : s)
    {
        cout << e << " ";
    }
    cout << endl;
    // 直接刪除x
    int x;
    cin >> x;
    int num = s.erase(x);
    if (num == 0)
    {
        cout << x << "不存在！" << endl;
    }
    for (auto e : s)
    {
        cout << e << " ";
    }
    cout << endl;
    // 直接查找在利?迭代器刪除x
    cin >> x;
    auto pos = s.find(x);
    if (pos != s.end())
    {
        s.erase(pos);
    }
    else
    {
        cout << x << "不存在！" << endl;
    }
    for (auto e : s)
    {
        cout << e << " ";
    }
    cout << endl;
    // 算法庫的查找 O(N)
    auto pos1 = find(s.begin(), s.end(), x);
    // set??實(shí)現(xiàn)的查找 O(logN)
    auto pos2 = s.find(x);
    // 利?count間接實(shí)現(xiàn)快速查找
    cin >> x;
    if (s.count(x))
    {
        cout << x << "在！" << endl;
    }
    else
    {
        cout << x << "不存在！" << endl;
    }
    return 0;
}

#include<iostream>
#include<set>
using namespace std;
int main()
{
    std::set<int> myset;
    for (int i = 1; i < 10; i++)
    myset.insert(i * 10); // 10 20 30 40 50 60 70 80 90
    for (auto e : myset)
    {
        cout << e << " ";
    }
    cout << endl;
    // 實(shí)現(xiàn)查找到的[itlow,itup)包含[30, 60]區(qū)間
    // 返回 >= 30
    auto itlow = myset.lower_bound(30);
    // 返回 > 60
    auto itup = myset.upper_bound(60);
    // 刪除這段區(qū)間的值
    myset.erase(itlow, itup);
    for (auto e : myset)
    {
        cout << e << " ";
    }
    cout << endl;
    return 0;
}

2.7 multiset和set的差異

multiset和set的使?基本完全類似，主要區(qū)別點(diǎn)在于multiset?持值冗余，那么insert/find/count/erase都圍繞著?持值冗余有所差異，具體參看下?的樣例代碼理解。

#include<iostream>
#include<set>
using namespace std;
int main()
{
    // 相?set不同的是，multiset是排序，但是不去重
    multiset<int> s = { 4,2,7,2,4,8,4,5,4,9 };
    auto it = s.begin();
    while (it != s.end())
    {
        cout << *it << " ";
        ++it;
    }
    cout << endl;
    // 相?set不同的是，x可能會(huì)存在多個(gè)，find查找中序的第?個(gè)
    int x;
    cin >> x;
    auto pos = s.find(x);
    while (pos != s.end() && *pos == x)
    {
        cout << *pos << " ";
        ++pos;
    }
    cout << endl;
    // 相?set不同的是，count會(huì)返回x的實(shí)際個(gè)數(shù)
    cout << s.count(x) << endl;
    // 相?set不同的是，erase給值時(shí)會(huì)刪除所有的x
    s.erase(x);
    for (auto e : s)
    {
        cout << e << " ";
    }
    cout << endl;
    return 0;
}

本篇文章介紹了關(guān)聯(lián)式容器set的使用，歡迎留言分享交流。

到此這篇關(guān)于C++ set的使用示例詳解的文章就介紹到這了,更多相關(guān)C++ set使用內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: