Dear list, I was wondering if there some kind of "priority queue", that is a data structure akin the priority queue, but where you can top and pop from both sides. My use case is that I need to quickly access the maximum, but also not push new elements if they are smaller than the minimum. I am aware I can use a std::set, but in the current implementation where I always push new elements even if they are bad, using a std::set the performance is significantly worse. Yours faithfully, Paolo
On September 1, 2016 4:55:38 AM EDT, Paolo Bolzoni <paolo.bolzoni.brown@gmail.com> wrote:
Dear list,
I was wondering if there some kind of "priority queue", that is a data structure akin the priority queue, but where you can top and pop from both sides. My use case is that I need to quickly access the maximum, but also not push new elements if they are smaller than the minimum.
Deque is one of my favorites. Ordered? Unordered?
I am aware I can use a std::set, but in the current implementation where I always push new elements even if they are bad, using a std::set the performance is significantly worse.
I'm not sure set is the same thing as an ordered anything (list, vector, queue, deque).
Yours faithfully, Paolo
Regards, Michael Powell
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
-- Sent from my Android device with K-9 Mail. Please excuse my brevity.
Oh, dear. I made a stupid mistake. I meant a "priority deque", a data structure where you can easily access the maximum and minimum element. In priority queue you can top and pop the maximum element, I would need both to pop and top the maximum and the minimum. On Thu, Sep 1, 2016 at 3:34 PM, Michael <mwpowellhtx@gmail.com> wrote:
On September 1, 2016 4:55:38 AM EDT, Paolo Bolzoni <paolo.bolzoni.brown@gmail.com> wrote:
Dear list,
I was wondering if there some kind of "priority queue", that is a data structure akin the priority queue, but where you can top and pop from both sides. My use case is that I need to quickly access the maximum, but also not push new elements if they are smaller than the minimum.
Deque is one of my favorites. Ordered? Unordered?
I am aware I can use a std::set, but in the current implementation where I always push new elements even if they are bad, using a std::set the performance is significantly worse.
I'm not sure set is the same thing as an ordered anything (list, vector, queue, deque).
Yours faithfully, Paolo
Regards,
Michael Powell
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
-- Sent from my Android device with K-9 Mail. Please excuse my brevity. _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
On September 1, 2016 9:34:03 AM EDT, Paolo Bolzoni <paolo.bolzoni.brown@gmail.com> wrote:
Oh, dear. I made a stupid mistake. I meant a "priority deque", a data structure where you can easily access the maximum and minimum element. In priority queue you can top and pop the maximum element, I would need both to pop and top the maximum and the minimum.
I understood your meaning. The generally recommend approach is use a std::vector in combination with one of the search algorithms for insertion purposes. If you absolutely have to, use sort. In either case the insertion times will naturally suffer. There are many examples of this. It would be simple to write a push/pop front/back for that. HTH
On Thu, Sep 1, 2016 at 3:34 PM, Michael <mwpowellhtx@gmail.com> wrote:
On September 1, 2016 4:55:38 AM EDT, Paolo Bolzoni
<paolo.bolzoni.brown@gmail.com> wrote:
Dear list,
I was wondering if there some kind of "priority queue", that is a data structure akin the priority queue, but where you can top and pop from both sides. My use case is that I need to quickly access the maximum, but also not push new elements if they are smaller than the minimum.
Deque is one of my favorites. Ordered? Unordered?
I am aware I can use a std::set, but in the current implementation where I always push new elements even if they are bad, using a std::set the performance is significantly worse.
I'm not sure set is the same thing as an ordered anything (list, vector, queue, deque).
Yours faithfully, Paolo
Regards,
Michael Powell
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
-- Sent from my Android device with K-9 Mail. Please excuse my brevity. _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
-- Sent from my Android device with K-9 Mail. Please excuse my brevity.
On Thu, Sep 1, 2016 at 3:34 PM, Paolo Bolzoni <paolo.bolzoni.brown@gmail.com
wrote:
Oh, dear. I made a stupid mistake. I meant a "priority deque", a data structure where you can easily access the maximum and minimum element. In priority queue you can top and pop the maximum element, I would need both to pop and top the maximum and the minimum.
Would BMI's ranked indices work for you? --DD http://www.boost.org/doc/libs/1_61_0/libs/multi_index/doc/tutorial/indices.h...
It seems this is exactly what I am looking for: https://github.com/nmcclatchey/Priority-Deque It even mention it's a "Boost candidate." Still, those ranked indeces may also work. Thanks for the link. On Thu, Sep 1, 2016 at 4:17 PM, Dominique Devienne <ddevienne@gmail.com> wrote:
On Thu, Sep 1, 2016 at 3:34 PM, Paolo Bolzoni <paolo.bolzoni.brown@gmail.com> wrote:
Oh, dear. I made a stupid mistake. I meant a "priority deque", a data structure where you can easily access the maximum and minimum element. In priority queue you can top and pop the maximum element, I would need both to pop and top the maximum and the minimum.
Would BMI's ranked indices work for you? --DD
http://www.boost.org/doc/libs/1_61_0/libs/multi_index/doc/tutorial/indices.h...
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
participants (3)
-
Dominique Devienne -
Michael -
Paolo Bolzoni