c++ - 什么是 24 小时分分钟 bool 记录的好数据结构

Question

我的任务是创建一个数据结构，为过去 24 小时的每一分钟保存一个 bool 值。 (事件 X 发生了吗？) 我需要始终保留最后 24 小时。 (也就是说，数据会不断添加，旧数据会弹出。)数据将持久保存到闪存驱动器中。我们在一个嵌入式平台上，但内存并没有那么有限(我有 128MB 可用)，不过碎片化可能会成为一个问题。这是一个实时系统，但由于记录是按分钟计算的，因此几乎没有运行时限制。

界面看起来像这样:

class x_record {
  public:
    // record whether or not x occurred this minute
    void record_entry(bool x_occured);

    // how many minutes has x occured in the last 24hrs? 
    unsigned int x_occurance_minutes() const;

  private:
    // HERE BE DRAGONS 
};

什么是存储实际数据的良好数据结构？我目前最喜欢的是 std::deque<bool>和 24 个 long long 的数组，其中 64 位中的 60 位分别用于一小时的 60 分钟。后者是当前持久性的最爱。

我想我对这两种想法的优缺点有一个很好的了解，但希望你们中的一些人能提供更多的内部信息，甚至更多的想法。

P.S.:这完全是 C++03 + TR1 + Boost 1.52，没有可用的 C++11/14。

Answer 1

详细说明vector<bool>版本，我认为这是个好主意，因为您总是存储相同数量的数据(至少我是这么理解的):

class x_record {
   vector<bool> data;
   unsigned int currentMinute;

public:
   x_record(): data(24*60, false), currentMinute(0){}

   // record whether or not x occurred this minute
   void record_entry(bool x_occured){
      data[currentMinute] = x_occured;
      currentMinute = (currentMinute+1)%data.size();
   }

};

这样， vector 大小是恒定的，所以它不应该被分割(因为它是同时分配的)。您可以使用 currentMinute 跟踪当前分钟多变的。填写所有字段时，只需将其设置为 0与 %(24*60)并覆盖旧数据，因为您不需要它。

您也可以使用普通的数组 代替vector<bool> ，但这将需要更多空间(因为通常 C++ 存储 bool 值的方式与 char 相同)，或者一些位操作——在我看来——重新发明轮子，当我们得到 vector<bool> 时。特化。