How does shift work when we use a unique function on a vector?

Question

So, I am currently reading some things in C ++, and I came across this cppreference example, and I could not understand how the shift works.

#include <iostream> #include <algorithm> #include <vector> int main() { std::vector<int> v{1, 2, 2, 2, 3, 3, 2, 2, 1}; std::vector<int>::iterator last; last = std::unique(v.begin(), v.end()); // 1 2 3 2 1 3 2 2 1 // ^ for (std::vector<int>::iterator it = v.begin(); it != last; ++it) { std::cout << *it << " "; } std::cout << "\n"; } 

I understand that when we use unique ones, this changes things, but I'm not sure how we get the sequence v.end() to us from last to v.end() .

From my own drawings on paper, I understand how we achieve a sequence from v.begin() to v.last() , but not from a sequence from v.last() to v.end() , as mentioned.

Here is the help site.

Answer 1

std:unique really just shifts items to the beginning as needed. The shift is not what you think. It should not be some kind of propagated singleton at that time. He can take advantage of the requirement by which an element must be assigned to move. By definition, move-assign, as soon as an element is moved, its previous contents are not specified. In your case, it just stores the “value” there, but it is not the specified value.

In short, what you see is the remaining values, and some of them may be nonspecific.

Below is a simple demonstration of your data. Initially, we have two places in the slots, R and W. I do not place any orders, this is the algorithm used by std::unique (to be honest, I do not know).

By trimming the trivial case (0 or 1-length sequence) when the value is to be stored, it is assigned by wrapping in the next slot above W, and W advances. Regardless of whether it is stored or not, R is always advancing. When this is done, the slot W is the last (i.e., the first of the remaining slots, some of which may have undefined values).

Given your data, the sequence would be something like this:

 1, 2, 2, 2, 3, 3, 2, 2, 1 - different, since the write target WR is the same as the read-point, do nothing, and advance both R and W 1, 2, 2, 2, 3, 3, 2, 2, 1 - equivalent, advance R only WR 1, 2, 2, 2, 3, 3, 2, 2, 1 - equivalent, advance R only WR 1, 2, 2, 2, 3, 3, 2, 2, 1 - different, move the 3 to the next write WR point and advance both R and W 1, 2, 3, 2, 3, 3, 2, 2, 1 - equivalent, advance R only WR 1, 2, 3, 2, 3, 3, 2, 2, 1 - different, move the 2 to the next write WR slot and advance both R and W 1, 2, 3, 2, 3, 3, 2, 2, 1 - equivalent, advance R only WR 1, 2, 3, 2, 3, 3, 2, 2, 1 - different, move the 1 to the next write WR slot and advance both R and W 1, 2, 3, 2, 1, 3, 2, 2, 1 - read is at end-of-sequence WR 

At this point, the reader is done. the first interval after W is equal to last as the algorithm goes (and can really be end if the original sequence had no duplicates). I leave you the task of determining which elements (3,2,2,1) are in the “unspecified” state after this.

_{Hint: what was moved? What was missed? What has been rewritten? Why does it matter? Try writing 0 to the slot for reading everything that has been moved, and see what is left in the sequence from last to end .}

Answer 2

The unique algorithm is very simple. For the [First, Last) range, you use two In and Out iterators to remove consecutive duplicates. In and Out initially assigned to the first element in the sequence.

 In = Out = First 

Then the algorithm is performed as follows if the range is not empty.

 while (++In != Last) { if (*In != *Out) { ++Out; *Out = *In; } } 

Now just continue until In reaches the end of the range. Then we return ++Out .

Out is basically an output iterator that writes unique elements to the same range, so we can extract the last iterator by increasing it after the above algorithm is completed.

This is easier if you do not think about it in terms of switching, but outputting to (and rewriting) the same range. The only tricky part is that we are overwriting the same range that we are reading. It is much easier to understand the algorithm if you discard unique elements in another sequence and return this sequence. Now you just apply a little optimization to avoid having to use a separate output range, overwriting the one you are reading.

Here is a quick implementation that I hacked that might be a little easier to understand than the vendor versions. It is deprived of some usual bundles, such as reusing the "first" as an input iterator, using the operator! = (Instead of! And ==), etc.

 template <class Iterator> Iterator my_unique(Iterator first, Iterator last) { if (first != last) { Iterator in = first; Iterator out = first; while (++in != last) { if (*in != *out) { ++out; *out = *in; } } return ++out; } return last; }