What a good data structure for a 24 minute boolean write

Question

I am tasked with creating a data structure that contains a logical value for every minute of the last 24 hours. (Did event X happen?) I need to keep the last 24 hours all the time. (That is, data will be constantly added, old data will be deleted.) Data must be stored on a flash drive. We are on the embedded platform, but the memory is not limited (I have 128 MB), however fragmentation can be a problem. This is a real-time system, but since recording per minute, there are slight run-time limitations.

The interface might look something like this:

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 
};

What would be a good data structure for storing actual data? My favorites are an std::deque<bool>array of 24 long long, with 60 of their 64 bits each being used for 60 minutes per hour. The latter is a favorite for perseverance.

I think I have a pretty good idea of ​​the pros and cons of both ideas, but I hope that some of you can provide additional insights and possibly even more ideas.

PS: This is strictly C ++ 03 + TR1 + Boost 1.52, not C ++ 11/14 available.

Answer 1

, (, , , ), std::bitset<> . , , , , :

class x_record {
  public:
    void record_entry(bool x_occured) {
      record_ <<= 1;
      record_[0] = x_occurred;
    }

    unsigned int x_occurance_minutes() const {
      return record_.count();
    }

    void write_to(std::ostream& os) const {
      os << m_overload_minutes.to_string();
    }

    void read_from(std::istream& is) const {
      std::string bits;
      is >> std::setw(minutes_to_keep) >> bits;
      if( !is || bits.size()!=minutes_to_keep )
        throw std::runtime_error("invalid file format");

      record_ = std::bitset<60*24>(bits);
    }

  private:
    std::bitset<60*24>  record_;
};

, std::bitset<> - , . , .

, ¹ .

, !

¹ , x_occurance_minutes() , record_.count() , record_entry() ( ) .

Answer 2

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();
   }

};

, , ( ). currentMinute. , 0 %(24*60) , .

vector<bool>, ( ++ bool , char), , , , , vector<bool>.

Answer 3

:

int countBits(std::uint32_t v) {
  // source: http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel
  typedef std::uint32_t T;
  v = v - ((v >> 1) & (T)~(T)0/3);                           // temp
  v = (v & (T)~(T)0/15*3) + ((v >> 2) & (T)~(T)0/15*3);      // temp
  v = (v + (v >> 4)) & (T)~(T)0/255*15;                      // temp
  return (T)(v * ((T)~(T)0/255)) >> (sizeof(T) - 1) * CHAR_BIT; // count
}

class x_record {
  public:
    x_record() { std::memset(&history, 0, sizeof(history)); }

    // record whether or not x occurred this minute
    void record_entry(bool x_occured) {
      uint64_t mask = 1 << (bit % 32);
      uint64_t set = x_occured ? mask : 0;
      history[bit / 32] = (history[bit / 32] & ~mask) | set;

      bit = (bit + 1) % (24*60);
    }

    // how many minutes has x occured in the last 24hrs? 
    int x_occurance_minutes() const {
      int count = 0;
      for (int i=0; i<45; ++i) {
        count += countBits(history[i]);
      }
      return count;
    }

  private:
    std::uint32_t history[45];
    short bit = 0;
};

Answer 4

std::vector<bool> . , std::deque<std::vector<bool> >. std::deque<long long>, .

, .

Answer 5

, std::bitset . , . , std::vector<bool> ( , , ). , , 24 * 60 , 24 * 60 .

Answer 6

, 24 , , .

( ):

class x_record {
public:
  // record whether or not x occurred this minute
  void record_entry(bool x_occured) {
    if (x_occured) {
      m_records.insert(getTime());
    }
  }

  // how many minutes has x occured in the last 24hrs? 
  unsigned int x_occurance_minutes() {
    clearRecords();
    return m_records.size();
  }

private:
    time_t getTime() const {
      return time(NULL) / 60; // Get Minute time stamp
    }

    void clearRecords() {
      // Erase all records that happend before the last 24 hours
      time_t frameStart = getTime() - 60*60*24;
      for (std::set<time_t>::iterator it = m_recods.begin(); it != m_records.end(); ++it) {
        if (*it < frameStart) {
          m_records.erase(it);
        } else {
          break;
        }
      }
    }

private:
    std::set<time_t> m_records;
};

, .

, , .

, time_t .

Answer 7

, boost.dynamic_bitset, /.

Dynamic_set handles most of the requirements:

• boost, no C ++ 11
• compact
• handles 24 * 60 bits
• has a count () function to count the set bits
• returns blocks for storage as bits
• no problem with std :: vector container