How to access a certain element in std::list<string>

Question

   list<string>&  whichList = theLists[ myhash( x, theLists.size( ) ) ];

I was wondering how to access a certain position say "i" and see if it was empty at that position.

I was doing it like this:

if(whichList[i] == 0)

but it does not seem to be working.

I realize this is wrong. Any suggestions?

Answer 1

You could try something like:

list<string> iterator it = whichList.begin();
std::advance(it, i);
if(*it == "") { /* ... */ }

But I think you need to clearly define what you mean by "empty" here - you can't compare strings to 0.

The key point is that list doesn't support random access - because of its implementation (a doubly-linked list), supporting random access would be an O(n) operation, i.e. linear in the length of the list in the worst case. That's inefficient, so it's deliberately not supported in the interface.

As others have pointed out, if you want random access then you're better off using something like a vector or deque. Generally speaking, you would use a vector if you only need fast insertion/removal at the end of the container, a deque if you also need fast insertion/removal at the front of the container, and a list only if you need fast insertion/removal in the middle of the container. In order to support the latter type of operation, list ends up sacrificing random access to elements.

See here for the definition of advance, incidentally:

http://www.sgi.com/tech/stl/advance.html

EDIT: As Alf pointed out, you can to some extent get fast insertion/removal in the middle of a vector using the gap buffer technique (see http://en.wikipedia.org/wiki/Gap_buffer), although an individual operation can be costly if you fill the gap (the idea is to amortise the cost over lots of operations, making an operation sequence comparatively cheap).