Re: Data structure for sorted list
- From: foobar <somefoobar@xxxxxxxxx>
- Date: Sat, 26 Apr 2008 00:26:27 -0700 (PDT)
If add and remove operations are supported to your sorted list then
you need to use map or set.
If the keys are not unique then you need to use multimap or multiset.
Following is an excerpt from MSDN describing what is best for which
conditions
<MSDN Excerpt>
The map should be the associative container of choice when the
conditions associating the values with their keys are satisfied by the
application. A model for this type of structure is an ordered list of
uniquely occurring key words with associated string values providing,
say, definitions. If, instead, the words had more than one correct
definition, so that keys were not unique, then a multimap would be the
container of choice. If, on the other hand, just the list of words
were being stored, then a set would be the correct container. If
multiple occurrences of the words were allowed, then a multiset would
be the appropriate container structure.
</MSDN Excerpt>
If the data never changes after you built the sorted list and only
find operation is what you intend to use then I second Doug's comment.
Using std::vector with lower_bound on sorted vector performs well, and
uses less memory compared to map variants.
On Apr 26, 3:18 am, "Doug Harrison [MVP]" <d...@xxxxxxxx> wrote:
On Fri, 25 Apr 2008 11:21:33 -0700, fractal <frac...@xxxxxxxxxxx> wrote:
fractal wrote:
I'm looking for ideas on how to create a sorted list that executes in
the shortest possible time.
Facts about the app:
* Presently, it builds a vector from external data, then quicksorts it
* Each data node has several (potentially long) strings to sort on,
which makes makes comparisons quite slow
* The number of nodes can vary from several dozen to tens of thousands.
* It's compiled with VC6, though if needed, an upgrade to 2008 would be
considered
Would a binary tree be the way to go? stl::map? Would another
structure execute faster than a simple quicksort?
Any thoughts would be appreciated!
I should probably mention that the existing list is vector of pointers
and is discarded after one use.
If I understand you correctly, you fill the data structure with all the
data it will ever hold before using it, and you never update the data
structure after you begin using it. Using std::vector and one std::sort
call sounds ideal to me, though if you only look up a handful of items, it
might be worthwhile to investigate partial_sort. (If you sort it fully, use
lower_bound to find items and binary_search just to test if they're
present.)
--
Doug Harrison
Visual C++ MVP
.
- References:
- Data structure for sorted list
- From: fractal
- Re: Data structure for sorted list
- From: fractal
- Re: Data structure for sorted list
- From: Doug Harrison [MVP]
- Data structure for sorted list
- Prev by Date: INDURA - INDURA is another popular brand, the trademark of Westex. It is 100% flame resistant cotton, and its higher version, INDURA Ultra Soft, is a blend of 88% cotton and 12% high tenacity nylon. Both these flame resistant fabrics are prime choice in welding industries and in places where there is a high exposure to flames. They are fire retardant fabrics, which repel flames and, even if they accidentally catch fire, will extinguish as soon as they are taken away from the source of the fire. The best part of INDURA is that it is light in weight and is extremely comfortable to the wear, since it is basically a cotton product.
- Next by Date: Corporate Uniforms And Workwear
- Previous by thread: Re: Data structure for sorted list
- Next by thread: Re: Data structure for sorted list
- Index(es):
Relevant Pages
|
