C++如何使用STL容器实现数据分组-C++-PHP中文网

C++中高效数据分组首选std::unordered_map<Key, std::vector<Value>>，因其平均O(1)插入和查找性能；若需键有序则用std::map，牺牲性能换顺序；值容器推荐std::vector，内存局部性好；优化时可用指针减少拷贝、reserve预分配内存、自定义哈希函数提升性能，并通过复合键或动态提取器支持多条件分组。

c++如何使用stl容器实现数据分组

C++中利用STL容器进行数据分组，核心思路其实就是构建一个“映射”关系：将一个或多个数据项归属到某个特定的组。最直接且常用的方式是借助关联容器（如

std::map

登录后复制

或

std::unordered_map

登录后复制

），让它们的键（key）代表组的标识，而值（value）则是一个序列容器（如

std::vector

登录后复制

或

std::list

登录后复制

），用来存放属于该组的所有数据项。这种模式非常灵活，能处理各种复杂的数据分组需求。

解决方案

数据分组的实现，通常围绕着一个核心循环展开：遍历原始数据集合，对于每一个数据项，确定它应该属于哪个组，然后将这个数据项添加到对应组的容器中。这里我更倾向于使用

std::unordered_map

登录后复制

，因为它在大多数情况下能提供更好的平均性能，特别是当分组数量较大且不需要保持组的顺序时。

假设我们有一组学生数据，每个学生有ID、姓名和班级，我们想按班级对学生进行分组。

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm> // for std::for_each

// 定义学生结构体
struct Student {
    int id;
    std::string name;
    std::string className;

    // 为了方便打印
    friend std::ostream& operator<<(std::ostream& os, const Student& s) {
        return os << "ID: " << s.id << ", Name: " << s.name << ", Class: " << s.className;
    }
};

// 主函数中进行分组
int main() {
    std::vector<Student> students = {
        {101, "Alice", "Class A"},
        {102, "Bob", "Class B"},
        {103, "Charlie", "Class A"},
        {104, "David", "Class C"},
        {105, "Eve", "Class B"},
        {106, "Frank", "Class A"}
    };

    // 使用unordered_map进行分组，键是班级名称，值是该班级的学生列表
    std::unordered_map<std::string, std::vector<Student>> groupedStudents;

    // 遍历学生数据，将每个学生分到对应的班级组
    for (const auto& student : students) {
        // 如果班级不存在，unordered_map会自动创建，并插入一个空的vector
        // 然后通过push_back将学生添加到对应的vector中
        groupedStudents[student.className].push_back(student);
    }

    // 打印分组结果
    std::cout << "--- Grouped Students by Class ---" << std::endl;
    for (const auto& pair : groupedStudents) {
        std::cout << "Class: " << pair.first << std::endl;
        for (const auto& student : pair.second) {
            std::cout << "  - " << student << std::endl;
        }
        std::cout << std::endl;
    }

    // 假设我们想进一步按学生ID的奇偶性分组（只是一个发散思维的例子）
    std::unordered_map<std::string, std::vector<Student>> groupedByParity;
    for (const auto& student : students) {
        std::string groupKey = (student.id % 2 == 0) ? "Even ID" : "Odd ID";
        groupedByParity[groupKey].push_back(student);
    }

    std::cout << "--- Grouped Students by ID Parity ---" << std::endl;
    for (const auto& pair : groupedByParity) {
        std::cout << "Group: " << pair.first << std::endl;
        for (const auto& student : pair.second) {
            std::cout << "  - " << student << std::endl;
        }
        std::cout << std::endl;
    }

    return 0;
}

登录后复制

这段代码展示了如何利用

std::unordered_map<Key, std::vector<Value>>

登录后复制

的结构来轻松实现数据分组。

[]

登录后复制

操作符的便利性在于，如果键不存在，它会自动插入一个默认构造的值（这里是空的

std::vector<Student>

登录后复制

），然后你就可以直接对其进行操作。

立即学习“C++免费学习笔记（深入）”；

C++中哪些STL容器最适合高效数据分组？

在C++中，要高效地实现数据分组，选择合适的STL容器至关重要。我个人觉得，这主要取决于几个因素：你是否关心分组键的顺序，以及你对查找和插入性能的具体要求。

```
std::unordered_map<Key, std::vector<Value>>
```
登录后复制
: 这是我的首选，也是最常用的组合。
```
unordered_map
```
登录后复制
提供了平均O(1)的查找和插入时间复杂度，这意味着即使数据量很大，分组操作也能保持相当高的效率。它的缺点是键没有特定的顺序，如果你需要按班级名称字母顺序或任何其他逻辑顺序来遍历分组，那么
```
unordered_map
```
登录后复制
就无法直接满足。但对于大多数纯粹的分组场景，性能往往是更重要的考量。
```
std::map<Key, std::vector<Value>>
```
登录后复制
: 如果分组键的顺序对你来说很重要，比如你希望按班级名称的字母顺序来输出分组结果，那么
```
std::map
```
登录后复制
就是更好的选择。
```
map
```
登录后复制
内部使用红黑树实现，保证了键的有序性，但代价是查找和插入的平均时间复杂度为O(logN)。对于数据量不是特别庞大，或者分组数量有限的场景，
```
map
```
登录后复制
的性能也完全足够，而且它的有序性有时候能省去额外的排序步骤。
```
std::vector<std::pair<Key, std::vector<Value>>>
```
登录后复制
和
std::sort
登录后复制
: 这种方式相对不那么直接，但有时也能派上用场。你可以先将所有数据项连同它们的组键一起存储在一个
```
std::vector
```
登录后复制
中，然后对这个
```
vector
```
登录后复制
进行排序，使得相同组键的数据项相邻。排序后，你就可以遍历这个已排序的
```
vector
```
登录后复制
，将相邻的相同组键的数据项收集到一起。这种方法的优点是内存局部性可能更好，但缺点是需要进行一次全局排序，时间复杂度通常是O(N log N)，而且后续访问特定组的数据不如
```
map
```
登录后复制
/
```
unordered_map
```
登录后复制
那样直接。不过，如果你的数据量不大，或者分组键的数量非常少，这种方法也未尝不可。我通常在数据量小，或者需要对分组键进行复杂自定义排序时才会考虑它。

至于值容器，

std::vector<Value>

登录后复制

几乎总是最佳选择，因为它提供了良好的缓存局部性，并且在大多数情况下，向末尾添加元素（

push_back

登录后复制

）的开销很小。如果你的分组内部需要频繁在中间插入或删除元素，那么

std::list<Value>

登录后复制

或

std::deque<Value>

登录后复制

可能会更合适，但这种情况在数据分组中相对少见。

腾讯智影-AI数字人

基于AI数字人能力，实现7*24小时AI数字人直播带货，低成本实现直播业务快速增增，全天智能在线直播

查看详情

优化复杂数据结构分组时的性能与内存

处理复杂数据结构的分组，不仅仅是选择对的容器那么简单，性能和内存往往是相互关联的挑战。在我处理过的项目中，尤其是一些需要实时响应的后端服务，这方面的优化经验告诉我，几个关键点值得深入思考。

首先，减少不必要的拷贝是重中之重。如果你的

Value

登录后复制

类型（比如上面例子中的

Student

登录后复制

）是一个很大的结构体或对象，每次把它从原始集合拷贝到分组容器中，都会带来显著的性能开销和内存占用。

存储指针或智能指针：与其直接存储
```
Student
```
登录后复制
对象，不如存储
```
Student*
```
登录后复制
或
```
std::shared_ptr<Student>
```
登录后复制
。这样，分组容器中存储的就只是指针大小的数据，大大减少了拷贝开销。当然，你需要自己管理这些对象的生命周期，或者使用智能指针来自动化管理。例如：
```
std::unordered_map<std::string, std::vector<std::shared_ptr<Student>>>
```
登录后复制
。
利用
std::move
登录后复制
：如果原始数据集合在分组后就不再需要，或者你可以接受它被“掏空”，那么在将数据项插入到分组容器时，使用
```
std::move
```
登录后复制
可以避免拷贝，直接将资源所有权转移过去。这对于那些具有移动构造函数和移动赋值函数的大对象来说，效率提升非常明显。

// 示例：使用std::move
// 假设 originalStudents 是一个临时的、可以被移动的vector
std::vector<Student> originalStudents = { /* ... */ };
std::unordered_map<std::string, std::vector<Student>> groupedStudents;

for (auto& student : originalStudents) { // 注意这里是引用
    groupedStudents[student.className].push_back(std::move(student));
}
// 此时 originalStudents 中的 Student 对象可能处于“有效但未指定状态”
// 它们的内容已经被移动走了

登录后复制

其次，预分配内存可以显著提升

std::vector

登录后复制

作为值容器的性能。当你向

vector

登录后复制

中不断

push_back

登录后复制

元素时，如果容量不足，

vector

登录后复制

会重新分配更大的内存，并将现有元素拷贝过去，这开销不小。

如果你能大致估计每个组会有多少数据项，或者总共有多少数据项，可以考虑在创建
```
vector
```
登录后复制
时就调用
```
reserve()
```
登录后复制
。例如，
```
groupedStudents[className].reserve(estimatedGroupSize);
```
登录后复制
。虽然精确估计很难，但哪怕是粗略的预留，也比每次扩容要好。对于
```
std::unordered_map
```
登录后复制
本身，如果你能预估分组的数量，也可以通过
```
reserve(num_groups)
```
登录后复制
来预留桶（buckets），减少哈希冲突和重新散列的次数。

再者，自定义哈希函数和相等比较对于

std::unordered_map

登录后复制

处理复杂键类型至关重要。如果你的分组键不是简单的

int

登录后复制

、

string

登录后复制

等，而是一个自定义的结构体，那么你需要为它提供一个

std::hash

登录后复制

特化或作为模板参数传入自定义哈希函数，以及

operator==

登录后复制

重载。一个好的哈希函数能有效减少冲突，从而维持

unordered_map

登录后复制

的O(1)平均性能。一个糟糕的哈希函数可能导致大量冲突，使其性能退化到O(N)。

// 示例：自定义结构体作为unordered_map的键
struct CompositeKey {
    std::string dept;
    int year;

    bool operator==(const CompositeKey& other) const {
        return dept == other.dept && year == other.year;
    }
};

// 为CompositeKey定义哈希函数
struct CompositeKeyHash {
    std::size_t operator()(const CompositeKey& k) const {
        // 组合哈希值，避免简单相加
        // std::hash<std::string>()(k.dept) ^ (std::hash<int>()(k.year) << 1) 是一种常见组合方式
        return std::hash<std::string>()(k.dept) ^ (std::hash<int>()(k.year) << 1);
    }
};

// 使用自定义键和哈希函数
std::unordered_map<CompositeKey, std::vector<Student>, CompositeKeyHash> groupedByDeptAndYear;

登录后复制

最后，选择合适的数据表示。有时候，你可能不需要将整个

Student

登录后复制

对象都存储在分组容器中，也许只需要存储它们的ID。这样可以大大减少每个

vector

登录后复制

的内存占用。例如：

std::unordered_map<std::string, std::vector<int>>

登录后复制

（只存储学生ID）。这完全取决于你的后续操作需要哪些数据。这种“瘦身”策略，在数据量巨大时，效果会非常明显。

处理多重条件或动态分组逻辑

在实际应用中，数据分组的条件往往不是单一的，或者分组逻辑可能需要根据运行时参数动态调整。这其实是更贴近真实世界复杂性的场景，我经常遇到。

一个常见的情况是多重条件分组。比如，我们不仅要按班级分组，还要在每个班级内部，再按学生的性别分组。最直接的办法是创建复合键。

std::pair

登录后复制

是一个非常方便的复合键类型，但如果你有三个或更多条件，可能就需要自定义一个结构体作为键了。

// 示例：按班级和性别分组
struct StudentInfo {
    int id;
    std::string name;
    std::string className;
    std::string gender; // "Male" or "Female"

    // ... (operator<<)
};

// 复合键：班级名 + 性别
struct ClassGenderKey {
    std::string className;
    std::string gender;

    bool operator==(const ClassGenderKey& other) const {
        return className == other.className && gender == other.gender;
    }
};

// 为ClassGenderKey定义哈希函数
struct ClassGenderKeyHash {
    std::size_t operator()(const ClassGenderKey& k) const {
        return std::hash<std::string>()(k.className) ^ (std::hash<std::string>()(k.gender) << 1);
    }
};

// 使用复合键进行分组
std::unordered_map<ClassGenderKey, std::vector<StudentInfo>, ClassGenderKeyHash> groupedByClassAndGender;

std::vector<StudentInfo> students = {
    {101, "Alice", "Class A", "Female"},
    {102, "Bob", "Class B", "Male"},
    {103, "Charlie", "Class A", "Male"},
    {104, "David", "Class C", "Male"},
    {105, "Eve", "Class B", "Female"},
    {106, "Frank", "Class A", "Male"}
};

for (const auto& student : students) {
    ClassGenderKey key = {student.className, student.gender};
    groupedByClassAndGender[key].push_back(student);
}

// 打印结果...

登录后复制

这种方式直观且高效，但需要为每个新的复合键类型定义哈希函数和相等比较操作符，这可能有点重复。

另一个更灵活的场景是动态分组逻辑。假设分组条件不是硬编码的，而是根据用户输入或配置文件来决定。这时，你可以将“如何提取分组键”的逻辑抽象成一个函数对象（functor）或Lambda表达式。

#include <functional> // for std::function

// 假设我们有一个通用的分组函数
template<typename T, typename KeyType, typename KeyExtractor>
std::unordered_map<KeyType, std::vector<T>> groupData(const std::vector<T>& data, KeyExtractor extractor) {
    std::unordered_map<KeyType, std::vector<T>> result;
    for (const auto& item : data) {
        result[extractor(item)].push_back(item);
    }
    return result;
}

// 在main函数中使用
// 按班级分组
auto groupByClass = groupData(students, [](const StudentInfo& s){ return s.className; });

// 按性别分组
auto groupByGender = groupData(students, [](const StudentInfo& s){ return s.gender; });

// 按班级和性别分组（需要返回一个可哈希的复合键）
auto groupByClassAndGenderDynamic = groupData(students, [](const StudentInfo& s){
    return ClassGenderKey{s.className, s.gender}; // 假设ClassGenderKey已定义哈希函数
});

登录后复制

通过这种方式，你可以将分组逻辑与分组的实现细节解耦。

KeyExtractor

登录后复制

可以是一个简单的lambda，也可以是一个复杂的函数对象，它负责从原始数据项中提取出用于分组的键。这大大增强了代码的复用性和灵活性，特别是当你的分组需求频繁变化时。

最后，对于一些更高级的需求，比如层次化分组，即先按一个条件分组，然后在每个组内再按另一个条件分组。这可以通过嵌套的STL容器来实现，例如：

std::unordered_map<std::string, std::unordered_map<std::string, std::vector<StudentInfo>>>

登录后复制

。外层键是班级，内层键是性别。这种结构在访问特定子组时非常高效，但代码可读性可能会有所下降，需要权衡。在我看来，如果层次不深，这种嵌套方式是可行的；如果层次过多，可能需要考虑将数据扁平化，然后用复合键一次性分组，或者设计更通用的数据结构来处理。

以上就是C++如何使用STL容器实现数据分组的详细内容，更多请关注php中文网其它相关文章！