What data structure should i use?

[DrJones]

I am looking for a data structure, which is capable storing a large amount a data. the data structure need to be able to sort the data quickly, and find certain elements as quickly as possible. what data structure would be ideal here?

[koothkeeper]

I'm guessing you mean container and not data structure. Perhaps you should look at the containers link (http://www.cplusplus.com/reference/stl/) to find the right STL container. If you are truly asking for a data structure, then that will depend upon the different types of data you need.

[DrJones]

sorry yeah... container..
i think a set or map would work..

But how do i do, with sorting it when it is suppose sort a struct?

struct town_gas
{

String name;
int prize;
}

The container has to sort based on the prize...

[koothkeeper]

Both maps and sets are sorted by design. If you are storing just a unique key value, a set is probably what you need. A map is an associative container allowing you to use a string for example as the key. Take a look at both to see how they might apply to your needs:

map: http://www.cplusplus.com/reference/map/map/

set: http://www.cplusplus.com/reference/set/set/

Let me know if you have other questions.

Good luck!

[Peter87]

If you are interested in the data structures that these containers use you should know that std::set and std::map is usually implemented as a red–black binary tree.

Container: http://en.cppreference.com/w/cpp/container/map
Data structure: https://en.wikipedia.org/wiki/Red%E2%80%93black_tree


There is also std::unordered_set and std::unordered_map that are implemented using hash tables. They also have fast lookup but if you iterate over the elements they will not be in any particular order.

Container: http://en.cppreference.com/w/cpp/container/unordered_map
Data structure: https://en.wikipedia.org/wiki/Hash_table


Depending on what you are doing you might also want to consider using an ordinary vector, and use binary search to find the element that you are looking for, but the code for this will probably not look as nice as with set/map. The advantage with this method is that the elements can be stored more space efficient but insertions are usually slower.