Movatterモバイル変換


[0]ホーム

URL:


cppreference.com
Namespaces
Variants
    Actions

      std::priority_queue

      From cppreference.com
      <cpp‎ |container
       
       
       
       
      Defined in header<queue>
      template<

         class T,
         class Container=std::vector<T>,
         class Compare=std::less<typename Container::value_type>

      >class priority_queue;

      Thepriority queue is acontainer adaptor that provides constant time lookup of the largest (by default) element, at the expense of logarithmic insertion and extraction.

      A user-providedCompare can be supplied to change the ordering, e.g. usingstd::greater<T> would cause the smallest element to appear as thetop().

      Working with apriority_queue is similar to managing aheap in some random access container, with the benefit of not being able to accidentally invalidate the heap.

      All member functions ofstd::priority_queue areconstexpr: it is possible to create and usestd::priority_queue objects in the evaluation of a constant expression.

      However,std::priority_queue objects generally cannot beconstexpr, because any dynamically allocated storage must be released in the same evaluation of constant expression.

      (since C++26)

      Contents

      [edit]Template parameters

      T - The type of the stored elements. The program is ill-formed ifT is not the same type asContainer::value_type.
      Container - The type of the underlying container to use to store the elements. The container must satisfy the requirements ofSequenceContainer, and its iterators must satisfy the requirements ofLegacyRandomAccessIterator. Additionally, it must provide the following functions with theusual semantics:

      The standard containersstd::vector (not includingstd::vector<bool>) andstd::deque satisfy these requirements.

      Compare - ACompare type providing a strict weak ordering.

      Note that theCompare parameter is defined such that it returnstrue if its first argument comesbefore its second argument in a weak ordering. But because the priority queue outputs largest elements first, the elements that "come before" are actually output last. That is, the front of the queue contains the "last" element according to the weak ordering imposed byCompare.

      [edit]Member types

      Member type Definition
      container_typeContainer[edit]
      value_compareCompare
      value_typeContainer::value_type[edit]
      size_typeContainer::size_type[edit]
      referenceContainer::reference[edit]
      const_referenceContainer::const_reference[edit]

      [edit]Member objects

      Member name Definition
      Container c
      the underlying container
      (protected member object)[edit]
      Compare comp
      the comparison function object
      (protected member object)

      [edit]Member functions

      constructs thepriority_queue
      (public member function)[edit]
      destructs thepriority_queue
      (public member function)[edit]
      assigns values to the container adaptor
      (public member function)[edit]
      Element access
      accesses the top element
      (public member function)[edit]
      Capacity
      checks whether the container adaptor is empty
      (public member function)[edit]
      returns the number of elements
      (public member function)[edit]
      Modifiers
      inserts element and sorts the underlying container
      (public member function)[edit]
      (C++23)
      inserts a range of elements and sorts the underlying container
      (public member function)[edit]
      (C++11)
      constructs element in-place and sorts the underlying container
      (public member function)[edit]
      removes the top element
      (public member function)[edit]
      (C++11)
      swaps the contents
      (public member function)[edit]

      [edit]Non-member functions

      specializes thestd::swap algorithm
      (function template)[edit]

      [edit]Helper classes

      specializes thestd::uses_allocator type trait
      (class template specialization)[edit]
      formatting support forstd::priority_queue
      (class template specialization)[edit]

      Deduction guides

      (since C++17)

      [edit]Notes

      Feature-test macroValueStdFeature
      __cpp_lib_containers_ranges202202L(C++23)Ranges-aware construction and insertion for containers
      __cpp_lib_constexpr_queue202502L(C++26)constexprstd::priority_queue

      [edit]Example

      Run this code
      #include <functional>#include <iostream>#include <queue>#include <string_view>#include <vector> template<typename T>void pop_println(std::string_view rem, T& pq){std::cout<< rem<<": ";for(;!pq.empty(); pq.pop())std::cout<< pq.top()<<' ';std::cout<<'\n';} template<typename T>void println(std::string_view rem,const T& v){std::cout<< rem<<": ";for(constauto& e: v)std::cout<< e<<' ';std::cout<<'\n';} int main(){constauto data={1,8,5,6,3,4,0,9,7,2};    println("data", data);     std::priority_queue<int> max_priority_queue; // Fill the priority queue.for(int n: data)        max_priority_queue.push(n);     pop_println("max_priority_queue", max_priority_queue); // std::greater<int> makes the max priority queue act as a min priority queue.    std::priority_queue<int,std::vector<int>,std::greater<int>>        min_priority_queue1(data.begin(), data.end());     pop_println("min_priority_queue1", min_priority_queue1); // Second way to define a min priority queue.    std::priority_queue min_priority_queue2(data.begin(), data.end(),std::greater<int>());     pop_println("min_priority_queue2", min_priority_queue2); // Using a custom function object to compare elements.struct{bool operator()(constint l,constint r)const{return l> r;}} customLess;     std::priority_queue custom_priority_queue(data.begin(), data.end(), customLess);     pop_println("custom_priority_queue", custom_priority_queue); // Using lambda to compare elements.auto cmp=[](int left,int right){return(left^1)<(right^1);};    std::priority_queue<int,std::vector<int>, decltype(cmp)> lambda_priority_queue(cmp); for(int n: data)        lambda_priority_queue.push(n);     pop_println("lambda_priority_queue", lambda_priority_queue);}

      Output:

      data: 1 8 5 6 3 4 0 9 7 2max_priority_queue: 9 8 7 6 5 4 3 2 1 0min_priority_queue1: 0 1 2 3 4 5 6 7 8 9min_priority_queue2: 0 1 2 3 4 5 6 7 8 9custom_priority_queue: 0 1 2 3 4 5 6 7 8 9lambda_priority_queue: 8 9 6 7 4 5 2 3 0 1

      [edit]Defect reports

      The following behavior-changing defect reports were applied retroactively to previously published C++ standards.

      DRApplied toBehavior as publishedCorrect behavior
      LWG 307C++98Container could not bestd::vector<bool>allowed
      LWG 2566C++98Missing the requirement forContainer::value_typeill-formed ifT is not the same type asContainer::value_type
      LWG 2684C++98priority_queue takes a comparator
      but lacked member typedef for it
      added

      [edit]See also

      resizable contiguous array
      (class template)[edit]
      space-efficient dynamic bitset
      (class template specialization)[edit]
      double-ended queue
      (class template)[edit]
      Retrieved from "https://en.cppreference.com/mwiki/index.php?title=cpp/container/priority_queue&oldid=182868"

      [8]ページ先頭

      ©2009-2025 Movatter.jp