title: Implementation of a "hits in last [second/minute/hour]" data structure
body: <p>I think this is a fairly common question but I can't seem to find answer by googling around (maybe there's a more precise name for the problem I don't know?)</p>
  
  <p>You need to implement a structure with a "hit()" method used to report a hit and hitsInLastSecond|Minute|Hour methods. You have a timer with say nanosecond accuracy. How do you implement this efficiently?</p>
  
  <p>My thought was something like this (in psuedo-C++)</p>
  
  <pre><code>class HitCounter {
    void hit() {
      hits_at[now()] = ++last_count;
    }
  
    int hitsInLastSecond() {
      auto before_count = hits_at.lower_bound(now() - 1 * second)
      if (before_count == hits_at.end()) { return last_count; }
      return last_count - before_count-&gt;second;
    }
  
    // etc for Minute, Hour
  
    map&lt;time_point, int&gt; hits_at;
    int last_count = 0;
  };
  </code></pre>
  
  <p>Does this work? Is it good? Is something better?</p>
  
  <p>Update: Added pruning and switched to a deque as per comments:</p>
  
  <pre><code>class HitCounter {
    void hit() {
      hits.push_back(make_pair(now(), ++last_count));
    }
  
    int hitsInLastSecond() {
      auto before = lower_bound(hits.begin(), hits.end(), make_pair(now() - 1 * second, -1));
      if (before == hits.end()) { return last_count; }
      return last_count - before_count-&gt;second;
    }
  
    // etc for Minute, Hour
  
    void prune() {
      auto old = upper_bound(hits.begin(). hits.end(), make_pair(now - 1 * hour, -1));
      if (old != hits.end()) {
        hits.erase(hits.begin(), old)
      }
    }
  
    deqeue&lt;pair&lt;time_point, int&gt;&gt; hits;
    int last_count = 0;
  };
  </code></pre>