c++ 无序容器

无序容器

无序列表不使用比较运算符来组织元素，而是使用哈希函数和关键字类型的==运算符。在关键字没有明显序关系时，使用此类容器会减免维护元素的序代价。

无序容器也有允许重复关键字的版本。使用无序容器替换有序容器会产生的区别在于：输出时的结果顺序会不同。

string word;
while (std::cin >> word) {
  ++word_count[word]; // 提取并递增word的计数器
}
for (const auto& w : word_count) { // 对map中的每个元素
  // 打印元素
  cout << w.first << " occurs " << w.second << ((w.second > 1) ? " times" : " time") << endl;
}

管理桶

无序容器在存储上组织为一组桶，每个桶保存零个或多个元素。无序容器使用哈希函数将元素映射到桶。

关键字类型的要求

默认情况下，无序容器使用关键字类型的==运算符来比较元素，它们还使用一个hash<key_type>类型的对象来生成每个元素的哈希值。

内置类型，string和智能指针类型包含hash模板，因此可以用于定义无序容器。其他类型需提供自己的hash模板。

自定义类类型作为unordered_multiset，需提供函数代替==运算符和哈希值计算函数。1：

class Student {
public:
	Student(string n = "", int a = 0) :name(n), age(a) {}
public:
	string name;
	int age;
};

size_t hasher(const Student& stu) {
	return std::hash<string>()(stu.name);
}

bool eqOp(const Student& stu1, const Student& stu2) {
	return stu1.name == stu2.name;
}

int main()
{
	unordered_multiset<Student, decltype(hasher)*, decltype(eqOp)*> students(42, hasher, eqOp);
	students.insert({ "aaa", 1});

}

写法2：

struct Student {
    string name;
    int id;

    // 重载比较操作符
    bool operator==(const Student& other) const {
        return name == other.name;
    }
};

// 为Student类型提供哈希函数特化
namespace std {
    template <>
    struct hash<Student> {
        size_t operator()(const Student& stu) const {
            return hash<string>()(stu.name);
        }
    };
}

int main() {
    unordered_multiset<Student> students; // 无需显式指定哈希和相等操作函数
    students.insert({ "aaa", 1 });
    
    for (const auto& stu : students) {
        cout << stu.name << " " << stu.id << endl;
    }

    return 0;
}