[C++知识库]C++高效集合数据结构设计

绪论

在复杂算法实现过程中我们经常会需要一个高效的集合数据结构，支持常数级别的增、删、查，以及随机返回、遍历，最好还能够支持交集、并集、子集操作

哈希集合实现

大家可能很快想到unordered_set，unordered_set由于底层是哈希表，所以自身就支持常数级别的增、删、查，虽然不支持常数级别的随机返回，但是可以很简单地实现一个O(n)的随机返回。于是我们可以很快实现一个好用的Set数据结构：

头文件Set.h

// Copyright(C), Edward-Elric233
// Author: Edward-Elric233
// Version: 1.0
// Date: 2022/6/27
// Description: 封装unordered_set实现支持交集、并集的set
#ifndef P_CENTER_SET_H
#define P_CENTER_SET_H

#include <unordered_set>
#include <vector>
#include <iostream>

namespace edward {

class Set {
    std::unordered_set<int> set_;
public:
    Set() = default;
    ~Set() = default;
    explicit Set(const std::vector<int> &arr):set_(arr.begin(), arr.end()) {}
    void insert(int x) {
        set_.insert(x);
    }
    void erase(int x) {
        set_.erase(x);
    }
    int size() const {
        return set_.size(); //size_t -> int
    }
    bool empty() const {
        return set_.empty();
    }
    bool exist(int x) const {
        return set_.count(x) > 0;
    }
    const std::unordered_set<int>& getSet() const {
        return set_;
    }
    int getRandom() const;
    const Set& operator&= (const Set& rhs);
    const Set& operator|= (const Set& rhs);
    bool operator<= (const Set& rhs) const;   //check if it's a subset of the right-hand side.
    friend Set operator& (const Set& lhs, const Set& rhs);
    friend Set operator| (const Set& lhs, const Set& rhs);
    friend std::ostream& operator<< (std::ostream &os, const Set& rhs);
};

Set operator& (const Set& lhs, const Set& rhs);
Set operator| (const Set& lhs, const Set& rhs);
std::ostream& operator<< (std::ostream &os, const Set& rhs);

}


#endif //P_CENTER_SET_H

实现文件Set.cpp

// Copyright(C), Edward-Elric233
// Author: Edward-Elric233
// Version: 1.0
// Date: 2022/6/27
// Description: 
#include "Set.h"
#include "utils.h"

namespace edward {

const Set& Set::operator&=(const Set &rhs) {
    for (auto iter = set_.begin(); iter != set_.end(); ) {
        if (rhs.set_.count(*iter) == 0) {
            set_.erase(iter++);
        } else {
            ++iter;
        }
    }
    return *this;
}

const Set& Set::operator|=(const Set &rhs) {
    for (auto x : rhs.set_) {
        insert(x);
    }
    return *this;
}

bool Set::operator<=(const Set &rhs) const {
    //check if it's a subset of the right-hand side.
    for (auto x : set_) {
        if (!rhs.exist(x)) return false;
    }
    return true;
}

Set operator& (const Set& lhs, const Set& rhs) {
    if (lhs.size() > rhs.size()) {
        return operator&(rhs, lhs);
    } else {
        //lhs.size() <= rhs.size()
        Set ans;
        for (auto x : lhs.set_) {
            if (rhs.set_.count(x) > 0) {
                ans.insert(x);
            }
        }
        return ans;
    }
}
Set operator| (const Set& lhs, const Set& rhs) {
    //按秩合并
    if (lhs.size() > rhs.size()) {
        return operator|(rhs, lhs);
    } else {
        //lhs.size() <= rhs.size()
        Set ans = rhs;
        return ans |= lhs;
    }
}

std::ostream& operator<< (std::ostream &os, const Set& rhs) {
    for (auto x : rhs.set_) {
        os << x << " ";
    }
    return os;
}

int Set::getRandom() const {
    int idx = Random::rand(size());
    auto iter = set_.begin();
    while (idx--) ++iter;
    return *iter;
}

}

标记数组实现

使用哈希表其实帮助我们解决了常数插入删除的问题，但是当我们尤其要求集合的高效时使用哈希表仍然有比较高的复杂度常数。这就要求我们使用空间换时间的思想：直接用数组进行哈希，每个元素值本身就是自己在数组中的下标（值到下标的哈希映射为：$x?x$）。这种哈希毋庸置疑是最快的，因为根本不需要进行运算，但是我们存在无法遍历和随机返回的问题，为了解决这个问题，我们再用一个辅助的数组存储值，而标记数组中则存储的是值在辅助数组中的下标，只要我们能够保证元素在辅助数组中是紧凑的，那么就可以实现遍历和随机返回，并且随机返回是O(1)的。
这种实现能够满足我们绝大多数需求，但是缺点也是显而易见的：空间复杂度太高，每个集合的空间复杂度固定地为集合元素的值域的大小，当我们元素的值域不是太大的时候，我们就可以使用这种集合实现，否则就只能使用上面的哈希集合。

头文件RandomSet.h

// Copyright(C), Edward-Elric233
// Author: Edward-Elric233
// Version: 1.0
// Date: 2022/7/4
// Description: 
#ifndef P_CENTER_RANDOMSET_H
#define P_CENTER_RANDOMSET_H

#include <vector>
#include "utils.h"

namespace edward {

class RandomSet {
    std::vector<int> pos_, nums_;
public:
    explicit RandomSet(int n)
    : pos_(n, -1) {
        nums_.reserve(n);
    }

    void insert(int x) {
        pos_[x] = nums_.size();
        nums_.push_back(x);
    }
    void erase(int x) {
        nums_[pos_[x]] = nums_.back();
        pos_[nums_.back()] = pos_[x];
        pos_[x] = -1;
        nums_.pop_back();
    }
    int size() const {
        return nums_.size(); //size_t -> int
    }
    bool empty() const {
        return nums_.empty();
    }
    bool exist(int x) const {
        return pos_[x] != -1;
    }
    const std::vector<int>& getSet() const {
        return nums_;
    }
    int getRandom() const {
        return nums_[Random::rand(nums_.size())];
    }
    friend std::ostream& operator<< (std::ostream& os, const RandomSet& randomSet);
};

std::ostream& operator<< (std::ostream& os, const RandomSet& randomSet);

}


#endif //P_CENTER_RANDOMSET_H

实现文件RandomSet.cpp

// Copyright(C), Edward-Elric233
// Author: Edward-Elric233
// Version: 1.0
// Date: 2022/7/4
// Description: 
#include "RandomSet.h"

namespace edward {

std::ostream& operator<< (std::ostream& os, const RandomSet& randomSet) {
    for (auto x : randomSet.nums_) {
        os << x << " ";
    }
    return os;
}

}

测试文件test.cpp

// Copyright(C), Edward-Elric233
// Author: Edward-Elric233
// Version: 1.0
// Date: 2022/6/27
// Description: 
#include "test.h"
#include "Set.h"
#include "utils.h"
#include "RandomSet.h"

namespace edward {

void test_Set() {
    /*
    edward::Set a({1,2}), b({3,4,5});
    //a.insert(4);

    print("a.size():", a.size());
    print("a & b:", a & b);
    print("a | b:", a | b);
    //print("a &= b:", a &= b);
    print("a |= b:", a |= b);
    */
}

void test_RandomSet() {
    RandomSet randomSet(10);
    randomSet.insert(0);
    randomSet.insert(1);
    randomSet.insert(2);
    print(randomSet);
    randomSet.erase(1);
    print(randomSet);
    print(randomSet.size());
    randomSet.erase(2);
    randomSet.erase(0);
    randomSet.insert(9);
    print(randomSet);
}

void test_Set_efficiency() {
    constexpr int MAXN = 1000000;
    Timer timer_Set;
    edward::Set set;
    for (int i = 0; i < MAXN; ++i) {
        set.insert(i);
    }
    for (int i = 0; i < MAXN; i += 2) {
        set.erase(i);
    }
    for (int i = 0; i < MAXN; i += 2) {
        set.insert(i);
    }
    print("Set.size() =", set.size());
    timer_Set("Set:");
    Timer timer_RandomSet;
    edward::RandomSet randomSet(MAXN);
    for (int i = 0; i < MAXN; ++i) {
        randomSet.insert(i);
    }
    for (int i = 0; i < MAXN; i += 2) {
        randomSet.erase(i);
    }
    for (int i = 0; i < MAXN; i += 2) {
        randomSet.insert(i);
    }
    print("RandomSet.size() =", randomSet.size());
    timer_RandomSet("RandomSet:");
}

}

其中print是我自己实现的打印可变参模板函数，Timer类是计时器，实现文件放在文章末尾。
测试结果如下：

Set.size() = 1000000
Set: 0.522428 s
RandomSet.size() = 1000000
RandomSet: 0.0637485 s

我们可以看出，使用数组实现的集合虽然存在大小的限制，但是操作平均快一个量级。对于我们需要设计高效算法的场合，我们可以使用后者。大家可能注意到我没有在第二种实现RandomSet中重载集合操作，这是因为如果已经需要考虑优化常数的话，那么往往也不允许实现一个完整的集合操作（交集、并集、子集），而是要求用户具体地手动实现，并根据实际情况进行优化。

工具文件utils.h

// Copyright(C), Edward-Elric233
// Author: Edward-Elric233
// Version: 1.0
// Date: 2022/6/27
// Description: 
#ifndef P_CENTER_UTILS_H
#define P_CENTER_UTILS_H

#include <iostream>
#include <random>
#include <chrono>

namespace edward {

constexpr int INF = 0x3f3f3f3f;

inline void print() {
    std::cout << "\n";
}
template<typename T, typename... Args>
void print(T&& first, Args&&... args) {
    std::cout << first << " ";
    print(std::forward<Args>(args)...);
}

class Random {
public:
    // random number generator.
    static std::mt19937 pseudoRandNumGen;
    static void initRand(int seed) { pseudoRandNumGen = std::mt19937(seed); }
    static int fastRand(int lb, int ub) { return (pseudoRandNumGen() % (ub - lb)) + lb; }
    static int fastRand(int ub) { return pseudoRandNumGen() % ub; }
    static int rand(int lb, int ub) { return std::uniform_int_distribution<int>(lb, ub - 1)(pseudoRandNumGen); }
    static int rand(int ub) { return std::uniform_int_distribution<int>(0, ub - 1)(pseudoRandNumGen); }
};

class Timer {
    std::chrono::time_point<std::chrono::system_clock> timePoint_;
public:
    Timer(): timePoint_(std::chrono::system_clock::now()) {}
    Timer(const Timer&) = delete;
    ~Timer() = default;
    void operator() (const std::string& msg) {
        auto duration = std::chrono::system_clock::now() - timePoint_;
        print(msg, static_cast<double>(duration.count()) / decltype(duration)::period::den, "s");
    }
};

}

#endif //P_CENTER_UTILS_H

工具文件utils.cpp

// Copyright(C), Edward-Elric233
// Author: Edward-Elric233
// Version: 1.0
// Date: 2022/6/27
// Description: 
#include "utils.h"

namespace edward {

std::mt19937 Random::pseudoRandNumGen;

}