what is the point of saying that the complexity of insert() and erase() in the list container is constant time

I'm learning the C++ standard library, and while learning about std::list I came across that the complexity of insert() and erase() is constant time.

Now, at first, I didn't know how that is possible, until I realized that I have to pass the iterator that holds the specified location where I want to insert into, so the function itself is O(1).

But, I still have to do O(N) time to traverse through the list to set the iterator to the position that I want. So, at the end of the day, its not O(1) but O(N).

Now, why does everyone say that its constant time when we know that its not? Unless we want to insert in the front or the back, or unless we have the iterator we want to insert into, which can't be known without an O(N) traverse, so why is it said that it's faster than std::deque's insert and erase? I think both need O(N) time.

std::list deletion is indeed only O(1).

However, as you note, the most common scenario is that you don't already have an iterator, and instead have an index or value. In that case, you need to find the iterator first, and the find operation is O(n), as you note.

However, in this case, std::list is slow, and you shouldn't be using it in this case to start with. In most scenarios, you should be using std::vector or std::deque instead.

For the most part, the ONLY real time you should use std::list is as a secondary data structure, where the primary data structure contains iterators into the list. In that scenario, deletion is indeed only O(1).

> now why everyone says that its constant time when we know that its not. unless we want to insert in the front or the back

Why are you discounting this? FIFO (queues) and LIFO (stacks) are both useful, and frequently used, and both work perfectly fine with std::list (or any other linked list).

> or unless we have the iterator we want to insert into which can't be known without a o(n) traverse

Maybe we stored the iterator in some other object, or another container like std::unordered_map which has constant lookup time. This is also a perfectly reasonable usage.

You've correctly identified some situations in which a list is not the right container. That doesn't mean it's never the right container, because there are other situations.

> unless we have the iterator we want to insert into, which can't be known without an O(N) traverse

False. One of the nifty features of a list is that iterators remain valid after inserting other elements. They also remain valid after deleting elements, unless the iterator's element is what was deleted. In some cases, the iterator can be known without an O(N) traverse.

Consider a class that manages data of some sort. Other parts of the code ask it to store data, and in return those parts of the code receive a "handle" to the stored data. Later, the handle could be used to request deletion of the data. Let's suppose the container of choice is a std::list, so the handles could be essentially iterators into the list.

Assuming we're not concerned about order, insertions can always occur at an end of the list. This is a constant-time operation, even after accounting for returning an iterator to the added element. The calling code stores the returned handle, also a constant-time operation.

Later, after potentially thousands of other elements have been added to and removed from the list, the iterator is still valid. It is a constant-time operation to give this iterator/handle back to the manager class, and it takes constant time for the manager to delete the data from the list. There is no need to search for the data; the iterator remained valid. There is no O(N) operation in this scenario; everything is done in constant time.

The moral of this story is do not assume that an operation (e.g. traversal of the list) is necessary simply because you have not seen—or thought of—other possibilities. People writing standards should learn this lesson twice.

Even if a traversal was needed in all known cases, the standard should not artificially impose the assumption that a traversal is needed. Deletion from a linked list requires only constant time, so enforce that. You never know what clever ideas someone will come up with in the future. Give that person the best tools possible (e.g. minimal complexity for deletion), even if you yourself do not know how to utilize those tools to their full potential.