dq.cpp

#include <algorithm>
#include <deque>
#include <iostream>
#include <sys/time.h>
#include <time.h>
#include <vector>

double gettimeofday_sec() {
  struct timeval tv;
  gettimeofday(&tv, NULL);
  return tv.tv_sec + (double)tv.tv_usec * 1e-6;
}

/*
 * g++ dq.cpp -O3 --std=c++0x && ./a.out
 *
 * Num elems: 1     Ratio      2.194
 * Num elems: 10    Ratio      1.771
 * Num elems: 20    Ratio      1.753
 * Num elems: 100   Ratio      1.690
 * Num elems: 500   Ratio      1.858
 */

int main() {
  const int kNumOps = 1000000;
  std::vector<int> num_elements = {1, 10, 20, 100, 500};

  for (int num : num_elements) {
    std::vector<int> v_operands;
    std::deque<int> d_operands;

    // Vector test
    auto vec_start = gettimeofday_sec();
    unsigned long long vec_total = 0;
    for (int i = 0; i < kNumOps; i++) {
      v_operands.clear();
      for (int j = 0; j < num; j++) {
        v_operands.push_back(i + j);
      }
      std::reverse(v_operands.begin(), v_operands.end());
      vec_total += v_operands.back();
    }
    auto vec_end = gettimeofday_sec();

    // Deque test
    auto deq_start = gettimeofday_sec();
    unsigned long long deq_total = 0;
    for (int i = 0; i < kNumOps; i++) {
      d_operands.clear();
      for (int j = 0; j < num; j++) {
        d_operands.emplace_front(i + j);
      }
      deq_total += d_operands.back();
    }
    auto deq_end = gettimeofday_sec();

    // Ratio
    printf("Num elems: %d \t Ratio %10.3f\n", num,
           (deq_end - deq_start) / (vec_end - vec_start));
  }
  return 0;
}