CODEWITHSUNDEEP
c++algorithmstl
DIVAKAR VENKATRAMANI
DIVAKAR VENKATRAMANI

Reputation: 237

Stream of Integers arriving at specified interval need to look sorted

Interview question: There is a stream of Integers that arrives at specified intervals (say every 20 sec). Which Container of STL would you use to store them so that the Integers look sorted? My reply was map/set when there is no duplicate or multimap/multiset when there is duplicate. Any better answer if exists?

Upvotes: 1

Views: 158

Answers (4)

Chammika Mannakkara
Chammika Mannakkara

Reputation: 11

To maintain a sorted list of integers streaming I would use std::priority_queue with any underlying container (vector or deque depending on the particular use).

You can keep push() ing to the priority_queue and use top() and pop() to retrieve in the sorted order.

Upvotes: 1

Jerry Coffin
Jerry Coffin

Reputation: 490108

If it's only being updated every 20 seconds, it probably doesn't matter a whole lot (unless it goes for so long that the set of integers becomes tremendously huge).

If you had data coming in a lot faster, there are alternatives that might be worth considering. One would be to use a couple of vectors. As data arrives, just push it onto one of the vectors. When you need to do an in-order traversal, sort that newly arrived data, and merge with the other vector of existing (already-sorted data). That'll give you results in order, which you can then write out to another vector, and start the same cycle again.

The big advantage here is that you're dealing with contiguous data instead of individually allocated nodes. Even with a possibility of three vectors in use at a time, your total memory usage is likely to be about equal (or possibly even less than) that of using a set or multiset.

Another possibility to consider (that's a bit of a hybrid between the two) would be something like a B+ tree. This is still a tree, so you can do in-order insertions with logarithmic complexity, but you have all the data in the leaf nodes (which are fairly large) so you get at least a reasonable amount of contiguous access as well.

Upvotes: 2

R Sahu
R Sahu

Reputation: 206577

Use a multiset if you want to preserve duplicates. If you don't want to preserve duplicates, use a set.

Upvotes: 2

Steephen
Steephen

Reputation: 15824

Answer should be std::set . std::map<key, value> has to consider when there is a pairs of data as <key, value> and it need to be sorted according to the value of key

In same way if you have to consider duplicates, use std::multiset and std::multimap according to type of data.

Upvotes: 0

Related Questions