Container that can iterate in order, access specific elements, and remove elements

Question

I am currently using a std::vector<int> vec of size nto store the integers from 0 to n-1 in any order. Suppose that the vec is given by the following:

std::vector<int> vec = {4, 1, 2, 0, 3};

I need to

• iterate over vec in order, i.e. 4 -> 1 -> 2 -> 0 -> 3.
• access specific elements by index vec[3] -> 0.
• remove specific elements by value del vec[2] -> {4, 1, 0, 3}.

The vector is given a priori and the maximum size is known (as we never add elements). What data structure would be suitable here (having performance in mind)?

Answer 1

Keep the std::vector, it has the least overhead and isn't asymptoticly worse at any of these.

iterate over vec in order

Any container will be at least linear in the number of elements.

access specific elements by index

std::vector is constant here

remove specific elements by value

Because you don't know where any given element is, and therefore have to do a search, which is worst case linear, every container will be worst case linear for this, so it doesn't matter that vector has linear erase.