柚子快報(bào)激活碼778899分享：【C++】set詳解

http://yzkb.51969.com/

?博客主頁：https://blog.csdn.net/2301_779549673 ?歡迎點(diǎn)贊 ? 收藏 ?留言 ? 如有錯(cuò)誤敬請指正！ ?本文由 JohnKi 原創(chuàng)，首發(fā)于 CSDN? ?未來很長，值得我們?nèi)Ρ几案篮玫纳?

文章目錄

?前言???? 一、set類的介紹????二、set的構(gòu)造和迭代器????三、set的增刪查????四、insert和迭代器遍歷使用樣例?總結(jié)

?前言

Set 是 C++ 標(biāo)準(zhǔn)模板庫（STL）中的一種關(guān)聯(lián)容器，主要用于存儲(chǔ)不重復(fù)且有序的元素。其內(nèi)部實(shí)現(xiàn)采用紅黑樹，這種數(shù)據(jù)結(jié)構(gòu)具有自動(dòng)排序的特性，能夠高效地進(jìn)行插入、刪除和查找操作。

紅黑樹是一種平衡二叉搜索樹，它的統(tǒng)計(jì)性能優(yōu)于一般的平衡二叉樹。在 set 中，每個(gè)元素的值都唯一，并且元素的值不能直接被改變。這是因?yàn)?set 中的元素值就是其鍵值，關(guān)系到 set 元素的排列規(guī)則。如果任意改變 set 的元素值，會(huì)嚴(yán)重破壞 set 的組織。

Set 的迭代器被定義為底層紅黑樹的 const_iterator，杜絕了寫入操作。這意味著我們不能通過 set 的迭代器直接修改元素的值。例如，當(dāng)我們嘗試通過 set 的迭代器改變元素的值時(shí)，編譯器會(huì)報(bào)錯(cuò)。

此外，當(dāng)對(duì) set 進(jìn)行元素新增操作（insert）或刪除操作（erase）時(shí)，操作之前的所有迭代器，在操作完成之后都依然有效，被刪除的那個(gè)元素的迭代器必然是個(gè)例外。這種特性使得 set 在進(jìn)行動(dòng)態(tài)操作時(shí)，能夠保持迭代器的有效性，方便了程序的編寫和維護(hù)。

總的來說，C++ 中的 set 容器以其獨(dú)特的特性和高效的內(nèi)部實(shí)現(xiàn)，為程序員提供了一種方便、可靠的數(shù)據(jù)存儲(chǔ)和操作方式。

???? 一、set類的介紹

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

template < class T, // set::key_type/value_type

class Compare = less, // set::key_compare/value_compare

class Alloc = allocator // set::allocator_type

> class set;

????二、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)。

Set 的構(gòu)造方式主要有以下幾種： 默認(rèn)構(gòu)造函數(shù)：set st;，創(chuàng)建一個(gè)空的 set。例如：set mySet;。 拷貝構(gòu)造函數(shù)：set(const set &st);，創(chuàng)建一個(gè)新的 set，它是現(xiàn)有 set 的副本。例如：set mySet = {1, 2, 3}; set anotherSet(mySet);。 使用區(qū)間構(gòu)造：可以用一個(gè)已有的區(qū)間中的元素構(gòu)造 set，如set s2(s1.begin(), s1.end());。 賦值操作可以使用重載的等號(hào)操作符：set& operator=(const set &st);，將一個(gè) set 的內(nèi)容賦值給另一個(gè)已經(jīng)存在的 set。例如：set mySet = {1, 2, 3}; set anotherSet; anotherSet = mySet;。

// 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

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 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();

????三、set的增刪查

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

插入元素 使用insert方法可以在 set 中插入元素。例如：mySet.insert(5);。如果元素已存在，插入操作將被忽略。insert方法的返回值是個(gè)pair結(jié)構(gòu)的對(duì)組，pair，bool 代表插入是否成功。當(dāng)向 set 容器添加元素成功時(shí)，該迭代器指向 set 容器新添加的元素，bool 類型的值為 true；如果添加失敗，即證明原 set 容器中已存有相同的元素，此時(shí)返回的迭代器就指向容器中相同的此元素，同時(shí) bool 類型的值為 false。查找元素 使用find方法查找 set 中元素。例如：auto it = mySet.find(element);，如果找到元素，it將指向該元素；否則，it將指向 set 的尾后。可以通過判斷it是否等于end()來確定元素是否被找到。刪除元素 使用erase方法刪除 set 中元素，有以下幾種方式： 刪除迭代器指向的元素：erase(pos);，例如：auto it = mySet.find(3); if(it!= mySet.end()){ it = mySet.erase(it); }。 刪除指定值的元素：erase(elem);，例如：mySet.erase(4);。 刪除區(qū)間內(nèi)的元素：erase(beg, end);。其他方法 size()：返回 set 中元素的數(shù)目。 empty()：判斷 set 是否為空。如果為空，返回 true；否則返回 false。 clear()：清空 set 中的所有元素。 lower_bound()：返回大于或等于給定元素的第一個(gè)元素的迭代器。 upper_bound()：返回大于給定元素的第一個(gè)元素的迭代器。 equal_range()：返回一組迭代器，表示給定元素在 set 中的范圍。

Member types

key_type -> The first template parameter (T)

value_type -> The first template parameter (T)

// 單個(gè)數(shù)據(jù)插?，如果已經(jīng)存在則插?失敗

pair insert (const value_type& val);

// 列表插?，已經(jīng)在容器中存在的值不會(huì)插?

void insert (initializer_list il);

// 迭代器區(qū)間插?，已經(jīng)在容器中存在的值不會(huì)插?

template

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;

易錯(cuò)點(diǎn)提示 end()函數(shù)的正確用法：end()函數(shù)的作用不是用于返回最后一個(gè)元素，而是用于返回 set 中最后一個(gè)元素的后一個(gè)位置的指針。如果一個(gè) set 中的元素是<1,2,3>，那么返回的就是元素 3 之后的一位的指針。如果要看最后一個(gè)元素，可以使用遍歷的方式找到最后一個(gè)元素，或者使用其他方法。

不能直接 copy：不能將一個(gè) set 直接使用=號(hào)賦值給另外一個(gè) set。如下面的寫法就是錯(cuò)誤的：set set1; set set2 = set1;。這種寫法會(huì)導(dǎo)致編譯錯(cuò)誤或者不可預(yù)期的結(jié)果。在 C++ 中，set 的賦值操作需要使用特定的方法，如拷貝構(gòu)造函數(shù)或者賦值運(yùn)算符重載。

????四、insert和迭代器遍歷使用樣例

#include

#include

using namespace std;

int main() {

// 去重+升序排序

set s;

// 去重+降序排序（給?個(gè)?于的仿函數(shù)）

//set> s;

s.insert(5);

s.insert(2);

s.insert(7);

s.insert(5);

//set::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 strset = { "sort", "insert", "add" };

// 遍歷string?較ascll碼??順序遍歷的

for (auto& e : strset) {

cout << e << " ";

}

cout << endl;

}

?總結(jié)

本篇博文對(duì) set 做了一個(gè)較為詳細(xì)的介紹，不知道對(duì)你有沒有幫助呢

覺得博主寫得還不錯(cuò)的三連支持下吧！會(huì)繼續(xù)努力的~

柚子快報(bào)激活碼778899分享：【C++】set詳解

http://yzkb.51969.com/

精彩文章