Efficient Way to Move Element Within std::deque?

Question

I am trying to maintain a sorted list.

Hence, when the key (not unique) of en element has changed, I will need to move an element at one location in std::deque to another location within the same std::deque.

I wonder what the most efficient way is. The simplest way is to do 1 binary search + 1 insert + 1 erase, which might involve memory allocation and deallocation.

Another way is to just call std::sort each time (after the key has changed) as it will do std::swap underneath. But it is a bit heavy O(n log n) (vs O(1) with 1 binary search + 1 insert + 1 erase = O(log n)).

Any suggestion is welcome.

Thanks!

It sounds like std::deque is not the appropriate container for your needs. Something like std::set or std::priority_queue or std::list may be more appropriate, depending. If you want to get useful help, you'll need to describe your actual use case. — Sneftel
@sneftel I am trying to use a queue to hold a list of tailor made timer tasks. Hence, I want to keep them sorted so that I can fire them in the correct sequence. Yes, I am aware of timerfd and alike. I have a specific environment that I can't use any OS based timer. — HCSF
Yes, std::multiset is a natural choice. Tho, std::map, std::multiset, and std::set have some latency spikes when tree rebalancing happens (I measured). — HCSF
That is exactly the most common application for a priority queue. — Sneftel
No, it doesn't really. It's not a very good priority queue. Around here we use a custom priority queue structure based on a pairing heap. It's an intrusive container, for fast updates. That all may be overkill for you unless your situation is particularly performance-critical. — Sneftel

bobah bobah · Accepted Answer · 2018-09-14T08:39:03

First qustion I would ask myself is why to use an std::deque container. It's neither the best data locality nor the fastest insertions. Especially when there is a container specifically designed for maintaining the sorting order at a minimum cost — std::map.

If you need both data locality and maintained sorting order have a look at boost::intrusive::map and boost::flat_map. They keep data local and just update the linkage when rebalancing the tree. The only difference is that the flat_map is encapsulating the tree implementation and the flat underlying storage, whereas the intrusive::map leaves the storage aspect entirely to you. I have an example of a conflation queue here which is using a ring buffer as a storage and an intrusive map as a sorting indexer on top of it.

Ultimately you need to benchmark and compare solutions based on your specific data and usage patterns.

Efficient Way to Move Element Within std::deque?

1 Answers