Dark Sorrow
Reputation: 1947
std::priority_queue pre-allocate memory memory error
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
Upvotes: 1
Views: 77
Answers (1)
Drew Dormann
Reputation: 63947
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
Upvotes: 3
Related Questions
- What's the problem with "using namespace std;"?
- Concatenating two std::vectors
- Why can't I access elements with operator[] in a const std::map?
- Error using std::set to implement a sparse 3D grid
- How can I use std::maps with user-defined types as key?
- error: no matching function for call to ‘std::vector<std::__cxx11::basic_string<char> >::push_back(int&)’
- How to call class member function from iterator of map in C++?
- Error using custom operator< with std::less