Suggestions on a lazy indexed vector in C++11?

I am working with a lot of objects and many of those objects have arrays of sub objects. Some of these can have millions of items, and during specific operations, I need the items to be accessed by name.

But, at the same time, I need to keep performance and memory consumption low. So my thought was to create a composite template class something along the lines of:

template <typename T>
class IndexedList {
public:
    std::vector<std::shared_ptr<T>> items;
    std::unordered_map<std::string, std::shared_ptr<T>> index;
    void build_index();
};

For the lists where the item names are unique, this is ok, but where I am struggling is how to deal with lists where the names are not unique. I can't really use a map, and I would rather not iterate over the set.

The other point is that I have to get the items back in the same order on some instances and in a sorted order in another.

So, the challenge is can it be done with a single template? I would prefer not to have to decide at compile time which method to use. Ideally something like a SmartList, that lazily indexes once the item list is loaded and decides at runtime if it should use a map or unordered_map (or set) based on the load pattern when searches by name begin coming in. It should also handle multiple keys values, if multiple were encountered during the load of the vector.

Anyone have such a beast?