如何在指定范围内开发一个 class 到 return 唯一数字？

Question

我需要制定一个class到return指定范围内的唯一号码。例如，如果指定范围是 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() 编辑的号码 return 调用 ReleaseNumber()，它将被释放并通过 ReleaseNextExpiredNumber() 方法 return 编辑。

// 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

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

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() 推到该向量上：

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() 的问题：如果过期，return releaseNumber()，否则 return -1。

Answer 2

首先，由于您使用的是连续的数字序列，因此您可以只使用数组将每个数字映射到一段数据：

dataArray[number - min] = whateverData;

其中 dataArray 有 max - min - 1 个元素（因为两个边界都包括在内）。

其次，您可以使用一个简单的 bool 数组来确定数字是否可用（bool[] 或 std::vector<bool> 都可以）。

就跟踪过期而言，您需要使用 time function for getting timestamps, and an array of time_t 结构来存储每个号码的过期时间。然后，您的 ReleaseNextExpiredNumber 可能看起来像这样：

time_t curTime = time(NULL); // get current time
for (int num = min; num <= max; num++) // or whatever number type you want
{
    if (available[num - min]) // skip available numbers
        continue;
    if (expirationTimes[num - min] > curTime) // you can compare via difftime
    {
        // release the number
        ReleaseNumber(num);
        return num;
    }
}
// nothing expired
return -1;

GetNextNumber 相当简单：

time_t curTime = time();
for (int num = min; num <= max; num++)
{
    if (!available[num - min])) // skip unavailable numbers
        continue;
    // mark as used
    available[num - min] = false;
    // compute expiration time
    expirationTimes[num - min] = curTime + expirationTime; // or whatever function to add seconds to a time_t
    // return it
    return num;
}
// nothing available
return -1;

Answer 3

这是一个有趣的问题，主要是因为很难维护时间队列和可用数量。我决定把它们分开。

此外，如果您希望有大量可用数字，那么循环缓冲区可能会比我的实现更好。

您有 min 和 max 作为 public 变量。我认为你做不到。如果其中一个发生变化，您将需要更新所有内容，可能会导致丢掉所有数字。在我的实现中，我刚刚将它们设为 const.

无论如何，这是我想出的：

class MyClass{
public:
    MyClass(int min, int max, int expirationTime) : _min(min), _max(max), _expirationTime(expirationTime), _isAvailable(_max - _min + 1, true) {}

    int getExpirationTime() const { return _expirationTime; }

    void setExpirationTime(int expirationTime){ _expirationTime = expirationTime; }

    int getNextNumber(){
        auto it = find(_isAvailable.begin(), _isAvailable.end(), true);
        auto result = it == _isAvailable.end() ? -1 : distance(_isAvailable.begin(), it) + _min;

        if (result > 0){
            *it = false;
            _fifo.push_back(make_pair(time(nullptr), result));
        }
        return result;
    }

    void releaseNumber(int number){
        assert(number >= _min && number <= _max);
        _isAvailable[number - _min] = true;
        _fifo.erase(find_if(_fifo.begin(), _fifo.end(), [&](const pair<time_t, int> i){ return i.second == number; }));
    }

    int releaseNextExpiredNumber(){
        auto result = -1;

        if(!_fifo.empty() && _fifo.front().first <= time(nullptr) + _expirationTime){
            result = _fifo.front().second;
            _isAvailable[result - _min] = true;
            _fifo.pop_front();
        }
        return result;
    }
private:
    const int _min;
    const int _max;
    int _expirationTime;
    vector<bool> _isAvailable;
    deque<pair<time_t, int>> _fifo;
};

如何在指定范围内开发一个 class 到 return 唯一数字？

How can I develop a class to return unique numbers in the specified range?

c++

data-structures