cpp_container.rst

Container

Priority Queue

Table of Contents

• Priority Queue
• Priority Queue
• Profiling
  • Push Front
  • Push Back
  • Pop Front
  • Pop Back

Priority Queue

#include <iostream>
#include <functional>
#include <vector>
#include <queue>

template<typename Q>
void dump(Q &q) {
  while(!q.empty()) {
    std::cout << q.top() << " ";
    q.pop();
  }
  std::cout << "\n";
}

void foo() {
  std::vector<int> data{1, 5, 2, 1, 3};
  std::priority_queue<int> queue;
  for (auto & x : data) { queue.push(x); }
  dump(queue);
}

void bar() {
  std::vector<int> data{1, 5, 2, 1, 3};
  std::priority_queue<int, std::vector<int>, std::greater<int>> queue;
  for (auto & x : data) { queue.push(x); }
  dump(queue);
}

void baz() {
  std::vector<int> data{1, 5, 2, 1, 3};
  auto cmp = [](int x, int y) { return x < y; };
  std::priority_queue<int, std::vector<int>, decltype(cmp)> queue(cmp);
  for (auto & x : data) { queue.push(x); }
  dump(queue);
}

int main(int argc, char *argv[]) {
  foo();
  bar();
  baz();
  // 5 3 2 1 1
  // 1 1 2 3 5
  // 1 1 2 3 5
}

Priority queue is useful when a programmer need to merge multiple lists of data in order.

#include <iostream>
#include <vector>
#include <queue>

template<typename Q>
void dump(Q &q) {
  while(!q.empty()) {
    std::cout << q.top() << " ";
    q.pop();
  }
  std::cout << "\n";
}

int main(int argc, char *argv[]) {
  std::priority_queue<int> queue;
  std::vector<int> x{9, 7, 8};
  std::vector<int> y{0, 5, 3};
  for (auto &e : x) { queue.push(e); }
  for (auto &e : y) { queue.push(e); }
  dump(queue);
  // 9 8 7 5 3 0
}

Profiling

// profile.h
#include <iostream>
#include <chrono>

using milliseconds = std::chrono::milliseconds;

template <typename T, typename F>
void profile(T &t, F &func) {
  const auto start = std::chrono::steady_clock::now();
  func(t);
  const auto end = std::chrono::steady_clock::now();
  const auto d = end - start;
  const auto mill = std::chrono::duration_cast<milliseconds>(d).count();
  std::cout << mill << " ms\n";
}

Push Front

// g++ -O3 -std=c++17 -Wall -Werror -I${HDR} a.cpp

#include <vector>
#include <deque>
#include <list>
#include <range/v3/view/iota.hpp>
#include "profile.h"

template <typename T>
void insert(T &t) {
  for (auto i : ranges::views::iota(0, 300000)) {
    t.insert(t.begin(), i);
  }
}

int main(int argc, char *argv[]) {
  std::vector<int> v;
  std::deque<int> q;
  std::list<int> l;
  profile(v, insert<decltype(v)>);
  profile(q, insert<decltype(q)>);
  profile(l, insert<decltype(l)>);
}

$ ./a.out
16045 ms
1 ms
6 ms

Push Back

#include <vector>
#include <deque>
#include <list>
#include <range/v3/view/iota.hpp>
#include "profile.h"

template <typename T>
void insert(T &t) {
  for (auto i : ranges::views::iota(0, 1000000)) {
    t.push_back(i);
  }
}

int main(int argc, char *argv[]) {
  std::vector<int> v;
  std::deque<int> q;
  std::list<int> l;
  profile(v, insert<decltype(v)>);
  profile(q, insert<decltype(q)>);
  profile(l, insert<decltype(l)>);
}

./a.out
7 ms
2 ms
39 ms

Pop Front

#include <vector>
#include <deque>
#include <list>
#include <range/v3/view/iota.hpp>
#include "profile.h"

template <typename T>
void insert(T &t) {
  for (auto i : ranges::views::iota(0, 300000)) {
    t.push_back(i);
  }
}

template <typename T>
void pop_front(T &t) {
  while (!t.empty()) {
    t.pop_front();
  }
}

template <typename T>
void erase(T &v) {
  while(!v.empty()) {
    v.erase(v.begin());
  }
}

int main(int argc, char *argv[]) {
  std::vector<int> v;
  std::deque<int> q;
  std::list<int> l;
  insert(v); insert(q); insert(l);
  profile(v, erase<decltype(v)>);
  profile(q, pop_front<decltype(q)>);
  profile(l, pop_front<decltype(l)>);
}

$ ./a.out
22923 ms
0 ms
12 ms

Pop Back

#include <vector>
#include <deque>
#include <list>
#include <range/v3/view/iota.hpp>
#include "profile.h"

template <typename T>
void insert(T &t) {
  for (auto i : ranges::views::iota(0, 1000000)) {
    t.push_back(i);
  }
}

template <typename T>
void pop_back(T &t) {
  while (!t.empty()) {
    t.pop_back();
  }
}

int main(int argc, char *argv[]) {
  std::vector<int> v;
  std::deque<int> q;
  std::list<int> l;
  insert(v); insert(q); insert(l);
  profile(v, pop_back<decltype(v)>);
  profile(q, pop_back<decltype(q)>);
  profile(l, pop_back<decltype(l)>);
}

$ ./a.out
0 ms
0 ms
30 ms