I was working with an unordered list in C++ and needed to get the nth element, but STL doesn’t offer random access and I knew I was going to end up writing a loop anyway. And, Boost doesn’t provide random access for list collections either.
So I started thinking about this a little. C# offers index operators to access the List<T> class and that's pretty nice to have. So I wrote my own that looked something like this:
So I started thinking about this a little. C# offers index operators to access the List<T> class and that's pretty nice to have. So I wrote my own that looked something like this:
template <class T> class RAList : public list<T>
{
public:
T& operator [](unsigned int n)
{
iterator it = begin();
for(; n > 0; --n)
{
++it;
}
return *it;
}
};
You could have a const version and add error checking/handling if you really felt like it (my version gets what the Microsoft STL implementation provides which is essentially boundary condition handling in debug builds via the dereference operator for the iterator). You could also just as easily add it to the singly-linked list slist<T> as well. You could also start looping from the back of the list if you knew the element you were looking for was nearer the end.
Anyway, now, I can do stuff like this:
RAList<A> raList;
raList.insert(raList.end(), A("One"));
raList.insert(raList.end(), A("Two"));
A a = raList[1];
That’s a little better.
Of course, this is an O(n) operation and often a list is used if you have a decent-sized, variable-length collection, so it can take some time to find that nth element. However, you'd have to loop anyway to find it, so no loss there.
C# does provide this functionality for List<T>, but it’s a gimme because List<T> in the CLI is backed with an array! That’s a topic for a future post, however. And, Java, like the STL does not provide random access to implementations of List (ArrayList and others do offer it, however, via the get(i) method, but not via an indexer).
Now, if C++ had extension methods… I guess that’s a topic for a future post too.
Comparing .Net's List to STL's list is like comparing apples and oranges. The equivalent types in each environment are .Net List and STL vector if you want random indexed access and LinkedList and list if you want a linked list (neither provides an indexer). Now with Linq thrown in all IEnumerable implementing types support index based member access at the cost of O(n) but extension methods are a separate topic as hinted at the end of the article.
ReplyDeleteYou're right. I do point out that .Net List is backed with an array and isn't a linked list at all which makes it quite different from the linked-list STL List. STL vector is nice since it has indexers already, however, the code I was working with already had STL List and was really taking advantage of (amortized) constant-time insertion and deletions, but occasionally needed random access.
ReplyDelete