Time complexity and insertion in std :: list

Question

The insert in std :: list is considered constant, regardless of whether it is made in front, in the middle, or behind the container.

On the other hand, memory acquisition for a newly inserted element is handled by a standard allocator that uses the new operator. AFAIK new operator is not guaranteed to have a constant time.

When the new operator searches for available space on the heap, he must be sure that he will not overlap the previously allocated memory, so he must track from what has already been allocated to the heap. I conclude that the insert should be at least linear in the number of elements already in the list.

What is wrong with this reasoning?

---

My question is:

• How can I say that inserting into lists is a constant time when memory acquisition for each new node is not guaranteed by a constant time?

Answer 1

^{Note: It is important to note the difference between the "real time of life" and the "time" that was mentioned when immersed in time complexity. When time complexity is a topic, it is important that no one confuses the use of “time” when “milliseconds have spent something.”}

---

WHAT IS THE DEFINITION OF CONSTANT TIME?

Wikipedia is often considered a bad reference in many contexts, but in this case (and many others) the available definitions are correct and will help describe how everything works.

The article on time complexity talks about constant time:

Wikipedia - Constant time

An algorithm is called constant time (also written as time O (1)) if the value of T (n) is limited to a value that is independent of the size of the input. For example, access to any single element in an array takes constant time, since only one operation is needed to find it.

---

Since the insert in std::list does not depend on the number of elements in the list, we say that the insert is a constant time; each insertion, regardless of where and when, consists of the same number of elementary operations; none of them are related to the size of the list.

---

---

But what if operator new not O(1) ?

Honestly, this does not matter, even if the complexity of new will implicitly depend on the number of previous objects that we allocated, the complexity of our list insertion will not change. The selection is indifferent to the size of the list.

O(1) , constant time, means that the execution time of something is not related to the size of the input in any given algorithm. Even if new not O(1) , our insert is O(1) , because it only describes itself.

The paths used within our list include operator new . The path does not change due to the size of our list, the complexity of the path is a constant time.

---

---

So what are we dealing with?

Hannibal_Smith in ##c++ at freenode said something clever and I liked it so much that I will include it in this post: Cost model is a pointing machine.

Although the sentence may be a little misleading, it serves the purpose of explaining how insert O(1) , although parts of the algorithm are not constant time.

The insert in std::list described in terms of the fact that it is a machine that deals only with pointers, and from this point of view it cannot be said that it is nothing but O(1) . The allocation performed inside this algorithm is not related to the complexity of the algorithm itself.

Answer 2

This is a very complex issue that has been discussed to some extent in this topic .

If I could try to generalize it: the standard makes some subtle differences. If you read it accurately, some operations are indeed listed as "constant time", but the std::list insert is not one of them. It is listed as “persistent” ( Change : incorrect, see below) and the sentence “General container requirements” (23.2.1 in this draft C ++ standard ) explains that

All complexity requirements in this section are indicated solely in terms of the number of operations on the contained objects.

( Edit : as Philippe Rosen pointed out, I was wrong; the std::list insert is indicated as "constant time", but I believe that the General Requirements condition is still regulated). Therefore, since the insertion of the list should work only with one object and its neighbors, this is “constant complexity”, although this may not be “constant time complexity”, since there are no time limits for complexity for distribution.

Pragmatically, a decent memory allocator will not be linear in the number of allocated objects, although this is probably also not a constant time.