Complexity stl deque :: insert ()

Question

I learned the complexity of deque::insert() from the C ++ 2003 standard (chapter 23.2.1.3) as follows:

In the worst case, inserting a single element into a deque takes time that is linear in minimizing the distance from the insertion point to the start of the detex and the distance from the insertion point to the end of the deque.

I always understand the implementation of stl deque as a collection of memory blocks. Therefore, the insert will only affect elements in the same piece of memory as the insert position. My question is, what does the standard mean, “linear at the minimum distance from the insertion point to the beginning of the detox and the distance from the insertion point to the end of the deck”?

My understanding is that the C ++ standard does not apply a specific deque implementation. Complexity is usually the worst case scenario. However, in a real implementation in compilers, it linearly depends on the number of elements in the memory block, which may vary for different sizes of elements.

Another assumption may be that since insert() will invalidate all iterators, deque needs to update all iterators. Therefore, it is linear.

Answer 1

std :: deque is usually (always?) implemented as a collection of pieces of memory, but usually it will not insert a whole new piece so that you can insert one new element in the middle of the collection. This way, it will find whether the insertion point is closer to the beginning or end, and shuffle the existing elements to make room for the new element in the existing fragment. It will only add a new piece of memory at the beginning or end of the collection.

Answer 2

I think the diagram will be better for you ... let him play with ASCII art!

Deque is usually an array of chunks of memory, but everything about the front and rear memory blocks is full. This is necessary because deque is a RandomAccessContainer, and in order to access O (1) to any container, you cannot have an unlimited number of containers from which you can read the size:

 bool size() const { return first.size + (buckets.size()- 2) * SIZE + last.size; } T& operator[](size_t i) { if (i < first.size) { return first[SIZE - i]; } size_t const correctedIndex = i - first.size; return buckets[correctedIndex / SIZE][correctedIndex % SIZE]; } 

These operations are O (1) due to multiplication / division!

In my example, I assume that the memory block is full when it contains 8 elements. In practice, no one said that the size should be fixed, just so that all the inner buckets are the same size.

  // Deque 0: ++ 1: ++++++++ 2: ++++++++ 3: ++++++++ 4: +++++ 

Now tell us what we want to insert in index 13. It falls somewhere in a bucket with the inscription 2. There are several strategies that we can think of:

• expand bucket 2 (only)
• insert a new bucket before or after 2 and shuffle only a few items

But these two strategies would violate the invariant that all "inner" buckets have the same number of elements.

Therefore, it remains for us to mix the elements around, either to the beginning or to the end (depending on which is cheaper), in our case:

  // Deque 0: +++ 1: ++++++++ 2: +O++++++ 3: ++++++++ 4: +++++ 

Notice how bucket 0 increased.

This random move means that in the worst case you will move half of the elements: O (N / 2).

deque has O (1) inserted either at the beginning or at the end, because there it is simply a matter of adding an element to the right place or (if the bucket is full), creating a new bucket.

There are other containers that have better insert / delete behavior for random indexes based on B + Trees . In an indexed B + Tree, you can instead of holding a "key" (or in parallel) maintain the number of elements inside you to a certain position. For effective work, there are various techniques. At the end, you get a container with:

• O (1): empty, size
• O (log N): at, insert, erase

You can check the blist module in Python, which implements a list item like Python, supported by such a structure.

Answer 3

Your hypothesis ... 99.9% true. It all depends on what the actual implementation is. What the standard indicates is the minimum requirement for both developers (who cannot claim to be standard if they do not meet specifications) and users (who should not expect “better performance” when writing independent implementation code).

The idea of ​​the specification is a piece (a == one) of uninitialized memory, where the elements are distributed around the center ... until there is room for them. An insert in the middle means a shift. Inserting in front or at the end means just building in place. (when there is no space, redistribution is performed) Indexes and iterators cannot be trusted after modification, since we cannot assume what was shifted and in which direction.

A more efficient implementation does not use one piece, but several blocks to redistribute the “switch” problem and allocate memory at a constant size from the base system (thus limiting redistribution and fragmentation). If you focus on one of them, you can expect better results, otherwise you better not assume any optimization of the structure.

Answer 4

The linear number of elements inserted (copy creation). In addition, depending on the specific implementation of the library, additional linear time depending on the number of elements between the position and one of the ends of the deck. Link...