2013-08-28 58 views
7

Tôi đã cố gắng ra một cái gì đó đơn giản như thế này:Làm thế nào để bạn vượt qua một mảng :: ::?

template<class T> 
array insertionSort(array<T> arr) { 

    for (int index = 1; index < arr.size(); index++) { 
     for (int insertion = index; insertion > 0 && array[insertion - 1] > array[insertion]; insertion--) { 
      std::swap(array[insertion - 1], array[insertion]); 
     } 
    } 

    return arr; 
} 

void main() { 
    array<int, 10> mine = { 1, 0, 2, 9, 3, 8, 4, 7, 5, 6 }; 

    array result = insertionSort<int>(mine); 

    cin.get(); 
} 

Có vẻ như mảng đòi hỏi hai tham số kiểu (các type cũng như size), vì vậy làm thế nào để vượt qua nó đến và đi từ một chức năng mà không biết kích thước lên phía trước?

+2

Làm cho kích thước tham số mẫu cũng vậy! Phải thừa nhận rằng, hầu hết thời gian bạn sẽ được tốt hơn đi qua vòng lặp và trừu tượng hóa các thuật toán của bạn từ bất kỳ đại diện cụ thể. Ví dụ, mã trên cũng nên làm việc cho 'std :: deque ', 'std :: vector ', v.v. –

+1

'Làm cho kích thước tham số mẫu', duh! Cảm ơn – sircodesalot

+0

Đặt kích thước làm thông số mẫu như @ DietmarKühl đề xuất nhưng sử dụng nó trong vòng lặp đầu tiên thay vì arr.size(). –

Trả lời

20

Nói chung, bạn không thực sự muốn vượt qua các thùng chứa xung quanh! Thuật toán tương tự hoạt động cho std::array<T, N> cũng hoạt động với các cấu trúc dữ liệu khác, ví dụ: std::vector<T> hoặc std::deque<T>. Cách tiếp cận C++ trong trường hợp đó là chuyển qua trình lặp và [hơi] điều chỉnh thuật toán:

template<typename BidrectionalIterator> 
void insertionSort(BidirectionalIterator begin, BidirectionalIterator end) { 
    for (BidirectionalIterator it(begin); it != end; ++it) { 
     for (BidirectionalIterator insertion(it), tmp(insertion); 
      begin != insertion && *--tmp > *insertion; --insertion) { 
      std::swap(*tmp, *insertion); 
     } 
    } 
} 

(Tôi đã không xác minh rằng thuật toán thực sự hoạt động nhưng bạn có ý tưởng).

Lưu ý rằng thuật toán cố ý sắp xếp chuỗi tại chỗ! Nếu bạn muốn tạo một bản sao đã sắp xếp, hãy tạo bản sao và sắp xếp: theo cách này bạn có thể lựa chọn để thực hiện tại chỗ hoặc không bị ép buộc sử dụng phương pháp có thể yêu cầu bộ nhớ quá mức (OK, khi trình tự lớn, bạn chắc chắn không muốn sử dụng thuật toán này nhưng đó là một câu hỏi riêng biệt).

+0

Thật thú vị. Tôi đang học hỏi rất nhiều về từ câu hỏi đơn giản này. – sircodesalot

+1

+1, Đây là câu trả lời đúng. –

+1

Yup câu trả lời này chắc chắn là tốt hơn, mọi chức năng trong tiêu đề thuật toán sẽ lặp lại không phải là container – aaronman

10

Nó hoạt động theo cách tương tự như truyền đối tượng mà không biết loại lên phía trước. Bạn sử dụng một mẫu tham số:

template<class T, size_t arrSize> 
std::array<T, arrSize> insertionSort(std::array<T, arrSize> arr) { 

    for (int index = 1; index < arrSize; index++) { 
     for (int insertion = index; insertion > 0 && array[insertion - 1] > array[insertion]; insertion--) { 
      std::swap(array[insertion - 1], array[insertion]); 
     } 
    } 

    return arr; 
} 
+0

Tuyệt vời. Rất vui vì tôi đã hỏi. Cảm ơn – sircodesalot

3

IMO, bạn nên chỉ cần vượt qua kích thước như một tham số mẫu và sử dụng nó trong vòng lặp thay vì arr.size():

template<class T, size_t size> 
array<T, size> insertionSort(array<T> arr) { 

    for (int index = 1; index < size; index++) { 
     for (int insertion = index; insertion > 0 && array[insertion - 1] > array[insertion]; insertion--) { 
      std::swap(array[insertion - 1], array[insertion]); 
     } 
    } 

    return arr; 
} 

void main() { 
    array<int, 10> mine; mine.fill(0); 

    array<int, mine.size()> result = insertionSort<int, mine.size()>(mine); 

    cin.get(); 
} 
+1

'mine.size()' dường như không hoạt động (bởi vì nó không phải là một giá trị không đổi). – sircodesalot

+0

Sau đó, có thể một khai báo 'const int arraySize = mine.size()' –

+0

@sircodesalot: Có nhiều khả năng trình biên dịch của bạn không thực hiện 'constexpr' đúng (hoặc ở tất cả nếu nó là Visual Studio). 'mảng :: size' là' constexpr'. Vì vậy, đó phải là hợp pháp. Mặc dù cá nhân, bạn chỉ nên sử dụng 'tự động'. Hoặc tốt hơn, sử dụng 'std :: sort', thay vì sao chép mảng xung quanh. –

Các vấn đề liên quan