C++ STL之Set

set是關聯容器,類似于集合。

特點是里面的元素不會重復,而且元素時有序的。

1.聲明定義:

#include<set>using namespace std;set<int> s;

2.常見用法

s.inert(5); //插入
s.begin();  //返回s的第一個元素 

s.end(); // 返回最后一個元素

s.clear() ; //清空

s.empty(); //判斷是否為空

s.max_size() //返回最可能包含的元素最大個數

s.size();        //返回當前元素的個數

s.rbegin();     //同end()

s.rend();       // 同begin()

s.equal_range();  //返回集合中與給定值相等的上下限兩個迭代器

s.erase();          //刪除集合中的元素

s.lower_bound  //返回大于或等于某值的第一個元素迭代器

s.key_comp();   //返回一個用于中間值比較的函數

s.upper_bound  //返回大于的第一個元素迭代器

3.自定義比較函數

1)元素不是結構體:(自定義比較函數myComp,重載“()”操作符)

struct myComp{bool operator() (const your_type &a,const your_type &b){return a.data - b.data > 0;}
}

2)如果元素是結構體

struct Info{string name;int score;bool operator<const Info &a) const{return a.score < score;}
}

---------------------------------------------------------------------------------------------

補充:

C++容器分為順序容器和關聯性容器:

? ? 順序容器包括vector、deque、list、forward_list、array、string,所有順序容器都提供了快速順序訪問元素的能力。

? ? 關聯容器包括set、map的關聯型容器和順序容器有著根本的不同:關聯容器中的元素是按關鍵字來保存和訪問的。

? ? 關聯容器不支持順序容器的位置相關的操作。原因是關聯容器中元素是根據關鍵字存儲的,這些操作對關聯容器沒有意義。

而且,關聯容器也不支持構造函數或插入操作這些接受一個元素值和一個數量值得操作。

? ? 關聯容器支持高效的關鍵字查找和訪問

? ??map中的元素是一些關鍵字----值(key--value)對:關鍵字起到索引的作用,值則表示與索引相關聯的數據。

? ??set中每個元素只包含一個關鍵字:set支持高效的關鍵字查詢操作----檢查一個給定關鍵字是否在set中。

? ??set封裝的二叉樹,所以它支持插入數據的排序,它是關聯式容器,存儲同一數據類型,set中的每一個元素都是唯一的,系統會根據元素的值自動進行排序。

? ? 它們內部采用的是平衡檢索二叉樹:紅黑樹,它的統計性能要好于一般的平衡二叉樹。

1)map和set的插入刪除效率要比其他序列容器高

? ? 對于關聯容器來說,不需要內存拷貝和移動。

? ? set容器所有元素都是以節點的方式來存儲,節點結構和鏈表相似,指向父節點和子節點。插入和刪除的時候改變的都是指針,不會移動內存。

2)每次insert之后,以前保存的iterator不會失效。

? ? iterator等價于指向節點的指針,其內存沒有發生變化,指向內存的指針也不會出現失效的情況。

? ? 對于vector來說,每一次插入和刪除都有可能使指針失效,即使在尾部插入也是 如此。

? ? 這是因為為了保證內部數據的連續存放,iterator指向的那塊內存在刪除和插入的過程可能已經被其他內存覆蓋和釋放了。

? ? 即使是用push_back的時候,容器的存儲空間可能不夠,需要一塊更大的內存。

? ? 只有把以前的內存釋放掉,申請更大的內存,復制已有的數據元素到新的內存,最后把需要插入的元素放到最后。

? ?那么以前的內存指針必然不可再用了。

3)當元素增多的時候,set的插入和搜索速度變化是不變的。? ?紅黑樹的查找時間復雜度都是logN。

----------------------------------------------------------------------------------------------------------------------------------------------------------------------

未完待續

?

轉載于:https://www.cnblogs.com/wanghao-boke/p/10483967.html

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/news/385101.shtml
繁體地址,請注明出處:http://hk.pswp.cn/news/385101.shtml
英文地址,請注明出處:http://en.pswp.cn/news/385101.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

表示數值的字符串

題目描述 請實現一個函數用來判斷字符串是否表示數值&#xff08;包括整數和小數&#xff09;。例如&#xff0c;字符串"100","5e2","-123","3.1416"和"-1E-16"都表示數值。 但是"12e","1a3.14","…

數據庫簡單實用(一)

一、實驗環境&#xff1a; MySQL 2.7.22 xfce終端 二、開發準備 打開MySQL服務并使用root登錄 sudo service mysql start //打開mysql服務 mysql -u root //使用root用戶登錄&#xff0c;密碼為空 -u和root之間可以不用空格 三、實驗步驟 //如果在操作中忘掉&#xff1b;可以使…

lambda 表達式定制操作

泛型算法中的定制操作 許多算法都會比較輸入序列中的元素以達到排序的效果&#xff0c;通過定制比較操作&#xff0c;可以控制算法按照編程者的意圖工作。 普通排序算法&#xff1a;template<class RandomIterator> void sort(RandomIterator first,RandomIterator last)…

包含min函數的棧

題目描述 定義棧的數據結構&#xff0c;請在該類型中實現一個能夠得到棧中所含最小元素的min函數&#xff08;時間復雜度應為O&#xff08;1&#xff09;&#xff09;。 解法&#xff1a; class Solution { public:stack<int> s;stack<int> s_min;void push(int v…

01-復雜度3 二分查找 (20 分)

本題要求實現二分查找算法。 函數接口定義&#xff1a; Position BinarySearch( List L, ElementType X );其中List結構定義如下&#xff1a; typedef int Position; typedef struct LNode *List; struct LNode {ElementType Data[MAXSIZE];Position Last; /* 保存線性表中最后…

二叉樹的鏡像

題目描述 操作給定的二叉樹&#xff0c;將其變換為源二叉樹的鏡像。 輸入描述: 二叉樹的鏡像定義&#xff1a;源二叉樹 8/ \6 10/ \ / \5 7 9 11鏡像二叉樹8/ \10 6/ \ / \11 9 7 5 解法&#xff1a; /* struct TreeNode {int val;struct TreeNode *left;struct Tre…

01-復雜度1 最大子列和問題 (20 分)

給定K個整數組成的序列{ N?1??, N?2??, ..., N?K?? }&#xff0c;“連續子列”被定義為{ N?i??, N?i1??, ..., N?j?? }&#xff0c;其中 1≤i≤j≤K。“最大子列和”則被定義為所有連續子列元素的和中最大者。例如給定序列{ -2, 11, -4, 13, -5, -2 }&#x…

300. 最長上升子序列

給定一個無序的整數數組&#xff0c;找到其中最長上升子序列的長度。 示例: 輸入: [10,9,2,5,3,7,101,18] 輸出: 4 解釋: 最長的上升子序列是 [2,3,7,101]&#xff0c;它的長度是 4。 說明: 可能會有多種最長上升子序列的組合&#xff0c;你只需要輸出對應的長度即可。 你算法…

02-線性結構1 兩個有序鏈表序列的合并 (15 分)

本題要求實現一個函數&#xff0c;將兩個鏈表表示的遞增整數序列合并為一個非遞減的整數序列。 函數接口定義&#xff1a; List Merge( List L1, List L2 );其中List結構定義如下&#xff1a; typedef struct Node *PtrToNode; struct Node {ElementType Data; /* 存儲結點數據…

50. Pow(x, n)

實現 pow(x, n) &#xff0c;即計算 x 的 n 次冪函數。 示例 1: 輸入: 2.00000, 10 輸出: 1024.00000 示例 2: 輸入: 2.10000, 3 輸出: 9.26100 示例 3: 輸入: 2.00000, -2 輸出: 0.25000 解釋: 2-2 1/22 1/4 0.25 說明: -100.0 < x < 100.0 n 是 32 位有符號整數&…

01-復雜度2 Maximum Subsequence Sum (25 分)

Given a sequence of K integers { N?1??, N?2??, ..., N?K?? }. A continuous subsequence is defined to be { N?i??, N?i1??, ..., N?j?? } where 1. The Maximum Subsequence is the continuous subsequence which has the largest sum of its elements.…

進制轉換習題

題目&#xff1a;進制轉換 解法&#xff1a; #include <iostream> #include <vector> #include <algorithm> using namespace std; long long nums, k;void solution(long long nums, long long k) {vector<int> res;while(nums){long long curr nu…

02-線性結構2 一元多項式的乘法與加法運算 (20 分)

設計函數分別求兩個一元多項式的乘積與和。 輸入格式: 輸入分2行&#xff0c;每行分別先給出多項式非零項的個數&#xff0c;再以指數遞降方式輸入一個多項式非零項系數和指數&#xff08;絕對值均為不超過1000的整數&#xff09;。數字間以空格分隔。 輸出格式: 輸出分2行&…

《Leetcode | 02》

序號題目類型標記 863. 二叉樹中所有距離為 K 的結點 ★ 94. 二叉樹的中序遍歷 ★ 102. 二叉樹的層次遍歷 144. 二叉樹的前序遍歷 450. 刪除二叉搜索樹中的節點 701. 二叉搜索樹中的插入操作 700. 二叉搜索樹中的搜索 108. 將有序數組轉換為二叉搜索樹 701. …

C++基礎:各種輸入方法總結

輸入原理簡述&#xff1a; 程序的輸入都建有一個緩沖區&#xff0c;即輸入緩沖區。每次輸入過程是這樣的&#xff0c;當一次鍵盤輸入結束時會將輸入的數據存入輸入緩沖區&#xff0c;而cin函數直接從輸入緩沖區中取數據。正因為cin函數是直接從緩沖區取數據的&#xff0c;所以…

04-樹7 二叉搜索樹的操作集 (30 分)

本題要求實現給定二叉搜索樹的5種常用操作。 函數接口定義&#xff1a; BinTree Insert( BinTree BST, ElementType X ); BinTree Delete( BinTree BST, ElementType X ); Position Find( BinTree BST, ElementType X ); Position FindMin( BinTree BST ); Position FindMax( B…

02-線性結構3 Reversing Linked List (25 分)

Given a constant K and a singly linked list L, you are supposed to reverse the links of every K elements on L. For example, given L being 1→2→3→4→5→6, if K3, then you must output 3→2→1→6→5→4; if K4, you must output 4→3→2→1→5→6. Input Specifi…

03-樹1 樹的同構 (25 分)

給定兩棵樹T1和T2。如果T1可以通過若干次左右孩子互換就變成T2&#xff0c;則我們稱兩棵樹是“同構”的。例如圖1給出的兩棵樹就是同構的&#xff0c;因為我們把其中一棵樹的結點A、B、G的左右孩子互換后&#xff0c;就得到另外一棵樹。而圖2就不是同構的。 圖1 圖2 現給定兩棵…

【樹】104. 二叉樹的最大深度

題目 104. 二叉樹的最大深度 方法1 /*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr),…

Leetcode 206. 反轉鏈表

206. 反轉鏈表 解法1 class Solution { public:ListNode *reverseList(ListNode *head){if(!head || !head->next)return head;ListNode *p;p reverseList(head->next);head->next->next head;head->next nullptr;return p;} };解法2 /*** Definition for…