Best data structure/ container in C++ for insertion and deletion

Question

I am looking for the best data structure for C++ in which insertion and deletion can take place very efficiently and fast.

Traversal should also be very easy for this data structure. Which one should i go with? What about SET in C++??

Answer 1

A linked list provides efficient insertion and deletion of arbitrary elements. Deletion here is deletion by iterator, not by value. Traversal is quite fast.

A dequeue provides efficient insertion and deletion only at the ends, but those are faster than for a linked list, and traversal is faster as well.

A set only makes sense if you want to find elements by their value, e.g. to remove them. Otherwise the overhead of checking for duplicate as well as that of keeping things sorted will be wasted.