hash vs array

[rdargent]

I have a vector of strings. For each string, an integer value is associated.
I want to retrieve the strings, ordered by their value and original order (Note: the values can be the same for 2 strings).

For example:
MAX 7
JASON 4
TONY 2
BRANDON 7
JOHN 10

I used a map< int, vector<string>* > where int is the integer value and vector<string>* is the vector containing the strings when their integer value is the same.

In the example:
(key) (value = vector)
2 TONY
4 JASON
7 MAX, BRANDON
10 JOHN

But I was wondering if this is the fastest way to order my data or if it would be better to apply a quicksort on the integer value...

Any idea?

[helios]

But I was wondering if this is the fastest way to order my data or if it would be better to apply a quicksort on the integer value...

Depends on your pattern of insertion and retrieval.
If you'll insert everything before having to retrieve anything, it's faster to sort a vector once. If you'll intersperse insertions and retrievals, a map is faster.
A vector can also be traversed slightly faster than a map.

[LB]

used a map< int, vector<string>* >

I think you wanted this?

map<int, string> StringMap;
for(map<int, string>::iterator Strit = StringMap.begin(); Strit != StringMap.end(); ++Strit;)
{
	cout << Strit.second << ' ' << Strit.first << endl;
}

[moorecm]

Consider a std::multimap< int, std::string >, since there are duplicate keys (integers). Note that this WILL not maintain the original order of the sequence.
http://www.cplusplus.com/reference/stl/multimap/

For a container that has the capability to provide multiple views, for example one sequential and one sorted, check out Boost.MultiIndex.
http://www.boost.org/doc/libs/1_44_0/libs/multi_index/doc/index.html

[rdargent]

@helios: Do you know where I could find the complexity formulas for what you are stating?

[helios]

(The following are the average times.)

Sorting a vector once takes linearithmic time. Inserting a single element into a map takes logarithmic time.
Traversing a vector takes linear time. Traversing a map takes linearithmic time.

The reference on this site includes the complexities for these operations and more.