标准C++库是否有存储Top N值的现成实现？

我自己实现了一个功能完整的Top N存储类，代码如下：

#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>

template <typename T>
class TopNStorage {
    std::priority_queue<T, std::vector<T>, std::greater<T>> counts;
    size_t n;
public: 
    TopNStorage(size_t n) : n(n) {  }

    void add(T value) {
        if (counts.size() >= n) {
            if (value > counts.top()) {
                counts.pop();
                counts.push(value);
            }
        }
        else {
            counts.push(value);
        }
    }

    auto get_values() const { 
        std::vector<T> sorted_collocations_counts(counts.size());

        std::copy(&(counts.top()), &(counts.top()) + counts.size(), sorted_collocations_counts.begin());
        std::sort(sorted_collocations_counts.begin(), sorted_collocations_counts.end());

        return sorted_collocations_counts;
    }
};

int main() {
    TopNStorage<int> storage(3);

    for (int i = 1; i <= 5; ++i) {
        storage.add(i);
    }

    for (auto value : storage.get_values()) {
        std::cout << value << "\n";
    }
}

动机 #

• 不想重复造轮子，这类任务很常见，应该有现成实现；
• 当前实现代码量偏大，希望用更简洁的方式完成；
• 自己的实现还不够通用，需要大量工作完善。

保留事项 #

• N值可能很大，因此不希望先添加值再删除最小元素：虽然那样代码更短，但会带来不必要的计算和内存分配。问题在于std::priority_queue用二叉堆和std::vector作为底层实现：(a) 添加不需要的值会导致过多堆重计算，N大时耗时明显；(b) 若待删除的“额外”值超出已分配vector的容量，会触发重新分配和大量内容复制，N足够大时影响显著。除了自定义内存分配器，没找到简便直接的方式给priority_queue预留容量。如果有改进当前代码且保持现有操作逻辑的思路，欢迎提出。
• 不用过多关注get_values方法，它只是用于演示。

说明 #

本问题与“仅针对给定序列一次性提取N个最小元素”的问题不同，我关注的是新增元素时持续维护Top N值，二者任务和侧重点有明显区别（详见保留事项部分），此前因表述歧义导致问题被误判关闭，特此说明。

标准C++标准库中没有专门用于持续维护Top N值的现成组件，但你可以基于现有STL工具简化实现，同时解决性能问题：

1. 优化现有priority_queue实现 #

你当前的核心逻辑已经高效，可通过继承priority_queue直接操作底层容器来解决内存扩容问题——priority_queue的底层容器是受保护成员c，可以直接调用reserve提前分配足够内存：

template <typename T>
class TopNStorage : private std::priority_queue<T, std::vector<T>, std::greater<T>> {
    using Base = std::priority_queue<T, std::vector<T>, std::greater<T>>;
    size_t n;
public:
    explicit TopNStorage(size_t n) : n(n) {
        // 提前预留容量，避免后续频繁扩容
        this->c.reserve(n);
    }

    void add(T value) {
        if (this->size() >= n) {
            if (value > this->top()) {
                this->pop();
                this->push(value);
            }
        } else {
            this->push(value);
        }
    }

    auto get_values() const {
        std::vector<T> res(this->c.begin(), this->c.end());
        std::sort(res.begin(), res.end());
        return res;
    }
};

这种方式既保留了你原有的高效堆操作逻辑，又通过预分配内存避免了大N场景下的频繁扩容开销。

2. 替代方案：使用std::multiset #

如果对元素有序性有更多需求，std::multiset是更简洁的选择——它本身是有序结构，插入、删除操作时间复杂度为O(logN)，无需额外排序：

template <typename T>
class TopNStorage {
    std::multiset<T> data;
    size_t n;
public:
    explicit TopNStorage(size_t n) : n(n) {}

    void add(T value) {
        if (data.size() >= n) {
            if (value > *data.begin()) {
                data.erase(data.begin());
                data.insert(value);
            }
        } else {
            data.insert(value);
        }
    }

    std::vector<T> get_values() const {
        return {data.begin(), data.end()};
    }
};

该实现代码更简洁，get_values直接返回有序结果，但multiset的内存开销略高于priority_queue，适合对代码简洁性要求更高的场景。

3. 第三方库补充（可选） #

如果允许引入外部依赖，Boost的heap库提供了更灵活的堆实现，支持容量预留、高效元素更新等特性，但这不符合标准库范围内“避免造轮子”的初衷。

总结：标准库没有直接的Top N维护组件，但基于priority_queue（优化内存分配）或multiset可以快速实现高效的Top N存储类，无需完全从零编写。

内容的提问来源于stack exchange，提问作者Damir Tenishev