Iterator để giá trị hoán vị

Question

Tôi có một cấu trúc đơn giản cho hoán vị:

struct Permutation 
{ 
    vector<string> items; // ["val_0", "val_1", "val_2", "val_3", "val_4"] 
    vector<short> permutationValue; // Let's say value is [4, 2, 0, 1, 3] 
} 

Tôi muốn để có thể sử dụng nó trong vòng phạm vi, như thế

for(string item: permutation){ 
{ 
    cout << item << endl; 
} 

cuối đầu ra dự kiến ​​nên là:

val_4 
val_2 
val_0 
val_1 
val_3 

Tôi nên triển khai phương pháp nào trong lớp học Permutation để đạt được điều đó?

Answer 1

Đây không phải là mã hoàn chỉnh cho vòng lặp về phía trước/sau/truy cập ngẫu nhiên nhưng đó là một nơi tốt để bắt đầu:

struct perm_iter { 
    const vector<short>& perm_; 
    const vector<string>& items_; 
    int idx_ {0}; 
    perm_iter(int idx, const vector<short>& perm, const vector<string>& items) 
    : idx_(idx) 
    , perm_(perm) 
    , items_(items) {} 

    perm_iter& operator++() { 
    idx_++; 
    return *this; 
    } 

    bool operator!=(const perm_iter& i) const { 
    return idx_ != i.idx_; 
    } 

    string operator*() { 
    return items_[perm_[idx_]]; 
    } 

}; 

struct Permutation 
{ 
    /* ... */ 
    perm_iter begin() { 
     return perm_iter(0, permutationValue, items); 
    } 

    perm_iter end() { 
     return perm_iter(items.size(), permutationValue, items); 
    } 

}; 

//usage: 
Permutation p; 
for (string s : p) 
    cout << s << endl; 

Answer 2

Bạn sẽ cần phải làm một chút công việc. Bạn cần phải thực hiện riêng lớp học của bạn tùy chỉnh iterator, và begin() và end():

struct Permutation 
{ 
    std::vector<std::string> items; 
    std::vector<short> permutationValue; 

    class iterator; 

    iterator begin(); 
    iterator end(); 

}; 

lớp iterator của bạn sẽ là một iterator truy cập ngẫu nhiên:

#include <iterator> 

class Permutation::iterator : public std::iterator<std::random_access_iterator_tag, std::string> 
{ 


}; 

Điều quan trọng là để kế thừa từ std::iterator, để cho trình biến đổi tùy chỉnh của bạn hoạt động chính xác với <algorithm>.

Có một số cách có thể để triển khai trình lặp. Nhưng ý tưởng chung là iterator của bạn sẽ lưu trữ một con trỏ đến đối tượng hoán vị của nó, và vị trí index hiện tại của mình, các thành viên lớp riêng của nó:

private: 
    Permutation *p; 
    size_t pos; 

operator* của nó được rõ ràng:

public: 
    std::string &operator*() const 
    { 
     return p->items[p->permutationValue[pos]]; 
    } 

Bạn sẽ cần triển khai tất cả toán tử vòng lặp khác, tăng/giảm truy cập trước trình lặp lặp ngẫu nhiên, toán tử ++, --, +, -, +=, -=, chỉ cần thêm hoặc trừ pos.

Bạn cũng sẽ cần phải thực hiện tất cả các toán tử so sánh cho lớp iterator của bạn: <, >, =, !=, <=, và >=, chỉ đơn giản bằng cách so sánh pos.

Các bit này sẽ hơi tẻ nhạt, nhưng không thể tránh khỏi. Bây giờ, tất cả những gì bạn phải làm là triển khai begin() và end() bằng cách tạo phiên bản trình lặp này, đặt pos ban đầu thành 0 hoặc items.size();. Bạn đã hoàn tất. Bây giờ bạn có thể sử dụng lặp lại phạm vi.

Để nhận thêm tín dụng, bạn cũng có thể triển khai const_iterator.

Kết luận: nó sẽ là một chút công việc, nhưng nó không phải là rất phức tạp.