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

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

template&lt;class T&gt; int OrderedList&lt;T&gt;::Find(const T&amp; val) const {
    typename MapInd::const_iterator it = mapIndices.find(val);
    if (it != mapIndices.end())
        return it-&gt;second;
    return -1;
}
Name: I would call it an &quot;Unordered Set&quot;
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&lt;int&gt;   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 &lt;&lt; &quot;Equal\n&quot;;              std::cout &lt;&lt; &quot;Equal\n&quot;;
}                                    }

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

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

std::cout &lt;&lt; c1.size() &lt;&lt; &quot;\n&quot;;      std::cout &lt;&lt; c1.Size() &lt;&lt; &quot;\n&quot;;

std::cout &lt;&lt; *(p1.first) &lt;&lt; &quot;\n&quot;;    std::cout &lt;&lt; c1[p1] &lt;&lt; &quot;\n&quot;;