list class of STL (insertion to the list)

[stmfc]

list class is said to provide constant-time insertion and removal of elements at any location in the list.
but i cannot insert an element to an arbitrary position in the list using:

myList.insert(myList.begin()+2500,1000);

i got the following error:
no operator "+" matches these operands
operand types are: std::list<int, std::allocator<int>>::iterator +int myList.insert(myList.begin()+2500,1000);

i think the error message makes sense, because as far as i know list doesnt provide random access.
what i want to ask is "how i can insert to an arbitray position in the list?"

[mac11]

i think the error message makes sense, because as far as i know list doesnt provide random access.
what i want to ask is "how i can insert to an arbitray position in the list?"

I'm not sure a list can do what you want, they are made to provide sequential access so you just walk the list to get to the place you want to insert and then call insert and provide your iterator to the place you walked to.

If you need random access maybe a vector or map is better.

[phiefer3]

The reason it doesn't work is because the you can't do pointer/iterator addition with a linked list. That sort of addition assumes that all elements are in a contiguous memory space such as an array.

In order to insert into an arbitrary position you need an iterator that points to that location. This technically does provide a constant time for inserting at any location, provided that you already have an iterator that points to that location.

You really don't have any choice but to step the iterator through the list to the point you want to insert at, and then use the insert function.

[weaknessforcats]

You really don't have any choice but to step the iterator through the list to the point you want to insert at, and then use the insert function.

That means you (stmfc) need to use a vector and not a list.

[phiefer3]

That means you (stmfc) need to use a vector and not a list.

true, for the case of inserting in an arbitrary location a vector or other random access data structure is most efficient. But he's using a list, and may have very good reasons to do so.

On a slight note, I have tested out overriding the subscript operator [] to allow pseudo-random access for a linked list. Basically it just used the index provided to step throw the list to the desired node. This concept could be adjusted to return a pointer or iterator to the desired location. It may not be as efficient as a vector, but it shouldn't take that long to step through even a large linked list.