Randomized Queue
(data_structure/randomized_queue.cpp)

• View this file on GitHub
• Last update: 2020-03-11 00:35:25+09:00

Depends on

• other/int_alias.cpp
• other/random_integer.cpp

Verified with

• test/randomized_queue.test.cpp

Code

#include "other/int_alias.cpp"
#include "other/random_integer.cpp"

#include <cassert>
#include <cstddef>
#include <random>
#include <utility>
#include <vector>

template <class T> class randomized_queue {
public:
  using value_type = T;

private:
  std::vector<T> c;

  void select() {
    std::swap(c.back(), c[random_integer<usize>(0, c.size() - 1)]);
  }

public:
  randomized_queue() = default;

  bool empty() const { return c.empty(); }
  usize size() const { return c.size(); }
  T &front() {
    assert(!empty());
    select();
    return c.back();
  }

  void push(T x) { c.push_back(std::move(x)); }
  T pop() {
    assert(!empty());
    select();
    T ret = std::move(c.back());
    c.pop_back();
    return ret;
  }
};

/**
 * @brief Randomized Queue
 */

#line 2 "other/int_alias.cpp"

#include <cstddef>
#include <cstdint>

using i32 = std::int32_t;
using i64 = std::int64_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;
using isize = std::ptrdiff_t;
using usize = std::size_t;
#line 2 "other/random_integer.cpp"

#include <random>
#include <type_traits>

template <class T, class... Args>
using any_of_is_same = std::disjunction<std::is_same<T, Args>...>;

template <class IntType = int>
IntType random_integer(const IntType a, const IntType b) {
  static_assert(
      any_of_is_same<IntType, short, int, long, long long, unsigned short,
                     unsigned int, unsigned long, unsigned long long>::value);
  static std::default_random_engine g(91);
  return std::uniform_int_distribution<IntType>(a, b)(g);
}
#line 3 "data_structure/randomized_queue.cpp"

#include <cassert>
#line 7 "data_structure/randomized_queue.cpp"
#include <utility>
#include <vector>

template <class T> class randomized_queue {
public:
  using value_type = T;

private:
  std::vector<T> c;

  void select() {
    std::swap(c.back(), c[random_integer<usize>(0, c.size() - 1)]);
  }

public:
  randomized_queue() = default;

  bool empty() const { return c.empty(); }
  usize size() const { return c.size(); }
  T &front() {
    assert(!empty());
    select();
    return c.back();
  }

  void push(T x) { c.push_back(std::move(x)); }
  T pop() {
    assert(!empty());
    select();
    T ret = std::move(c.back());
    c.pop_back();
    return ret;
  }
};

/**
 * @brief Randomized Queue
 */

Back to top page