是否存在可限制元素最多出现k次的自清理类vector容器？

你需要的这个数据结构可以直接基于STL现有容器二次封装实现，不需要从零开发，以下是两种常用场景的具体实现：

核心设计逻辑 #

• 底层存储直接复用你需要的基础容器（std::vector<T> / std::stack<T>都可），额外搭配一个std::unordered_map<T, size_t>做元素出现次数的全局统计
• 插入元素时自动更新计数，若计数超过预设的k阈值，立刻触发自动清理逻辑删除超出数量的对应元素，同步更新计数保证数据一致性

顺序存储版（类vector<T>） #

#include <vector>
#include <unordered_map>
#include <algorithm>

template <typename T>
class LimitedVector {
private:
    std::vector<T> storage;
    std::unordered_map<T, size_t> count_map;
    size_t max_occurrence; // 对应你要求的k阈值

public:
    explicit LimitedVector(size_t k) : max_occurrence(k) {}

    // 插入元素接口，插入后自动检查是否超阈值
    void push_back(const T& elem) {
        storage.push_back(elem);
        count_map[elem]++;

        if (count_map[elem] > max_occurrence) {
            // 保留最早插入的k个同值元素，删除所有超出部分
            size_t remain = max_occurrence;
            storage.erase(std::remove_if(storage.begin(), storage.end(),
                [&](const T& item) {
                    if (item == elem && remain == 0) return true;
                    if (item == elem) remain--;
                    return false;
                }), storage.end());
            count_map[elem] = max_occurrence;
        }
    }

    // 其他常用接口可直接透传给底层storage实现，示例如下
    size_t size() const { return storage.size(); }
    const T& operator[](size_t idx) const { return storage[idx]; }
};

后进先出版（类stack<T>） #

#include <stack>
#include <unordered_map>

template <typename T>
class LimitedStack {
private:
    std::stack<T> storage;
    std::unordered_map<T, size_t> count_map;
    size_t max_occurrence;

public:
    explicit LimitedStack(size_t k) : max_occurrence(k) {}

    void push(const T& elem) {
        storage.push(elem);
        count_map[elem]++;

        if (count_map[elem] > max_occurrence) {
            // 保留最晚入栈的k个同值元素，删除所有超出部分
            std::stack<T> temp;
            size_t remain = max_occurrence;
            while (!storage.empty()) {
                T top = storage.top();
                storage.pop();
                if (top == elem && remain == 0) continue;
                if (top == elem) remain--;
                temp.push(top);
            }
            // 把保留的数据导回原栈
            while (!temp.empty()) {
                storage.push(temp.top());
                temp.pop();
            }
            count_map[elem] = max_occurrence;
        }
    }

    // 其他常用接口透传示例
    const T& top() const { return storage.top(); }
    void pop() {
        T elem = storage.top();
        count_map[elem]--;
        if (count_map[elem] == 0) count_map.erase(elem);
        storage.pop();
    }
    bool empty() const { return storage.empty(); }
};

注意事项 #

• 如果你用的T类型不支持哈希，可以把std::unordered_map替换为std::map，只需要T支持比较运算符即可
• 对插入性能要求高的场景，可以额外维护每个元素的位置索引列表，清理时直接按位置删除不需要遍历全容器，仅需要牺牲少量内存存储索引
• 上述实现的清理逻辑可按需调整，比如改成超阈值直接删除最新插入的元素，不需要遍历全容器，性能会更高

内容的提问来源于stack exchange，提问作者P.R.F.