Làm cách nào để tạo một trình vòng lặp trên một số danh sách được sắp xếp?

Question

Ok, vì vậy đây là câu hỏi phỏng vấn mà tôi nhận được và chỉ thực hiện tầm thường vào thời điểm đó. Tôi tự hỏi giải pháp tối ưu là gì và cách nó được triển khai tốt nhất.

Bạn được cung cấp nhiều danh sách được sắp xếp, xây dựng một cái gì đó cho phép chúng tôi lặp qua tất cả các danh sách này từ nhỏ nhất đến phần tử lớn nhất.

Ví dụ:

{ -2, 5, 10} 
{ 2, 9, 11} 
{ -5, 9} 


-> -5, -2, 2, 5, 9, 9, 10, 11 

Cập nhật:

Với một chút sự giúp đỡ từ các SO trò chuyện # c-hỏi-và-câu trả lời và @Nican nói riêng, tôi đã nhận được tàu này bay bằng cách nào đó. Tôi đã đăng mã làm việc của tôi như là một câu trả lời để cho phép các giải pháp khác là tốt.

Câu trả lời tôi đã đăng bên dưới vẫn còn lộn xộn và cụ thể là tôi chưa triển khai == và! = Chính xác. Tôi vẫn cần giúp đỡ về những thứ đó.

Biện minh cho câu hỏi này

Tìm việc triển khai iterator tùy chỉnh sạch và Minimalistic trực tuyến mà không phải là phổ biến. Và tôi tin rằng câu hỏi này có thể phục vụ như là một điểm khởi đầu tốt cho những người khác để nâng cao hiểu biết của họ về vòng lặp và thực hành tốt nhất.

Answer 1

Đây không phải là một câu trả lời hoàn chỉnh

Tôi đã thực hiện một phần giải pháp cho thời điểm đó nó hoạt động. Đây không phải là một triển khai hoàn chỉnh, cũng không chính xác trong các dòng với các yêu cầu của một input_iterator. Điều này minh họa quan điểm, và việc còn lại là tùy thuộc vào bất cứ ai cảm thấy cuộc gọi.

-

Tôi vừa chọn lại từ ghi chú và nỗ lực của mình hôm qua. Tôi đã nhận được một số trợ giúp thực sự tốt đẹp từ Nican.

Tôi đang sử dụng một đống để giữ các danh sách bên trong cấu trúc của mình. (Trong đó có các phê bình hợp lệ mà tôi đang tái phát minh priority_queue). Có một vài điều vẫn còn thiếu ở đây, trong số những thứ khác:

• Sao chép constructor
• Post-sửa chữa ++ hành
• == đúng và = thực hiện, tôi chỉ so sánh quy mô!.
• Điều này có thể dễ dàng trở thành người chuyển tiếp.

Tôi đã đạt được điểm mà tôi đã xây dựng hiểu biết về trình vòng lặp của mình. Và điều này là xa như tôi sẽ mất nó trong thời gian này.

#include <algorithm> 
#include <forward_list> 
#include <iostream> 
#include <iterator> 
#include <string> 
#include <vector> 

template <typename Iter> 
struct SortedListIterItem { 
    Iter it_beg; 
    Iter it_end; 
    /* Used by the heap to sort ascending */ 
    bool operator<(const SortedListIterItem<Iter>& other) { 
    return *it_beg > *other.it_beg; 
    } 
    bool operator==(const SortedListIterItem<Iter>& other) { 
    return it_beg == other.it_begin && it_end == *other.it_beg; 
    } 
    SortedListIterItem<Iter>(Iter _begin, Iter _end) 
     : it_beg(_begin), it_end(_end){}; 
}; 

template <typename Iter> 
class SortedListsIter { 
    // member typedefs provided through inheriting from std::iterator 
    class iterator { 
    std::vector<SortedListIterItem<Iter> > m_items; 

    public: 
    iterator(std::vector<SortedListIterItem<Iter> > _items = {}) 
     : m_items(_items){}; 
    iterator& operator++() { 
     std::pop_heap(m_items.begin(), m_items.end()); 
     SortedListIterItem<Iter>& largest = m_items.back(); 

     if (++largest.it_beg == largest.it_end) { 
     m_items.pop_back(); 
     } else { 
     std::push_heap(m_items.begin(), m_items.end()); 
     } 
     return *this; 
    } 
    // iterator traits 
    using value_type = typename Iter::value_type; 
    using pointer = typename Iter::pointer; 
    using reference = typename Iter::reference; 
    using iterator_category = std::input_iterator_tag; 
    /** A simplified comparator, which is not a correct implementation. 
    * While it does work for regular for loops. */ 
    bool operator!=(iterator other) { 
     return (m_items.size() != other.m_items.size()); 
    } 
    value_type operator*() const { 
     return *(m_items.front().it_beg); 
    }; 
    }; 
    std::vector<SortedListIterItem<Iter> > m_items; 

public: 
    void add_list(Iter it_begin, Iter it_end) { 
    if (it_begin != it_end) { 
     m_items.push_back(SortedListIterItem<Iter>(it_begin, it_end)); 
     std::push_heap(m_items.begin(), m_items.end()); 
    } 
    // Ignore empty lists. 
    } 
    iterator begin() { return iterator(m_items); }; 
    iterator end() { 
    std::vector<SortedListIterItem<Iter> > _items; 
    return iterator(_items); 
    }; 
}; 

int main(int argc, char** argv) { 
    std::forward_list<std::string> animals = {"Cat", "Dog", "Horse"}; 
    std::forward_list<std::string> fish = {"Dolphin", "Mermaid", "Shark"}; 
    std::forward_list<std::string> birds = {"Crow", "Duck", "Eagle"}; 
    SortedListsIter<std::forward_list<std::string>::iterator> my_string_iter; 
    my_string_iter.add_list(fish.begin(), fish.end()); 
    my_string_iter.add_list(animals.begin(), animals.end()); 
    my_string_iter.add_list(birds.begin(), birds.end()); 

    for (auto i : my_string_iter) { 
    std::cout << " " << i << ","; 
    } 
    std::cout << std::endl; 
    for (auto i : my_string_iter) { 
    std::cout << " " << i << ","; 
    } 
    std::cout << std::endl; 

    std::vector<int> l4 = {1, 2, 99}; 
    std::vector<int> l5 = {-11, -4, 3}; 
    std::vector<int> l6 = {-5, 1}; 

    SortedListsIter<std::vector<int>::iterator> my_iter2; 
    my_iter2.add_list(l4.begin(), l4.end()); 
    my_iter2.add_list(l5.begin(), l5.end()); 
    my_iter2.add_list(l6.begin(), l6.end()); 

    for (auto i : my_iter2) { 
    std::cout << " " << i << ","; 
    } 
    std::cout << std::endl; 

    return 0; 
} 

Answer 2

Tôi nghĩ rằng SortedListsIter::iterator nên chứa một bản sao của tất cả các mặt hàng, chứ không phải là tài liệu tham khảo, do đó bạn có thể ForwardIterator thay vì InputIterator.Bạn cũng tránh được những tài liệu tham khảo lơ lửng trong iterator cuối (mà có thể là một iterator mặc định được xây dựng, như iterator::iterator(std::vector<SortedListIterItem<Iter> > _items = {}) : m_items(_items){};)

Hai đống có thể khác nhau theo thứ tự của các yếu tố, vì vậy chúng tôi sử dụng std::is_permutation để xác định sự bình đẳng

bool SortedListsIter::iterator::operator==(iterator other) 
{ return std::is_permutation(m_items.begin(), m_items.end(), other.m_items.begin(), other.m_items.end()); } 

C++ 11 thay thế (4 phiên bản lặp để kiểm tra khoảng cách không có sẵn):

bool SortedListsIter::iterator::operator==(iterator other) 
{ return (std::distance(m_items.begin(), m_items.end()) == std::distance(other.m_items.begin(), other.m_items.end())) 
     && std::is_permutation(m_items.begin(), m_items.end(), other.m_items.begin()); } 

mục bình đẳng rất đơn giản:

bool SortedListIterItem::operator==(SortedListIterItem other) 
{ return (it_beg == other.it_beg) && (it_end == other.it_end); }