dioSTL/queue.h at master · V0idk/dioSTL · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
#ifndef _QUEUE_H_
#define _QUEUE_H_

#include "deque.h"
#include "functional.h"
#include "vector.h"

namespace mmm {
// class of queue
template <class T, class Container = mmm::deque<T>> class queue {
public:
  typedef Container container_type;
  typedef typename Container::value_type value_type;
  typedef typename Container::reference reference;
  typedef typename Container::reference const_reference;
  typedef typename Container::size_type size_type;

private:
  Container container_;

public:
  queue() { }
  explicit queue(const container_type &ctnr) : container_(ctnr) {}
  queue( const queue& other ):queue() {
    container_ = other.container_;
  }
  queue( queue&& other ): queue() {
    container_.swap(other.container_);
  }
  bool empty() const { return container_.empty(); }
  size_type size() const { return container_.size(); }
  reference &front() { return container_.front(); }
  const_reference &front() const { return container_.front(); }
  reference &back() { return container_.back(); }
  const_reference &back() const { return container_.back(); }
  void push(const value_type &val) { container_.push_back(val); }
  void pop() { container_.pop_front(); }
  void swap(queue &x) { container_.swap(x.container_); }

public:
  template <class T1, class Container1>
  friend bool operator==(const queue<T1, Container1> &lhs,
                         const queue<T1, Container1> &rhs);
  template <typename T1, typename Container1>
  friend bool operator<(const queue<T1, Container1> &,
                        const queue<T1, Container1> &);
};

template <class T, class Container>
bool operator==(const queue<T, Container> &lhs,
                const queue<T, Container> &rhs) {
  return lhs.container_ == rhs.container_;
}
template <class T, class Container>
bool operator!=(const queue<T, Container> &lhs,
                const queue<T, Container> &rhs) {
  return !(lhs == rhs);
}

template <typename T, typename Container>
inline bool operator<(const queue<T, Container> &x,
                      const queue<T, Container> &y) {
  return x.c < y.c;
}

template <typename T, typename Container>
inline bool operator>(const queue<T, Container> &x,
                      const queue<T, Container> &y) {
  return y < x;
}

template <typename T, typename Container>
inline bool operator<=(const queue<T, Container> &x,
                       const queue<T, Container> &y) {
  return !(y < x);
}

template <typename T, typename Container>
inline bool operator>=(const queue<T, Container> &x,
                       const queue<T, Container> &y) {
  return !(x < y);
}

template <class T, class Container>
void swap(queue<T, Container> &x, queue<T, Container> &y) {
  x.swap(y);
}

/**************class of priority_queue************************/
//不过是push/pop时进行堆维护而已
//注意默认容器为vector.因为堆算法函数用的是swap,而非修改指针.
template <class T, class Container = mmm::vector<T>,
          class Compare = mmm::less<typename Container::value_type>>
class priority_queue {
public:
  typedef typename Container::value_type value_type;
  typedef Container container_type;
  typedef typename Container::reference reference;
  typedef typename Container::const_reference const_reference;
  typedef typename Container::size_type size_type;

private:
  container_type container_;
  Compare compare_;

public:
  priority_queue() : priority_queue(Compare(), Container()) { }

  explicit priority_queue(const Compare& compare)
      : priority_queue(compare, Container()) { }

  explicit priority_queue(const Compare &comp,
                          const Container &ctnr)
      : container_(ctnr), compare_(comp) {}
  template <class InputIterator>
  priority_queue(InputIterator first, InputIterator last,
                 const Compare &comp = Compare(),
                 const Container &ctnr = Container())
      : container_(ctnr), compare_(comp) {
    container_.insert(container_.end(), first, last);
    mmm::make_heap(container_.begin(), container_.end());
  }
  bool empty() const { return container_.empty(); }
  size_type size() const { return container_.size(); }
  reference top() { return container_.front(); }

  void push(const value_type &val) {
    container_.push_back(val);
    mmm::push_heap(container_.begin(), container_.end(), compare_);
  }
  void pop() {
    mmm::pop_heap(container_.begin(), container_.end(), compare_);
    container_.pop_back();
  }
  void swap(priority_queue &x) {
    container_.swap(x.container_);
    // mmm::swap(container_, x.container_);
    mmm::swap(compare_, x.compare_);
  }
};
template <class T, class Container, class Compare>
void swap(priority_queue<T, Container, Compare> &x,
          priority_queue<T, Container, Compare> &y) {
  x.swap(y);
}
} // namespace mmm

#endif