C++_STL — queue (and priority_queue)

Reference: the queue

The queue:

template <class T.class Container = deque<T> > class queue;
Copy the code

Fifo queue

Parameters:

T: element type

Container: Type of the inner underlying Container object that stores elements.

Constructor STD ::queue::queue

initialize (1)	explicit queue (const container_type& ctnr);
move-initialize (2)	explicit queue (container_type&& ctnr = container_type());
allocator (3)	template <class Alloc> explicit queue (const Alloc& alloc);
init + allocator (4)	template <class Alloc> queue (const container_type& ctnr, const Alloc& alloc);
move-init + allocator (5)	template <class Alloc> queue (container_type&& ctnr, const Alloc& alloc);
copy + allocator (6)	template <class Alloc> queue (const queue& x, const Alloc& alloc);
move + allocator (7)	template <class Alloc> queue (queue&& x, const Alloc& alloc);

1.1 features

1, Initialize the constructor:

Construct a container adapter whose internal container is initialized as a copy of CTNR.

Move the initialization constructor:

Construct a container adapter whose inner container constructs it by moving to get the value of CTNR.

3. Allocator constructor:

Construct a container adapter whose inner container is constructed with alloc as a parameter.

Initialize with allocator constructor

Construct a container adapter whose inner container is constructed with CNTR and alloc as parameters.

Move initialization using the allocator constructor

Construct a container adapter whose internal container is constructed with STD :: Move (CNTR) and alloc as arguments.

Use the allocator constructor to copy:

Construct a container adapter whose inner container is constructed with the inner container of x as the first argument and alloc as the second argument.

Move with allocator constructor:

Construct a container adapter whose inner container is constructed by moving the inner container of X as the first argument and passing alloc as the second argument.

// constructing queues
#include <iostream>       // std::cout
#include <deque>          // std::deque
#include <list>           // std::list
#include <queue>          // std::queue

int main (a)
{
  std::deque<int> mydeck (3.100);        // deque with 3 elements
  std::list<int> mylist (2.200);         // list with 2 elements

  std::queue<int> first;                 // empty queue
  std::queue<int> second (mydeck);       // queue initialized to copy of deque

  std::queue<int,std::list<int> > third; // empty queue with list as underlying container
  std::queue<int,std::list<int> > fourth (mylist);

  std::cout << "size of first: " << first.size() < <'\n';
  std::cout << "size of second: " << second.size() < <'\n';
  std::cout << "size of third: " << third.size() < <'\n';
  std::cout << "size of fourth: " << fourth.size() < <'\n';

  return 0;
}
Copy the code

2, STD: : queue: : back

reference& back(a);
const_reference& back(a) const;
Copy the code

2.1 features

Returns a reference to the last element in the queue. This is the “latest” element in the queue (that is, the last element pushed into the queue).

2.2 the return value

A reference to the last element in the queue.

// queue::back
#include <iostream>       // std::cout
#include <queue>          // std::queue

int main (a)
{
  std::queue<int> myqueue;

  myqueue.push(12);
  myqueue.push(75);   // this is now the back

  myqueue.back() -= myqueue.front(a); std::cout <<"myqueue.back() is now " << myqueue.back() < <'\n';

  return 0;
}
Copy the code

3, STD: : queue: : emplace

template <class... Args> void emplace (Args&&... args);
Copy the code

3.1 features

Adds a new element to the end of the queue, after its current last element. The new element is constructed in place with ARgs as an argument to its constructor.

3.2 parameter

Constructor argument

// queue::emplace
#include <iostream>       // std::cin, std::cout
#include <queue>          // std::queue
#include <string>         // std::string, std::getline(string)

int main (a)
{
  std::queue<std::string> myqueue;

  myqueue.emplace ("First sentence");
  myqueue.emplace ("Second sentence");

  std::cout << "myqueue contains:\n";
  while(! myqueue.empty())
  {
    std::cout << myqueue.front() < <'\n';
    myqueue.pop(a); }return 0;
}
Copy the code

4, STD: : queue: : empty

bool empty(a) const;
Copy the code

4.1 features

Checks whether the queue is empty

4.2 the return value

True if the size of the underlying container is 0, false otherwise.

// queue::empty
#include <iostream>       // std::cout
#include <queue>          // std::queue

int main (a)
{
  std::queue<int> myqueue;
  int sum (0);

  for (int i=1; i<=10; i++) myqueue.push(i);

  while(! myqueue.empty())
  {
     sum += myqueue.front(a); myqueue.pop(a); } std::cout <<"total: " << sum << '\n';

  return 0;
}
Copy the code

5, STD: : queue: : front

 reference& front(a);
const_reference& front(a) const;
Copy the code

5.1 features

Returns a reference to the header element

5.2 the return value

A reference to the header element

// queue::front
#include <iostream>       // std::cout
#include <queue>          // std::queue

int main (a)
{
  std::queue<int> myqueue;

  myqueue.push(77);
  myqueue.push(16);

  myqueue.front() -= myqueue.back(a);/ / 77-16 = 61

  std::cout << "myqueue.front() is now " << myqueue.front() < <'\n';

  return 0;
}
Copy the code

6, STD: : queue: : pop

void pop(a);
Copy the code

6.1 features

Pops up the queue header element and removes the queue header element, effectively reducing its size by one.

// queue::push/pop
#include <iostream>       // std::cin, std::cout
#include <queue>          // std::queue

int main (a)
{
  std::queue<int> myqueue;
  int myint;

  std::cout << "Please enter some integers (enter 0 to end):\n";

  do {
    std::cin >> myint;
    myqueue.push (myint);
  } while (myint);

  std::cout << "myqueue contains: ";
  while(! myqueue.empty())
  {
    std::cout << ' ' << myqueue.front(a); myqueue.pop(a); } std::cout <<'\n';

  return 0;
}
Copy the code

7, STD: : queue: : push

void push (const value_type& val);
void push (value_type&& val);
Copy the code

7.1 features

Inserts a new element at the end of the queue, after its current last element. The contents of this new element are initialized to val. This member function effectively calls push_back, the member function of the underlying container object.

7.2 parameter

Insert the initialization value of the element.

// queue::push/pop
#include <iostream>       // std::cin, std::cout
#include <queue>          // std::queue

int main (a)
{
  std::queue<int> myqueue;
  int myint;

  std::cout << "Please enter some integers (enter 0 to end):\n";

  do {
    std::cin >> myint;
    myqueue.push (myint);
  } while (myint);

  std::cout << "myqueue contains: ";
  while(! myqueue.empty())
  {
    std::cout << ' ' << myqueue.front(a); myqueue.pop(a); } std::cout <<'\n';

  return 0;
}
Copy the code

8, STD: : queue: : size

size_type size(a) const;
Copy the code

8.1 features

Returns the size of the underlying container

8.2 the return value

Size of the underlying container

// queue::size
#include <iostream>       // std::cout
#include <queue>          // std::queue

int main (a)
{
  std::queue<int> myints;
  std::cout << "0. size: " << myints.size() < <'\n';

  for (int i=0; i<5; i++) myints.push(i);
  std::cout << "1. size: " << myints.size() < <'\n';

  myints.pop(a); std::cout <<"2. size: " << myints.size() < <'\n';

  return 0;
}
Copy the code

9, STD: : queue: : swap

void swap (queue& x) noexcept(/*see below*/);
Copy the code

9.1 features

Swap the contents of this underlying container with x underlying container

// queue::swap
#include <iostream>       // std::cout
#include <queue>          // std::queue

int main (a)
{
  std::queue<int> foo,bar;
  foo.push (10); foo.push(20); foo.push(30);
  bar.push (111); bar.push(222);

  foo.swap(bar);

  std::cout << "size of foo: " << foo.size() < <'\n';
  std::cout << "size of bar: " << bar.size() < <'\n';

  return 0;
}
Copy the code

Priority_queue:

template <class T.class Container = vector<T>,
  class Compare = less<typename Container::value_type> > class priority_queue;
Copy the code

Priority queue

By design, its first element is always the largest of the elements it contains, according to some strict weak sorting criteria. Compare = less, a is less than b, b is at the head of the team, a is at the end of the team

Parameters:

T: type of the element.

Container: Type of the inner underlying Container object that stores elements.

A unary predicate, unlike a function call’s Compare function, is a pseudo-function or functor, which is a class

Be careful not to be confused with constructor arguments

constructor

initialize (1)	priority_queue (const Compare& comp, const Container& ctnr);
range (2)	template <class InputIterator> priority_queue (InputIterator first, InputIterator last, const Compare& comp, const Container& ctnr);
move-initialize (3)	explicit priority_queue (const Compare& comp = Compare(), Container&& ctnr = Container());
move-range (4)	template <class InputIterator> priority_queue (InputIterator first, InputIterator last, const Compare& comp, Container&& ctnr = Container());
allocator versions (5)	template explicit priority_queue (const Alloc& alloc); template priority_queue (const Compare& comp, const Alloc& alloc); template priority_queue (const Compare& comp, const Container& ctnr, const Alloc& alloc); template priority_queue (const Compare& comp, Container&& ctnr, const Alloc& alloc); template priority_queue (const priority_queue& x, const Alloc& alloc); template priority_queue (priority_queue&& x, const Alloc& alloc);

1.1 parameter

Comp: Comparison object used to sort the heap.

CTNR: container object.

First,last: Input iterators to the initial and final positions in the sequence. The elements in this sequence are inserted into the underlying container before sorting.

// constructing priority queues
#include <iostream>       // std::cout
#include <queue>          // std::priority_queue
#include <vector>         // std::vector
#include <functional>     // std::greater

class mycomparison
{
  bool reverse;
public:
  mycomparison(const bool& revparam=false) {reverse=revparam; }bool operator(a) (const int& lhs, const int&rhs) const
  {
    if (reverse) return (lhs>rhs);
    else return(lhs<rhs); }};int main (a)
{
  int myints[]= {10.60.50.20};

  std::priority_queue<int> first;
  std::priority_queue<int> second (myints,myints+4);
  std::priority_queue<int, std::vector<int>, std::greater<int> >
                            third (myints,myints+4);
  // using mycomparison:
  typedef std::priority_queue<int,std::vector<int>,mycomparison> mypq_type;

  mypq_type fourth;                       // less-than comparison
  mypq_type fifth (mycomparison(true));   // greater-than comparison

  return 0;
}
Copy the code

#include <functional>
#include <queue>
#include <vector>
#include <iostream>
 
template<typename T>
void print_queue(T q) { // NB: pass by value so the print uses a copy
    while(! q.empty()) {
        std::cout << q.top() < <' ';
        q.pop(a); } std::cout <<'\n';
}
 
int main(a) {
    std::priority_queue<int> q;
 
    const auto data = {1.8.5.6.3.4.0.9.7.2};
 
    for(int n : data)
        q.push(n);
 
    print_queue(q);
 
    std::priority_queue<int, std::vector<int>, std::greater<int>>
        q2(data.begin(), data.end());
 
    print_queue(q2);
 
    // Using lambda to compare elements.
    auto cmp = [](double left, double right) { return (int)left<(int)right; };
    std::priority_queue<double, std::vector<double>, decltype(cmp) > q3;
    const auto data1 = {1.1.1.4.2.1.3.4.3.3.4.1.1.8.5.1.3.6.7.7};
    for(double n : data1)
        q3.push(n);
 
    print_queue(q3);
}
Copy the code

Queue All priority_queues except front

2, STD: : priority_queue: : top

const_reference top(a) const;
Copy the code

2.1 features

Returns a constant reference to the top element in priority_queue.

2.2 the return value

Constant reference to the top element.

// priority_queue::top
#include <iostream>       // std::cout
#include <queue>          // std::priority_queue

int main (a)
{
  std::priority_queue<int> mypq;

  mypq.push(10);
  mypq.push(20);
  mypq.push(15);

  std::cout << "mypq.top() is now " << mypq.top() < <'\n';

  return 0;
}
Copy the code

Reference: Queue 295. Median of data streams – LeetCode (leetcode-cn.com)