erasing the i'th element from std::list

[Absurd]

Hi.

given a list and an index i (of type int), how can I erase the i'th element using the STL library?

to be more specific:

I have a class named RadioStation, that holds a list of Playlists as an instance variable:

list<Playlist> m_playlists;

and I need to implement the following method:

bool removePlayList(unsigned iPlaylistNumber);

the above method supposed to erase the Playlist whose index is iPlayListNumber.

the naive way to do it (or at least the one that I came up with) is this:
since list::erase takes an iterator to a position, I first set an iterator to the very begining of the list:

list<Playlist>::iterator iter=m_playlists.begin();

then advancing iter iPlaylistNumber steps ahead:

std::advance(iter,iPlaylistNumber);

and finally erasing the element:

m_playlists.erase(iter);

is there other, easier way to do it?

thanks in advanced!

[SirPrattlepod]

m_playlists.erase(m_playlists.begin() + i);


make sure the element exists beforehand


Oops. I didn't read carefully and was thinking of vectors for some reason.

[grumpy]

If you know the position (or index) of the element you wish to remove, and have your heart set on using std::list, that's probably the easiest way. list's iterators do not support adding integral values (other than 1) in order to advance.

Given that you are referring to elements of a list using an integral index, you might be better off using a vector. Vector's iterators provide alternative methods of obtaining an iterator corresponding to an index.

[SirPrattlepod]

Oops. I didn't read carefully and was thinking of vectors for some reason.

Yeah? Well, welcome to my ignore list fool!

[Absurd]

Thanks grumpy.
I relize vector gives random access, wich will make it more easier here, but list is more suitable for my purposes in this case.

[Elkvis]

list is more suitable for my purposes in this case.

with modern C++ compilers and hardware, the advantage that list has over vector is rapidly shrinking.

[Absurd]

with modern C++ compilers and hardware, the advantage that list has over vector is rapidly shrinking.

I agree, but since this is part of a class assignment, the grade is given by our choices on which containers to use in what case.
the more efficient the code, the less points we'll lose.

[Elkvis]

out of curiosity, what makes std::list more suitable for your needs? it's less efficient on storage, less efficient when accessing elements by index, and can only be more efficient when adding and removing items, and even then, it's not a guarantee.

[Absurd]

well, mainly because beside removePlaylist(int iPlaylistNumber);, I'm also implementing (and using quite a lot) removePlaylist(Playlist pl); where std::list removes objects in O(1), instead of O(n) with std::vector.

[kmdv]

with modern C++ compilers and hardware, the advantage that list has over vector is rapidly shrinking.

WAT ?!!

Elaborate...

and can only be more efficient when adding and removing items, and even then, it's not a guarantee

It is guaranteed.

@OP:

How I would recommend to do it not for an assignment:

1. Make abstraction of the list; encapsulate either std::list or std::vector (whatever is easier to use).
2. Ask yourself if the performance is actually a problem. If it is, then optimise (possibly switching to a different container).

How I would recommend to do it for an assignment:

The problem is that it is harder to optimise for both, insertion/erasure and random access, at the same time. You can certainly get a mixture of the two. One solution is to use std::list and cache (that is, remember) any random access.

How to implement random access caching?

First, you have to make an abstraction. You should create a class "Playlists" which would internally keep:
- an std::list holding your playlists;
- iterator to the recently accessed element;
- index of the recently accessed element.
Whenever you randomly access element of your container, you can make use of the iterator and its associated index to quickly move to the desired element of std::list. It means that if the recently visited element was at index 100, and now you want to visit element at index 101, the class "Playlists" will (under the hood) increment the internal iterator and its associated index by one, and then return dereferenced value. If the next element is at index 102, then again, it will increment iterator and its associated index only by one.

The proposed random access caching is only one of the solutions.

But do you really need a list? What about a map:

std::unordered_map<std::string, Playlist> playlists;

Random access, insertion, and erasure would all have constant time in average (std::map would guarantee logarithmic). Additionally, you can use mnemonical names instead of ugly indices.

[grumpy]

with modern C++ compilers and hardware, the advantage that list has over vector is rapidly shrinking.

I disagree.

list and vector are specified to have different complexity of some operations (appending to the beginning or end, inserting in the middle, counting the elements, etc). Depending on the pattern of use of the container and its size, there are distinct advantages of each container type over another.

Modern compilers and hardware have an effect, sure. But they can't generally turn high complexity operations into low complexity operations. And they are limited by the dependencies between operations.

[Elkvis]

Elaborate...

if the entire vector can be stored in the processor's cache memory, it's possible for vector to be faster than list for all operations, because of the nodal nature of a list. it's conceivable that in a worst case, every time you retrieve the next element of a linked list, it could cause a cache miss and force the processor to fetch it from main memory.

[King Mir]

Bjarne Stroustrup made exactly this point in GoingNative2012 (short video of that segment)