CODEWITHSUNDEEP
c++stl
titan
titan

Reputation: 435

STL to store the numbers in sorted order

which is the ideal STL container to use in C++ for a sorted insert for the integers which could contain duplicates.

Upvotes: 1

Views: 811

Answers (5)

Rontogiannis Aristofanis
Rontogiannis Aristofanis

Reputation: 9063

I recommend you the following:

  1. std::multiset found at the <set> header
  2. std::priority_queue found at the <queue> header

You can also store the data into a std::vector/std::deque/std::list and then sort them using the std::sort function, which is found at the <algorithm> header.

Upvotes: 0

hege
hege

Reputation: 1017

If the lookups and insertions are interleave with that magnitude, I would rather suggest a simple vector and sort it when the lookup period starts.

Upvotes: 0

Tom Kerr
Tom Kerr

Reputation: 10720

std::multiset is probably the expected answer.

If the domain is relatively small (especially compared to the number of incidences), then counting sort can be used to good effect however. You would use std::vector<int> with the size of the domain. Then the value becomes the index, and the count becomes the number of incidences.

Upvotes: 0

Mark B
Mark B

Reputation: 96241

The two obvious choices are a heap/priority_queue or a multiset. The heap will only let you access the largest element at any point while the multiset will store the items (with duplicates) in sorted order, allowing you to iterate over them.

With more information about your specific problem a more refined answer could be provided.

Upvotes: 0

jcoder
jcoder

Reputation: 30035

If I understand you possibly a std::multiset It will store duplicates but when you iterate over the container you'll get them in sorted order

Upvotes: 2

Related Questions