Datatype for lookup table/index into array

Assume I have a class 'Widget'. In my application, I create a lot of Widgets which (for cache locality and other reasons) I keep in a vector.

For efficient lookups I would like to implement an index datastructure. For the sake of the question, let's assume it is a simple lookup table from int indices to Widget elements in the abovementioned vector. My question is: What should the contents of the lookup table be. In other words, with which type should I replace the question mark in

using LookupTable = std::vector<?>

I see the following options:

• References (Widget&, or rather as it has to be assignable: reference_wrapper<Widget>)


• Pointers (Widget*)


• Indices in the Widget vector (size_t)


• Iterator objects pointing into the Widget vector (std::vector<Widget>::iterator)

Among these options, indices seem to be the only option that don't get invalidated by a vector resize. I might actually be able to avoid resizes, however, implementing the lookup table like that means making assumptions about the vector implementation which seems unreasonable from a 'decoupled design' standpoint.

OTOH indices are not typesafe: If the thing I get out of the lookup table was a reference I could only use it to access the corresponding widget. Using size_t values I can do nonsensical operations like multiplying the result by 3. Also consider the following two signatures:

void doSomethingWithLookupResult(Widget& lookupResult);
void doSomethingWithLookupResult(size_t lookupResult);

The former is significantly more descriptive.

In summary: Which datatype can I use for my lookup table to achieve both a decoupling from the vector implementation and type safety?