C++ set 与 unordered

区别：

比较项	set	unordered_set
排序	升序(默认)	无排序
实现	自平衡BST，类似红黑树	哈希表
搜索时间	log(n)	O(1) -> Average，O(n) -> Worst Case
插入时间	log(n) + Rebalance	Same as search
删除时间	log(n) + Rebalance	Same as search

何时使用set

需要有序的数据。
将不得不按排序顺序打印/访问数据。
需要元素的前任/后继。
由于set是有序的，因此可以在set元素上使用binary_search()，lower_bound()和upper_bound()之类的函数。这些函数不能在unordered_set()上使用。
有关更多情况，请参见BST优于哈希表的优势。

在以下情况下使用unordered_set

需要保留一组不同的元素，并且不需要排序。
需要单元素访问，即无遍历。

set:
Input  :  1, 8, 2, 5, 3, 9
Output :  1, 2, 3, 5, 8, 9

Unordered_set:
Input  : 1, 8, 2, 5, 3, 9
Output : 9 3 1 8 2 5

如果要查看c ++ STL中set和unordered_set的实现详细信息，请参见Set Vs Map。 Set允许按排序顺序遍历元素，而Unordered_set不允许按排序顺序遍历元素。

// Program to print elements of set 
#include <bits/stdc++.h> 
using namespace std; 

int main() 
{ 
    set<int> s; 
    s.insert(5); 
    s.insert(1); 
    s.insert(6); 
    s.insert(3); 
    s.insert(7); 
    s.insert(2); 

    cout << "Elements of set in sorted order: \n" 
    for (auto it : s) 
        cout << it << " "; 

    return 0; 
}

执行上面示例代码，得到以下结果：

Elements of set in sorted order: 
1 2 3 5 6 7

// Program to print elements of set 
#include <bits/stdc++.h> 
using namespace std; 

int main() 
{ 
    unordered_set<int> s; 
    s.insert(5); 
    s.insert(1); 
    s.insert(6); 
    s.insert(3); 
    s.insert(7); 
    s.insert(2); 

    cout << "Elements of unordered_set: \n" 
    for (auto it : s) 
        cout << it << " "; 

    return 0; 
}

执行上面示例代码，得到以下结果：

Elements of unordered_set: 
2 7 5 1 6 3

套装中的前任/后继：
可以修改Set来查找其前任或后继，而Unordered_set不允许查找前任/后继。

// Program to print inorder predecessor and inorder successor 
#include <bits/stdc++.h> 
using namespace std; 

set<int> s; 

void inorderPredecessor(int key) 
{ 
    if (s.find(key) == s.end()) { 
        cout << "Key doesn't exist\n" 
        return; 
    } 

    set<int>::iterator it; 
    it = s.find(key); // get iterator of key 

    // If iterator is at first position 
    // Then, it doesn't have predecessor 
    if (it == s.begin()) { 
        cout << "No predecessor\n" 
        return; 
    } 

    --it; // get previous element 
    cout << "predecessor of " << key << " is="; 
    cout << *(it) << "\n" 
} 

void inorderSuccessor(int key) 
{ 
    if (s.find(key) == s.end()) { 
        cout << "Key doesn't exist\n" 
        return; 
    } 

    set<int>::iterator it; 
    it = s.find(key); // get iterator of key 
    ++it; // get next element 

    // Iterator points to NULL (Element does 
    // not exist) 
    if (it == s.end()) 
    { 
        cout << "No successor\n" 
        return; 
    } 
    cout << "successor of " << key << " is="; 
    cout << *(it) << "\n" 
} 

int main() 
{ 
    s.insert(1); 
    s.insert(5); 
    s.insert(2); 
    s.insert(9); 
    s.insert(8); 

    inorderPredecessor(5); 
    inorderPredecessor(1); 
    inorderPredecessor(8); 
    inorderSuccessor(5); 
    inorderSuccessor(2); 
    inorderSuccessor(9); 

    return 0; 
}

执行上面示例代码，得到以下结果：

predecessor of 5 is=2
No predecessor
predecessor of 8 is=5
successor of 5 is=8
successor of 2 is=5
No successor

欢迎任何形式的转载，但请务必注明出处，尊重他人劳动成果。
转载请注明：文章转载自有区别网 [http://www.vsdiffer.com]
本文标题：C++ set 与 unordered_set的区别
本文链接：https://www.vsdiffer.com/vs/set-vs-unordered_set-c-stl.html
免责声明：以上内容仅是站长个人看法、理解、学习笔记、总结和研究收藏。不保证其正确性，因使用而带来的风险与本站无关！如本网站内容冒犯了您的权益，请联系站长，邮箱：，我们核实并会尽快处理。

C++ set 与 unordered_set的区别

随机