Dynamic array width id?

I need some sort of dynamic array in C++ where each element have thei开发者_Python百科r own id represented by an int.

The datatype needs these functions:

• int Insert() - return ID
• Delete(int ID)
• Get(ID) - return Element

What datatype should I use? I'we looked at Vector and List, but can't seem to find any sort of ID. Also I'we looked at map and hastable, these may be usefull. I'm however not sure what to chose.

---

I would probably use a vector and free id list to handle deletions, then the index is the id. This is really fast to insert and get and fairly easy to manage (the only trick is the free list for deleted items).

Otherwise you probably want to use a map and just keep track of the lowest unused id and assign it upon insertion.

---

A std::map could work for you, which allows to associate a key to a value. The key would be your ID, but you should provide it yourself when adding an element to the map.

An hash table is a sort of basic mechanism that can be used to implement an unordered map. It corresponds to std::unordered_map.

---

It seems that the best container to use is unordered_map. It is based on hash. You can insert, delete or searche for elements in O(n).

Currently unordered_map is not in STL. If you want to use STL container use std::map. It is based on tree. Inserts, deletes and searches for elements in O(n*log(n)).

Still the container choice depends much on the usage intensity. For example, if you will find for elements rare, vector and list could be ok. These containers do not have find method, but <algorithm> library include it.

---

A vector gives constant-time random access, the "id" can simply be the offset (index) into the vector. A deque is similar, but doesn't store all items contiguously.

Either of these would be appropriate, if the ID values can start at 0 (or a known offset from 0 and increment monotonically). Over time if there are a large amount of removals, either vector or deque can become sparsely populated, which may be detrimental.

std::map doesn't have the problem of becoming sparsely populated, but look ups move from constant time to logarithmic time, which could impact performance.

boost::unordered_map may be the best yet, as the best case scenario as a hash table will likely have the best overall performance characteristics given the question. However, usage of the boost library may be necessary -- but there are also unordered container types in std::tr1 if available in your STL implementation.