OrderedList class template

Question

I called my template OrderedList, but I don't like the name. Is there a better one?

It stores a vector of values of type T, and a map from each value to its index in the vector.

Just for information, the code should be pure C++03, so please don't suggest how it could be improved with C++11/14/17 extensions, or with Boost.

template<class T> class OrderedList {
    public:
        typedef typename std::map<T, int> MapInd;
    public:
        int Insert(const T& val); // insert new value, return its index
        int Find(const T& val) const; // find index for the value, or -1 if not found
        const T& operator[](int i) const {return vValues[i];}
        int Size() const {return vValues.size();}
    private:
        MapInd mapIndices; // index for each element
        std::vector<T> vValues; // element for each index
};

template<class T> int OrderedList<T>::Insert(const T& val) {
    if (Size() < 0)
        return -1;
    int ind = Find(val);
    if (ind >= 0)
        return ind;
    ind = Size();
    mapIndices[val] = ind;
    vValues.push_back(val);
    return ind;
}

template<class T> int OrderedList<T>::Find(const T& val) const {
    typename MapInd::const_iterator it = mapIndices.find(val);
    if (it != mapIndices.end())
        return it->second;
    return -1;
}

Answer 1

Name: I would call it an "Unordered Set"

You have a container that you can add items to. Duplicates are not accepted and return the index of the existing value. New values are added to the container in the order they are inserted.

Because items can be inserted in any order iterating through the container returns the values in insert order (somewhat random) so the container is not sorted in any way.

Issues: You keep two copies of each value.

There is a copy in the map and a copy in the vector. So your container uses twice as much spaces it needs too (especially for big objects).

What you have implemented looks like std::set

But it has worse space requirements.

Comparison to std::set

std::set<int>   c1;                  OrderedList c1;

auto p1 = c1.insert(5);              auto p1 = c1.Insert(5);
auto p2 = c1.insert(5);              auto p2 = c1.Insert(5);
if (p1.first == p2.first) {          if (p1 == p2) {
    std::cout << "Equal\n";              std::cout << "Equal\n";
}                                    }

auto p3 = c1.find(6);                auto p3 = c1.find(6);
if (p3.first == c1.end()) {          if (p3 == -1) {
    std::cout << "Not Found\n";          std::cout << "Not Found\n"
}                                    }

auto p4 = c1.find(5);                auto p4 = c1.find(5);
if (p4 == p1.first) {                if (p4 == p1) {
    std::cout << "Already there\n";      std::cout << "Already there\n"
}                                    }

std::cout << c1.size() << "\n";      std::cout << c1.Size() << "\n";

std::cout << *(p1.first) << "\n";    std::cout << c1[p1] << "\n";

Answer 2

I was going to write this as a comment to @LokiAstari's answer but it turned out to be too long...

What @LokiAstari points out in their answer is mostly correct. What you have implemented is essentially a std::set but with one minor difference you preserve the insertion order when you later iterate over the set.

While iterating over a std::set is the same time complexity as iterating over your OrderedList; the set is implemented using a tree and when iterating a tree you will chase pointers possibly resulting in several cache misses on the way, while on the other hand your code is using a vector which is contiguous and fast to iterate over. Because of this iterating the OrderedList will be faster in most cases. However you have double the memory usage of a std::set.

Note that std::set::insert and std::set::remove do not invalidate any iterators:

Until C++17

No iterators or references are invalidated.

Since C++17

No iterators or references are invalidated. If the insertion is successful, pointers and references to the element obtained while it is held in the node handle are invalidated, and pointers and references obtained to that element before it was extracted become valid.

(Note: the iterator itself never becomes invalidated even after C++17)

However std::unordered_set (Since C++11) may or may not invalidate the iterators depending on if a rehashing occurred or not. So if stable iterators are important for you then you should not use it.

As for your question it is hard for us to help you because you have not clearly specified the requirements on the container you're trying to design. Depending on how you want to use it (we don't know) you may or may not be better of just using std::set. But my gut feeling here is that requiring stable iterators indicates that you have a problem elsewhere in your code and that your efforts are better spent rethinking your design to get rid of that requirement.