c++ - 我如何开发一个类来返回指定范围内的唯一数字？

Question

我需要开发一个类来返回指定范围内的唯一数字。例如，如果指定的范围是 1-4，调用 GetNextNumber() 将按如下方式工作:

MyClass obj = new MyClass();
obj->min = 1;
obj->max = 4;
obj->expirationTime = 30; //seconds

int nextNumber = 0;
nextNumber = obj->GetNextNumber(); // returns 1
nextNumber = obj->GetNextNumber(); // returns 2
nextNumber = obj->GetNextNumber(); // returns 3
nextNumber = obj->GetNextNumber(); // returns 4
nextNumber = obj->GetNextNumber(); // returns -1 or throws an exception, becuase all numbers from 1 to 4 have been used.

obj->ReleaseNumber(2); // now that number 2 has been released, it can be used again
nextNumber = obj->GetNextNumber(); // returns 2
nextNumber = obj->GetNextNumber(); // returns -1 or throws an exception, becuase all numbers from 1 to 4 have been used.

如果我们不对从 GetNextNumber() 返回的号码调用 ReleaseNumber()，它将被释放并由 ReleaseNextExpiredNumber() 返回方法。

// after 10 seconds:
int nextExpiredNumber = 0;
nextExpiredNumber = obj->ReleaseNextExpiredNumber(); // returns -1 or throws and exeption because nothing has been expired after 10 seconds
// after 30 seconds
nextExpiredNumber = obj->ReleaseNextExpiredNumber(); // returns 1, because "ReleaseNumber(1)" has not been called within 30 seconds.
// now that number 1 has been released, the `GetNextNumber()` method will return 1:
nextNumber = obj->GetNextNumber(); // returns 1

我打算自己开发这样的类，但在此之前，我想确保我没有重新发明轮子。我还需要这个类是线程安全的。感谢您的任何建议!

Answer 1

处理数字只是插入和弹出容器的问题。我选择了 deque，因为它在 pop_front 和 push_back 上很高效:

class MyClass {
    std::deque<int> numbers;

public:
    MyClass(int lo, int hi) {
        numbers.resize(hi - lo + 1);
        std::iota(numbers.begin(), numbers.end(), lo);
    }

    int getNextNumber() {
        if (!numbers.empty()) {
            int next = numbers[0];
            numbers.pop_front();
            return next;
        }
        else {
            return -1;
        }
    }

    void releaseNumber(int i) {
        numbers.push_back(i);
    }
};

在此基础上添加时间意味着您只有另一个带有时间戳的值容器:

using timestamp = std::chrono::system_clock::time_point; // or whatever
std::vector<std::pair<int, timestamp>> used;

并使 getNextNumber() 推送到该 vector 上:

numbers.pop_front();
used.emplace_back(next, std::chrono::system_clock::now());
return next;

releaseNumber() 从中删除:

auto it = std::find_if(used.begin(), used.end(), 
    [=](const std::pair<int, timestamp>& p){
        return p.first == i;
    });
used.erase(it);

这样，ReleaseNextExpiredNumber() 只是检查 used.front() 的问题:如果它已过期，则返回 releaseNumber() , 否则返回 -1。