Nhận trình lặp ngược lại từ trình lặp lặp mà không biết loại giá trị

Question

Tôi đang cố triển khai một số thuật toán sắp xếp kiểu STL. Nguyên mẫu cho std::sort trông giống như thế này (từ cplusplus.com):

template <class RandomAccessIterator> 
void sort (RandomAccessIterator first, RandomAccessIterator last); 

Chức năng thường được gọi như thế này (mặc dù các loại container có thể thay đổi):

std::vector<int> myVec; 
// Populate myVec 
std::sort(myVec.begin(), myVec.end()); 

Tôi lặp lại nguyên mẫu của std::sort cho chức năng phân loại của riêng tôi. Để lặp lại thông qua vùng chứa cần sắp xếp, tôi thực hiện như sau:

template <class RandomAccessIterator> 
void mySort(RandomAccessIterator first, RandomAccessIterator last) { 
    RandomAccessIterator iter; 
    for (iter = first; iter != last; ++iter) { 
    // Do stuff 
    } 
} 

Đủ dễ dàng. Nhưng nếu tôi muốn sử dụng một iterator ngược? Điều này sẽ thuận tiện trong các thuật toán sắp xếp vùng chứa từ cả hai đầu, ví dụ: cocktail sort.

Có cách nào để có trình lặp ngược lại từ các trình vòng lặp được chuyển vào làm tham số không? Nếu tôi biết loại thùng chứa trước, tôi có thể làm một cái gì đó như thế này:

template <class RandomAccessIterator> 
void mySort(RandomAccessIterator first, RandomAccessIterator last) { 
    std::vector<int>::reverse_iterator riter(last); 
    std::vector<int>::reverse_iterator rend(first); 
    for (; riter != rend; ++riter) { 
    // Do stuff 
    } 
}  

Thật không may, tôi không biết loại container. Những gì tôi thực sự cần phải làm là một cái gì đó như thế này:

template <class RandomAccessIterator> 
void mySort(RandomAccessIterator first, RandomAccessIterator last) { 
    RandomAccessIterator riter = reverse_iterator(last); 
    RandomAccessIterator rend = reverse_iterator(begin); 
    for (; riter != rend; ++riter) { 
    // Do stuff 
    } 
} 

Có một số cách để làm điều này mà không cần phải vượt qua trong vòng lặp ngược như tham số bổ sung (trong đó sẽ giải quyết được vấn đề, nhưng làm cho prototype hàm ít trực quan) ?

Lưu ý rằng tôi cần cả hai phía trước và lặp ngược trong việc thực hiện của tôi, vì vậy gọi hàm theo cách này

std::vector<int> myVec; 
// Populate myVec 
mySort(myVec.rbegin(), myVec.rend()); 

sẽ không hoạt động.

Answer 1

Các STL có std::reverse_iterator<Iterator>:

template <class RandomAccessIterator> 
void mySort(RandomAccessIterator first, RandomAccessIterator last) 
{ 
    typedef std::reverse_iterator<RandomAccessIterator> RIter; 
    RIter riter(last); 
    RIter rend(first); 
    for (; riter != rend; ++riter) { 
    // Do stuff 
    } 
} 

Một important note: Thông báo

tuy nhiên rằng khi một iterator bị đảo ngược, phiên bản đảo ngược không không trỏ đến cùng một nguyên tố trong khoảng , nhưng với cái trước nó. Điều này là như vậy, để sắp xếp cho phần tử cuối cùng của một phạm vi: Trình lặp lại trỏ đến phần tử trong một phạm vi, khi được đảo ngược, được thay đổi để trỏ đến phần tử (không quá khứ) của phạm vi (điều này sẽ là phần tử đầu tiên của dải nếu được đảo ngược). Và nếu một bộ lặp tới phần tử đầu tiên trong một dãy được đảo ngược, các điểm vòng lặp đảo ngược với phần tử trước phần tử đầu tiên ( này sẽ là phần tử cuối cùng của phạm vi nếu đảo ngược).

Answer 2

Kiểm tra phương thức cơ sở() của trình đảo ngược.