4

I need a data structure which can hold a set of numbers and sort them as quick as possible.

I thought a list would be good because inserting a new number in to the list would be easier than a vector (which would require copying the elements after the insertion). However, traversing the linked list (I am using the sorted list as a lookup to grab objects from an unordered_map) is likely to be much slower because the memory is scattered throughout the heap.

I was thinking of using a map, but wouldn't this also have a bad memory access due to the non-continuous nature?

A statically-allocated array (with lots of empty space) and a fast sorting algorithm is another idea I thought upon.....

To recap- I need a data structure which allows me to insert new elements and re-sort the elements as quick as possible. The elements will be numbers.

Any help is appreciated?

intrigued_66
  • 16,082
  • 51
  • 118
  • 189
  • See [this question](http://stackoverflow.com/q/471432/819272) on how to choose your Standard Containers. – TemplateRex Oct 04 '13 at 09:40
  • This is hard to answer since *fastest* depends not only on the big-O complexity, but also on the constant terms (i.e. a data structure with bad big-O might outperform a "better" one on "smaller" input sizes). Only a benchmark with realistic data can tell you what is "better" since "small" can often be pretty large. – Benjamin Bannier Oct 04 '13 at 09:41

5 Answers5

2

The fastest data structure is an array- contiguous regions of memory, optimal for the cache.

Sorting depends. A combination of quicksort with insertion sort used to sort sub-arrays below a certain size might be your best bet without resorting to something more esoteric.

Nikhil
  • 2,298
  • 13
  • 14
0

You probably want to think about how you store these objects in your vector/map. A smart pointer with the necessary comparison functor is probably what you want.

Paul Evans
  • 27,315
  • 3
  • 37
  • 54
  • I am just storing primitives? All I want is a storage container to store sorted numbers and allow me to insert/iterate over them. – intrigued_66 Oct 04 '13 at 09:46
0

If by "set of numbers" you mean each number only occurs once, and you want it sorted, use std::set. To be honest, unless you are dealing with huge amounts of data, std::list or even std::vector will probably be good enough.

Neil Kirk
  • 21,327
  • 9
  • 53
  • 91
0

The Boost.Containers library contains a flat_set data structure. It implements a std::set interface on top of a std::vector data storage. Advantages according to the documentation

  • Faster lookup than standard associative containers
  • Much faster iteration than standard associative containers
  • Less memory consumption for small objects (and for big objects if shrink_to_fit is used)
  • Improved cache performance (data is stored in contiguous memory)
  • Non-stable iterators (iterators are invalidated when inserting and erasing elements)
  • Non-copyable and non-movable values types can't be stored
  • Weaker exception safety than standard associative containers (copy/move constructors can throw when shifting values in erasures and insertions)
  • Slower insertion and erasure than standard associative containers (specially for non-movable types)
TemplateRex
  • 69,038
  • 19
  • 164
  • 304
-1

What is the fastest data structure

An array.

(and sorting algorithm)

Quicksort, provided you can tolerate the worst-case behaviour. Otherwise probably heapsort.

user207421
  • 305,947
  • 44
  • 307
  • 483
  • @downvoters Really this is incredible. This is Data Structures 101. You don't even give a hint of why you disagree. – user207421 Oct 04 '13 at 10:08
  • Didn't downvote, but I think the question is unanswerable without more details (and e.g. even bogosort would outperform both algorithms you mention on certain inputs). – Benjamin Bannier Oct 04 '13 at 11:41