STL-set

集合set

集合内部元素是有序的不能重复
不能通过指针修改元素的值，只能删掉，重新插入
multiset可以添加重复元素

• 插入元素

Integer.insert(12);
multiInteger.insert(Integer.begin(), Integer.end());

• 查找元素

auto it = Integer.find(23);

• 删除元素

Integer.erase(it);

• 统计元素个数（针对multiset）

multiInteger.count(10)

• 查找第一个大于或小于某个值的数

upper_bound()
lower_bound()

代码示例1: set与multiset

#include <iostream>
#include <set>
using namespace std;

struct Contact
{
    string name;
    int num;
    Contact(const string& _name, const int& _num) {
        name = _name;
        num = _num;
    }
    bool operator < (const Contact& itemToCompare) const {
        return this->num < itemToCompare.num;
    }
    void display() const {
        cout << "name=" << this->name << ", num=" << this->num << endl;
    }
};

template<typename T>
void info(const T& se) {
    cout << "INFO: ";
    for (auto& s : se) {
        cout << s << " ";
    }
    cout << endl;
}
int main(int argc, char const *argv[])
{
    set<int> Integer;
    Integer.insert(12);
    Integer.insert(23);
    Integer.insert(1);
    info(Integer);
    it = Integer.upper_bound(10);
    if (it != Integer.end())
        cout << "Found: " << *it << endl;
    else
        cout << "NOT Found" << endl;

    auto it = Integer.find(23);
    if (it != Integer.end()) {
        cout << *it << endl;
    }
    Integer.erase(it);
    info(Integer);
    Integer.clear();
    info(Integer);

    multiset<int> multiInteger;
    multiInteger.insert(10);
    multiInteger.insert(10);
    multiInteger.insert(Integer.begin(), Integer.end());
    info(multiInteger);
    cout << multiInteger.count(10) << endl;
    return 0;
}
INFO: 1 12 23 
Found: 12   // 找到第一个大于10的元素
23
INFO: 1 12 
INFO: 
INFO: 10 10 
2

代码示例2: 存储结构体

要重载<和==运算符，前者用于排序，后者用于查找
问题
用哪个值去实现<运算符，也会用那个值去find

struct Contact
{
    string name;
    int num;
    Contact(const string& _name, const int& _num) {
        name = _name;
        num = _num;
    }


    // 如果这里用num去排序，查找时也是看num相不相同
    bool operator < (const Contact& itemToCompare) const {
        return (this->name < itemToCompare.name);
    }
    // 所以这里的规则最好一样
    bool operator == (const Contact& itemToCompare) const {
        return (this->name == itemToCompare.name);
    }

    void display() const {
        cout << "name=" << this->name << ", num=" << this->num << endl;
    }
};

int main(int argc, char const *argv[])
{
    const string NameInput = "kavin";
    auto iterator = setContacts.find(Contact(NameInput, 0));
    if (iterator != setContacts.end()) {
        cout << "Found: ";
        iterator->display();
    }
    else {
        cout << "NOT Found!!!" << endl;
    }
    return 0;
}
name=jack, num=23
name=joke, num=0
name=kavin, num=12
name=lisa, num=34
Found: name=kavin, num=12

这里可以看到输入的是("kavin",0)，但是他还是找到了("kavin",12)，因为相等的规则是名字相同就可以

散列表unordered_set

无序的集合，不能重复
但是可以实现查找时间复杂度为常数
unordered_multiset可以存储重复元素
查找、删除、

#include <iostream>
#include <unordered_set>
using namespace std;

template<typename T>
void info(const T& input) {
    cout << "Size=" << input.size() << endl;
    cout << "Max bucket=" << input.max_bucket_count() << endl;
    cout << "Load factor=" << input.load_factor() << endl;
    cout << "INFO: ";
    for (auto& s : input) {
        cout << s << " ";
    }
    cout << endl;
}

int main(int argc, char const *argv[])
{
    unordered_set<int> num = {45, 23, 78, 54};
    info(num);
    auto it = num.find(78);
    if (it != num.end()) {
        cout << "Found: " << *it << endl;
    }
    num.erase(it);
    info(num);
    return 0;
}
Size=4  // 当前存储的元素个数
Max bucket=1152921504606846975  // 最大可存储的元素数
Load factor=0.8
INFO: 54 78 23 45 
Found: 78

Size=3
Max bucket=1152921504606846975
Load factor=0.6
INFO: 54 23 45