Công việc dịch chuyển làm việc như thế nào khi chúng ta sử dụng hàm duy nhất trên một véc-tơ?

Question

Vì vậy, tôi hiện đang đọc trên một số công cụ c + + và tôi đi qua ví dụ này về cppreference và tôi không thể hiểu làm thế nào ca làm việc.

#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"; 
} 

Tôi hiểu rằng khi chúng ta sử dụng độc đáo nó thay đổi mọi thứ kết thúc, tuy nhiên tôi không chắc chắn cách thức chúng tôi thu được đoạn ban cho chúng ta last-v.end().

Thông qua bản vẽ của riêng tôi trên giấy, tôi hiểu cách chúng tôi đạt được trình tự từ v.begin() đến v.last(), nhưng không phải trình tự từ v.last() đến v.end() như đã đề cập.

Đây là reference site.

Answer 1

std:unique thực sự chỉ thay đổi các phần tử về đầu khi cần. Sự thay đổi không giống như bạn có thể suy nghĩ. Nó không cần phải có một số yếu tố được truyền bá một yếu tố. Có thể tận dụng yêu cầu yếu tố phải là chuyển nhượng được chuyển nhượng. Theo định nghĩa của chuyển-di chuyển, khi một phần tử được di chuyển, nội dung trước của nó không được chỉ định. Trong trường hợp của bạn, nó chỉ giữ "giá trị" ở đó, nhưng nó không phải là giá trị được chỉ định.

Tóm lại, những gì bạn thấy là giá trị còn lại và một số trong số đó có thể là không cụ thể.

Sau đây là bản trình diễn đơn giản sử dụng dữ liệu của bạn. Ban đầu chúng tôi có hai vị trí khe cắm, R và W. Tôi không đảm bảo rằng đây là thuật toán được sử dụng bởi std::unique (Tôi thực sự không biết).

vỏ ra các trường hợp tầm thường (tự 0 hoặc 1-chiều dài), khi một giá trị là phải giữ nó là di chuyển-giao trong khe tiếp theo trên W và W là tiên tiến. Bất kể nó được lưu giữ hay không, R luôn được nâng cao. Khi hoàn tất, vị trí qua W là last (nghĩa là lần đầu tiên của các vị trí còn lại trên các vị trí, một số có thể có giá trị không xác định).

Với dữ liệu của bạn, trình tự sẽ là một cái gì đó như thế này:

1, 2, 2, 2, 3, 3, 2, 2, 1 - different, since the write target 
W R      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 
    W R      

1, 2, 2, 2, 3, 3, 2, 2, 1 - equivalent, advance R only 
    W  R      

1, 2, 2, 2, 3, 3, 2, 2, 1 - different, move the 3 to the next write 
    W  R    point and advance both R and W 

1, 2, 3, 2, 3, 3, 2, 2, 1 - equivalent, advance R only 
     W  R 

1, 2, 3, 2, 3, 3, 2, 2, 1 - different, move the 2 to the next write 
     W   R   slot and advance both R and W 

1, 2, 3, 2, 3, 3, 2, 2, 1 - equivalent, advance R only 
     W   R  

1, 2, 3, 2, 3, 3, 2, 2, 1 - different, move the 1 to the next write 
     W    R slot and advance both R and W 

1, 2, 3, 2, 1, 3, 2, 2, 1 - read is at end-of-sequence 
      W    R 

Tại thời điểm này, người đọc xong. khe đầu tiên qua W là last khi thuật toán đi (và có thể thực sự là end nếu chuỗi gốc không có bản sao). Tôi để lại cho bạn thử thách xác định các yếu tố nào (3,2,2,1) ở trạng thái "không xác định" sau khi hoàn thành.

_{Gợi ý: điều gì đã được di chuyển? Điều gì đã bị bỏ qua? Điều gì đã bị ghi đè? Tại sao nó lại quan trọng? Hãy thử viết 0 trên khe đọc của bất kỳ thứ gì là đã di chuyển và xem những gì còn sót lại theo thứ tự từ last đến end.}

Answer 2

Thuật toán duy nhất rất đơn giản. Với phạm vi, [Thứ nhất, Cuối cùng), bạn sử dụng hai trình lặp, In và Out để loại bỏ các bản sao liên tiếp.In và Out ban đầu được gán cho phần tử đầu tiên trong chuỗi.

In = Out = First 

Thuật toán sau đó tiến hành như sau, miễn là phạm vi không trống.

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

Bây giờ, chỉ cần tiếp tục cho đến khi Đã đến cuối phạm vi. Sau đó, chúng tôi trả lại ++Out.

Out về cơ bản là trình vòng lặp đầu ra viết các phần tử duy nhất vào cùng một phạm vi, vì vậy chúng tôi có thể truy xuất trình lặp cuối cùng bằng cách tăng sau khi thuật toán trên hoàn tất. Nếu bạn không nghĩ về nó theo số , hãy thay đổi nhưng xuất để (và ghi đè) cùng một phạm vi. Phần khó khăn duy nhất là chúng tôi đang ghi đè cùng phạm vi mà chúng tôi đang đọc. Sẽ dễ dàng hơn khi nắm bắt thuật toán nếu bạn đang đẩy lùi các phần tử duy nhất vào một chuỗi khác và trả về chuỗi đó. Bây giờ bạn chỉ cần áp dụng một tối ưu hóa nhỏ để tránh yêu cầu một phạm vi đầu ra riêng biệt bằng cách ghi đè lên một trong những bạn đang đọc.

Dưới đây là triển khai nhanh, tôi đã cập nhật, điều này có thể dễ hiểu hơn phiên bản của nhà cung cấp. Đó là không có một số các fluff thông thường như tái sử dụng 'đầu tiên' như là iterator đầu vào, sử dụng toán tử! = (Thay vì! Và ==), v.v.

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; 
}