std::priority_queue pre-allocate memory memory error

Question

I'm working on a deterministic real time project which has an execution cycle per iteration of couple of hundred micro-seconds. I'm facing issue where by the push operation on a std::priority_queue randomly is taking large amount of time. Push operation generally takes around 5-25 micro-seconds but randomly takes 300 micro-seconds to 5 milliseconds.

To overcome this issue, I decided to pre-allocate memory for my std::priority_queue. I'm referring to the following answer: https://stackoverflow.com/a/29236236/6319901 for this regard.

Development OS: Ubuntu 24.04 LTS.
My target OS: vxWorks 7
Language: C++17

Code:

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

struct ipc_receive_t
{
    std::uint32_t   priority;
    int             data1;
    float           data2;
    bool operator<(const ipc_receive_t& object) const //Check if greater
    {
        return this->priority < object.priority;
    }
};


int main(int argc, char const *argv[])
{
    std::cout << "Hello, World!!!\n";
    std::vector<ipc_receive_t> container;
    container.reserve(1000);
    std::priority_queue<ipc_receive_t, std::vector<ipc_receive_t>> pq (
        std::greater<ipc_receive_t>(), std::move(container)
    );
    return 0;
}

Output :

g++ -std=c++17 main.cpp -o main
main.cpp: In function ‘int main(int, const char**)’:
main.cpp:27:9: error: no matching function for call to ‘std::priority_queue<ipc_receive_t, std::vector<ipc_receive_t> >::priority_queue(std::greater<ipc_receive_t>, std::remove_reference<std::vector<ipc_receive_t>&>::type)’
   27 |         );
      |         ^
In file included from /usr/include/c++/14/queue:66,
                 from main.cpp:1:
/usr/include/c++/14/bits/stl_queue.h:691:9: note: candidate: ‘template<class _InputIterator, class _Alloc, class _Requires> std::priority_queue<_Tp, _Sequence, _Compare>::priority_queue(_InputIterator, _InputIterator, const _Compare&, _Sequence&&, const _Alloc&) [with _Alloc = _InputIterator; _Requires = _Alloc; _Tp = ipc_receive_t; _Sequence = std::vector<ipc_receive_t>; _Compare = std::less<ipc_receive_t>]’
  691 |         priority_queue(_InputIterator __first, _InputIterator __last,
      |         ^~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_queue.h:691:9: note:   candidate expects 5 arguments, 2 provided
/usr/include/c++/14/bits/stl_queue.h:679:9: note: candidate: ‘template<class _InputIterator, class _Alloc, class, class _Requires> std::priority_queue<_Tp, _Sequence, _Compare>::priority_queue(_InputIterator, _InputIterator, const _Compare&, const _Sequence&, const _Alloc&) [with _Alloc = _InputIterator; <template-parameter-2-3> = _Alloc; _Requires = <template-parameter-1-3>; _Tp = ipc_receive_t; _Sequence = std::vector<ipc_receive_t>; _Compare = std::less<ipc_receive_t>]’
  679 |         priority_queue(_InputIterator __first, _InputIterator __last,
      |         ^~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_queue.h:679:9: note:   candidate expects 5 arguments, 2 provided
/usr/include/c++/14/bits/stl_queue.h:671:9: note: candidate: ‘template<class _InputIterator, class _Alloc, class, class _Requires> std::priority_queue<_Tp, _Sequence, _Compare>::priority_queue(_InputIterator, _InputIterator, const _Compare&, const _Alloc&) [with _Alloc = _InputIterator; <template-parameter-2-3> = _Alloc; _Requires = <template-parameter-1-3>; _Tp = ipc_receive_t; _Sequence = std::vector<ipc_receive_t>; _Compare = std::less<ipc_receive_t>]’
  671 |         priority_queue(_InputIterator __first, _InputIterator __last,
      |         ^~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_queue.h:671:9: note:   candidate expects 4 arguments, 2 provided
/usr/include/c++/14/bits/stl_queue.h:663:9: note: candidate: ‘template<class _InputIterator, class _Alloc, class, class _Requires> std::priority_queue<_Tp, _Sequence, _Compare>::priority_queue(_InputIterator, _InputIterator, const _Alloc&) [with _Alloc = _InputIterator; <template-parameter-2-3> = _Alloc; _Requires = <template-parameter-1-3>; _Tp = ipc_receive_t; _Sequence = std::vector<ipc_receive_t>; _Compare = std::less<ipc_receive_t>]’
  663 |         priority_queue(_InputIterator __first, _InputIterator __last,
      |         ^~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_queue.h:663:9: note:   candidate expects 3 arguments, 2 provided
/usr/include/c++/14/bits/stl_queue.h:649:9: note: candidate: ‘template<class _InputIterator, class> std::priority_queue<_Tp, _Sequence, _Compare>::priority_queue(_InputIterator, _InputIterator, const _Compare&, _Sequence&&) [with <template-parameter-2-2> = _InputIterator; _Tp = ipc_receive_t; _Sequence = std::vector<ipc_receive_t>; _Compare = std::less<ipc_receive_t>]’
  649 |         priority_queue(_InputIterator __first, _InputIterator __last,
      |         ^~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_queue.h:649:9: note:   candidate expects 4 arguments, 2 provided
/usr/include/c++/14/bits/stl_queue.h:638:9: note: candidate: ‘template<class _InputIterator, class> std::priority_queue<_Tp, _Sequence, _Compare>::priority_queue(_InputIterator, _InputIterator, const _Compare&, const _Sequence&) [with <template-parameter-2-2> = _InputIterator; _Tp = ipc_receive_t; _Sequence = std::vector<ipc_receive_t>; _Compare = std::less<ipc_receive_t>]’
  638 |         priority_queue(_InputIterator __first, _InputIterator __last,
      |         ^~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_queue.h:638:9: note:   candidate expects 4 arguments, 2 provided
/usr/include/c++/14/bits/stl_queue.h:629:9: note: candidate: ‘template<class _InputIterator, class> std::priority_queue<_Tp, _Sequence, _Compare>::priority_queue(_InputIterator, _InputIterator, const _Compare&) [with <template-parameter-2-2> = _InputIterator; _Tp = ipc_receive_t; _Sequence = std::vector<ipc_receive_t>; _Compare = std::less<ipc_receive_t>]’
  629 |         priority_queue(_InputIterator __first, _InputIterator __last,
      |         ^~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_queue.h:629:9: note:   template argument deduction/substitution failed:
main.cpp:27:9: note:   deduced conflicting types for parameter ‘_InputIterator’ (‘std::greater<ipc_receive_t>’ and ‘std::vector<ipc_receive_t>’)
   27 |         );
      |         ^
/usr/include/c++/14/bits/stl_queue.h:594:9: note: candidate: ‘template<class _Alloc, class _Requires> std::priority_queue<_Tp, _Sequence, _Compare>::priority_queue(std::priority_queue<_Tp, _Sequence, _Compare>&&, const _Alloc&) [with _Requires = _Alloc; _Tp = ipc_receive_t; _Sequence = std::vector<ipc_receive_t>; _Compare = std::less<ipc_receive_t>]’
  594 |         priority_queue(priority_queue&& __q, const _Alloc& __a)
      |         ^~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_queue.h:594:9: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/stl_queue.h: In substitution of ‘template<class _Tp, class _Sequence, class _Compare> template<class _Alloc> using std::priority_queue<_Tp, _Sequence, _Compare>::_Uses = typename std::enable_if<std::uses_allocator<_Sequence, _Alloc>::value>::type [with _Alloc = std::vector<ipc_receive_t>; _Tp = ipc_receive_t; _Sequence = std::vector<ipc_receive_t>; _Compare = std::less<ipc_receive_t>]’:
/usr/include/c++/14/bits/stl_queue.h:593:33:   required from here
  593 |       template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
      |                                 ^~~~~~~~
/usr/include/c++/14/bits/stl_queue.h:513:15: error: no type named ‘type’ in ‘struct std::enable_if<false, void>’
  513 |         using _Uses = typename
      |               ^~~~~
/usr/include/c++/14/bits/stl_queue.h:590:9: note: candidate: ‘template<class _Alloc, class _Requires> std::priority_queue<_Tp, _Sequence, _Compare>::priority_queue(const std::priority_queue<_Tp, _Sequence, _Compare>&, const _Alloc&) [with _Requires = _Alloc; _Tp = ipc_receive_t; _Sequence = std::vector<ipc_receive_t>; _Compare = std::less<ipc_receive_t>]’
  590 |         priority_queue(const priority_queue& __q, const _Alloc& __a)
      |         ^~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_queue.h:590:9: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/stl_queue.h:585:9: note: candidate: ‘template<class _Alloc, class _Requires> std::priority_queue<_Tp, _Sequence, _Compare>::priority_queue(const _Compare&, _Sequence&&, const _Alloc&) [with _Requires = _Alloc; _Tp = ipc_receive_t; _Sequence = std::vector<ipc_receive_t>; _Compare = std::less<ipc_receive_t>]’
  585 |         priority_queue(const _Compare& __x, _Sequence&& __c, const _Alloc& __a)
      |         ^~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_queue.h:585:9: note:   candidate expects 3 arguments, 2 provided
/usr/include/c++/14/bits/stl_queue.h:579:9: note: candidate: ‘template<class _Alloc, class _Requires> std::priority_queue<_Tp, _Sequence, _Compare>::priority_queue(const _Compare&, const _Sequence&, const _Alloc&) [with _Requires = _Alloc; _Tp = ipc_receive_t; _Sequence = std::vector<ipc_receive_t>; _Compare = std::less<ipc_receive_t>]’
  579 |         priority_queue(const _Compare& __x, const _Sequence& __c,
      |         ^~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_queue.h:579:9: note:   candidate expects 3 arguments, 2 provided
/usr/include/c++/14/bits/stl_queue.h:573:9: note: candidate: ‘template<class _Alloc, class _Requires> std::priority_queue<_Tp, _Sequence, _Compare>::priority_queue(const _Compare&, const _Alloc&) [with _Requires = _Alloc; _Tp = ipc_receive_t; _Sequence = std::vector<ipc_receive_t>; _Compare = std::less<ipc_receive_t>]’
  573 |         priority_queue(const _Compare& __x, const _Alloc& __a)
      |         ^~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_queue.h:573:9: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/stl_queue.h:569:9: note: candidate: ‘template<class _Alloc, class _Requires> std::priority_queue<_Tp, _Sequence, _Compare>::priority_queue(const _Alloc&) [with _Requires = _Alloc; _Tp = ipc_receive_t; _Sequence = std::vector<ipc_receive_t>; _Compare = std::less<ipc_receive_t>]’
  569 |         priority_queue(const _Alloc& __a)
      |         ^~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_queue.h:569:9: note:   candidate expects 1 argument, 2 provided
/usr/include/c++/14/bits/stl_queue.h:554:9: note: candidate: ‘template<class _Seq, class _Requires> std::priority_queue<_Tp, _Sequence, _Compare>::priority_queue() [with _Requires = _Seq; _Tp = ipc_receive_t; _Sequence = std::vector<ipc_receive_t>; _Compare = std::less<ipc_receive_t>]’
  554 |         priority_queue()
      |         ^~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_queue.h:554:9: note:   candidate expects 0 arguments, 2 provided
/usr/include/c++/14/bits/stl_queue.h:563:7: note: candidate: ‘std::priority_queue<_Tp, _Sequence, _Compare>::priority_queue(const _Compare&, _Sequence&&) [with _Tp = ipc_receive_t; _Sequence = std::vector<ipc_receive_t>; _Compare = std::less<ipc_receive_t>]’
  563 |       priority_queue(const _Compare& __x, _Sequence&& __s = _Sequence())
      |       ^~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_queue.h:563:38: note:   no known conversion for argument 1 from ‘std::greater<ipc_receive_t>’ to ‘const std::less<ipc_receive_t>&’
  563 |       priority_queue(const _Compare& __x, _Sequence&& __s = _Sequence())
      |                      ~~~~~~~~~~~~~~~~^~~
/usr/include/c++/14/bits/stl_queue.h:558:7: note: candidate: ‘std::priority_queue<_Tp, _Sequence, _Compare>::priority_queue(const _Compare&, const _Sequence&) [with _Tp = ipc_receive_t; _Sequence = std::vector<ipc_receive_t>; _Compare = std::less<ipc_receive_t>]’
  558 |       priority_queue(const _Compare& __x, const _Sequence& __s)
      |       ^~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_queue.h:558:38: note:   no known conversion for argument 1 from ‘std::greater<ipc_receive_t>’ to ‘const std::less<ipc_receive_t>&’
  558 |       priority_queue(const _Compare& __x, const _Sequence& __s)
      |                      ~~~~~~~~~~~~~~~~^~~
/usr/include/c++/14/bits/stl_queue.h:496:11: note: candidate: ‘std::priority_queue<ipc_receive_t, std::vector<ipc_receive_t> >::priority_queue(const std::priority_queue<ipc_receive_t, std::vector<ipc_receive_t> >&)’
  496 |     class priority_queue
      |           ^~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_queue.h:496:11: note:   candidate expects 1 argument, 2 provided
/usr/include/c++/14/bits/stl_queue.h:496:11: note: candidate: ‘std::priority_queue<ipc_receive_t, std::vector<ipc_receive_t> >::priority_queue(std::priority_queue<ipc_receive_t, std::vector<ipc_receive_t> >&&)’
/usr/include/c++/14/bits/stl_queue.h:496:11: note:   candidate expects 1 argument, 2 provided

bool operator< ... //Check if greater That's not what that operator does. — Drew Dormann
– Drew Dormann, Commented Feb 12 at 17:46

Drew Dormann · Accepted Answer · 2025-02-12 20:03:55Z

3

The third template parameter of a std::priority_queue is its comparator type, which defaults to std::less<T> when it's not specified.

Your code is not compiling because std::greater<ipc_receive_t>() is not of type std::less<ipc_receive_t>.

You will need this code.

std::priority_queue<ipc_receive_t, std::vector<ipc_receive_t>, std::greater<void>> pq (
    {}, std::move(container)
);

and you will need to define

bool operator>(const ipc_receive_t& object) const

edited Feb 12 at 20:03

answered Feb 12 at 17:41

Drew Dormann

65.5k14 gold badges133 silver badges200 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Dark Sorrow Feb 14 at 12:46

I wanted to confirm, for the std::priority_queue constructor you are using is with the following signature priority_queue( const Compare& compare, Container&& cont ); . On page en.cppreference.com/w/cpp/container/priority_queue/… this is the constructor with identifier 4.

Drew Dormann Feb 14 at 14:30

@DarkSorrow correct.

Collectives™ on Stack Overflow

std::priority_queue pre-allocate memory memory error

1 Answer 1

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related