3
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ Lists are ordered by definition. Did you want a SortedList? \$\endgroup\$ – cHao Dec 20 '16 at 21:41
  • \$\begingroup\$ @cHao do you understand what does it do? \$\endgroup\$ – user31264 Dec 20 '16 at 21:49
  • \$\begingroup\$ Sort of, now that i read through it. Acts more like an ordered set than a list, though. \$\endgroup\$ – cHao Dec 20 '16 at 21:54
2
\$\begingroup\$

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";
\$\endgroup\$
  • \$\begingroup\$ "What you have implemented looks like std::set" - maybe very remotely. It stores the number for each value, std::set doesn't. "your container uses twice as much spaces it needs too" - without storing them twice, it wouldn't be able to provide the neccessary functionality (or would do it in linear instead of logarythmic time). \$\endgroup\$ – user31264 Dec 21 '16 at 0:59
  • \$\begingroup\$ @user31264: It stores the number for each value: Basically this is like a primitive iterator. \$\endgroup\$ – Martin York Dec 21 '16 at 3:36
  • \$\begingroup\$ @user31264: without storing them twice, it wouldn't be able to provide the neccessary functionality. Easily. If you use a standard set you get exactly the same functionality. Search/Insert in logarithmic time. If it was not possible I would not have mentioned it. \$\endgroup\$ – Martin York Dec 21 '16 at 3:37
  • \$\begingroup\$ @LokiAstaru - "If you use a standard set you get exactly the same functionality." - absolutely not. "Search/Insert in logarithmic time. " - Find() is different than set search, operator[] is not implemented at all, Insert() is different than set insert. \$\endgroup\$ – user31264 Dec 21 '16 at 7:46
  • \$\begingroup\$ @user31264: std::set: Search/Insert is logarithmic. Find/Insert returns an iterator (which is what your integer is). Your operator[] is a complex way of dereferencing an iterator (value returned by find/insert). std::set provides an iterator that can be directly de-references. So functionality is identical. \$\endgroup\$ – Martin York Dec 21 '16 at 8:05
2
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.