C++中的set和unordered_set

set

简介

集合（Set）容器是一个按特定顺序存储唯一元素的关联容器。

类模板

1
2
3
4

template < class T,
           class Compare = less<T>,
           class Alloc = allocator<T> >
> class set;

模板参数

1. T：元素的类型。
2. Compare：一个二元谓词，以两个元素为参数返回一个 bool 值。(比较函数)
3. Alloc：容器内部用来管理内存分配及释放的内存分配器的类型。这个参数是可选的，它的默认值是 std::allocator.

详细说明

在一个集合中，元素的值同时可以用来标志对应的元素（即值是自身的主键），每个值必须是唯一的。主键是不可修改的，因此在 set 中的元素不能被逐个修改（所有元素保持恒定），但是可以删除某个元素或插入新的元素。
set 容器中的所有元素都是按由类型为 Compare 的比较对象指定的严格弱序规则排序的。
在用主键访问单个元素时，set 容器通常比 unordered_set 容器低效，但 set 容器允许按顺序直接对某个子集进行迭代。
set 容器通常被实现为一个二叉搜索树（及其变型），该数据结构具有对数据自动排序的功能。 支持双向迭代

相关函数使用说明

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

#include <iostream>
#include <set>
#include <unordered_set>
using namespace std;
struct Node {
    int val;
    int id;
    Node(int id,int val)
    :val(val),id(id){

    }
};



bool operator<(const Node& a,const Node &b)
{
    return a.val<b.val;
}


int main(int argc, const char * argv[]) {
    cout<<"初始化一个set"<<endl;
    set<int> test_set = {2,3,19,8,6,7};

    cout<<"删除一个元素"<<endl;
    test_set.erase(19);

    cout<<"遍历set里面的元素"<<endl;
    for (auto pos = test_set.begin(); pos!=test_set.end(); pos++) {
        cout<<*pos<<" ";
    }
    cout<<endl;

    cout<<"查找元素的个数，如果为1就是找到，为0就是找不到"<<endl;
    if (test_set.count(5)==1) {
        cout<<"have find"<<endl;
    }else{
        cout<<"no find"<<endl;
    }

    cout<<"查找元素的迭代器，找不到则返回最后一个元素的迭代器，找得到就返回元素的迭代器"<<endl;
    if (test_set.find(5)!=test_set.end()) {
        cout<<"have find"<<endl;
    }else{
        cout<<"no find"<<endl;
    }

    cout<<"有效元素个数"<<endl;
    cout<<test_set.size()<<endl;

    cout<<"自定义类型的set，默认是less函数(<),所以必须重载<操作符,其他用法跟标准的set一样"<<endl;
    Node n1(1,5);
    Node n2(2,3);
    Node n3(3,9);
    set<Node> node_set;
    node_set.insert(n1);
    node_set.insert(n2);
    node_set.insert(n3);
    cout<<"遍历自定义类型set里面的元素"<<endl;
    for (auto pos = node_set.begin(); pos!=node_set.end(); pos++) {
        cout<<pos->id<<" ";
    }
    cout<<endl;
  return 0;
}

unordered_set

简介

无序集合（Unordered Set）容器是一个存储唯一元素的关联容器，容器中的元素无特别的次序关系。该容器允许基于值地快速元素检索。

类模板

1
2
3
4
5
6

// <unordered_set>
template < class Key,
    class Hash = hash<Key>,
    class Pred = equal_to<Key>,
    class Alloc = allocator<Key>
> class unordered_set;

模板参数

1. Key：元素的类型。
2. Hash：一元谓词，以一个 Key 类型的对象为参数，返回一个基于该对象的 size_t 类型的唯一值（哈希函数）。
3. Pred：二元谓词，以两个 Key 类型的对象为参数，返回一个 bool 值，如果第一个参数等价于第二个参数，该 bool 值为 true，否则为 false。默认为 std::equal_to。
4. Alloc：容器内部用来管理内存分配及释放的内存分配器的类型。这个参数是可选的，它的默认值是 std::allocator。

详细说明

在一个 unordered_set 容器中，元素的值同时可以用来标志对应的元素（即值是自身的主键），每个值必须是唯一的。主键是不可修改的，因此在 unordered_set 中的元素不能被逐个修改（所有元素保持恒定），但是可以删除某个元素或插入新的元素。
在 unordered_set 内部，元素不会按任何顺序排序，而是通过元素值的 hash 值将元素分组放置到各个槽（Bucket，也可译成“桶”）中，这样就能通过元素值快速地访问各个对应的元素（平均耗时为一个常量，即时间复杂度为 O(1)）。
在访问容器中的某个元素时，unordered_set 容器比 set 容器高效，而在迭代容器元素的某个子集时，前者比后者稍微低效了一点。
unordered_set 容器支持正向迭代

相关函数说明

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

#include <iostream>
#include <set>
#include <unordered_set>

using namespace std;
struct Node {
    int val;
    int id;
    Node(int id,int val)
    :val(val),id(id){

    }
};

struct node_hash_fun{
    size_t operator()(const Node &n)const{
        return n.id*50+n.val;
    }
};

struct node_equal_fun{
    bool operator()(const Node &n,const Node&m)const{
        return n.id==m.id&&n.val==m.val?true:false;
    }
};


int main(int argc, const char * argv[]) {
    cout<<"相当于java的hashSet,里面存放的元素是无序的,其他用法跟set大同小异"<<endl;
    unordered_set<int> test_unordered_set = {2,5,3,6,7,1,9,0};

    cout<<"遍历unordered_set"<<endl;
    for (auto pos = test_unordered_set.begin(); pos!=test_unordered_set.end(); pos++) {
        cout<<*pos<<" ";
    }
    cout<<endl;

    Node n1(1,5);
    Node n2(2,3);
    Node n3(3,9);
    cout<<"自定义类型unordered_set，必须重载hash_func和==操作符,其他用法跟标准的unordered_set一样"<<endl;   unordered_set<Node,node_hash_fun,node_equal_fun,allocator<Node>> node_unordered_set;
    node_unordered_set.insert(n1);
    node_unordered_set.insert(n2);
    node_unordered_set.insert(n3);

    cout<<"遍历自定义类型unordered_set"<<endl;
    for (auto pos = node_unordered_set.begin(); pos!=node_unordered_set.end(); pos++) {
        cout<<(*pos).id<<" ";
    }
    cout<<endl;

    return 0;
}

Comments