Datatype for lookup table/index into array

Question

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?

Answer 1

Use std::vector::size_type (not size_t). std::vector::size_type may be size_t in most implementations, but for portability and future-proofing sake, we'll do it right.

Go ahead and make a typedef: using WidgetIndex = std::vector::size_type;

so that this looks reasonable:

void doSomethingWithLookupResult(WidgetIndex lookupResult);

This avoids the vector resize issue which, while you down play it in your question, will eventually come back to bite you.

Don't play games with some user defined type such as tohava (very cleverly) proposes, unless you plan to use this idiom a great deal in your code base. Here is why not:

• The problem that you are addressing (type-safety) is real and we'd like a solution to it if it is "free," but compared to other opportunities C++ programmers have to shoot themselves in the foot, this isn't that big an issue.
• You'll be wasting time. Your time to design the class and then the time of every user of your code base (including yourself after you've forgotten the implementation in a few months) that will stare at that code and have to puzzle it out.
• At some point in the future you'll trip over that "interesting" corner case that none of us can see now by staring at this code.

All that said, if you are going to use this idiom often in your code base (you have many classes that are stored in very static vectors or arrays), then it may make sense to make this investment. In that case the maintenance burden is spread over more code and the possibility of using the wrong index type with the wrong container is greater.