Tách danh sách STL?

Question

Tôi có một danh sách liên kết hình tròn trông giống như thế này:

4 -> 3 -> 2 -> 5 -> 0 -> 1 -> beginning

Tôi muốn chia danh sách này thành hai đoạn, đảo ngược một trong những phân đoạn, và sau đó gia nhập lại danh sách. Một cái gì đó như thế này:

Split, một O (1) hoạt động 4 ** 3 -> 2 -> 5 ** 0 -> 1 -> beginning

Xếp, một O (n) hoạt động 0 ** 3 -> 2 -> 5 ** 4 -> 1 -> beginning

nỗi, một O (1) hoạt động 0 -> 3 -> 2 -> 5 -> 4 -> 1 -> beginning

STL dường như không có một danh sách liên kết vòng tròn, nhưng tôi hy vọng tôi có thể thoát khỏi với đại diện cho danh sách như là một (chuyển tiếp) danh sách. Này, yêu cầu: * Một cách để phân chia các danh mục vào danh sách con * Một cách để hợp nhất danh sách với nhau

Kết hợp các danh sách con cùng nhau nên dễ sử dụng std::list::splice, và nó phải là một O (1) hoạt động. Yay!

Tuy nhiên, tôi không thể tìm thấy cách O (1) tốt để chia danh sách thành danh sách phụ. One approach là sử dụng trình vòng lặp, nhưng tôi không nghĩ rằng nó hoạt động trong trường hợp của tôi vì danh sách con đi ra khỏi danh sách và tiếp tục lại ở đầu danh sách.

Có cách nào hiệu quả để triển khai thuật toán này bằng STL không? Hay tôi nên từ bỏ và viết thư viện danh sách liên kết tròn của riêng mình?

Cảm ơn!

Answer 1

Tôi không chắc chắn như thế nào hữu ích này, nhưng ở đây nó là:

template<typename I> 
void inner(I b, I e) 
{ 
    std::reverse(b, e); // l = {4 5 2 3 0 1} 
} 

template<typename L, typename I> 
void outer(L& l, I b, I e) 
{ 
    l.splice(l.begin(), l, e, l.end()); // l = {0 1 4 3 2 5} 
    std::reverse(l.begin(), b);   // l = {4 1 0 3 2 5} 
} 

int main() 
{ 
    std::list<int> t, l{4, 3, 2, 5, 0, 1}; 
    std::cout << l << std::endl; 

    auto b = l.begin(), e = l.begin(); 
    std::advance(b, 1); 
    std::advance(e, 4); 
    bool in = true; 

    in ? inner(b, e) : outer(l, b, e); 
    std::cout << l << std::endl; 
} 

Có hai lựa chọn:

• đảo ngược nội phần của danh sách (3 2 5)
• đảo ngược bên ngoài một phần (0 1 -> 4)

và bạn có thể muốn đảo ngược đoạn ngắn hơn, nhưng bạn sẽ phải tính cho điều này, đó là thời gian tuyến tính. Tôi đã viết hai hàm riêng biệt inner,outer cho hai tác vụ này.

inner rất đơn giản (không có gì ngoài trình bao bọc) và hoạt động như mong đợi. Tuy nhiên, outer là để lại danh sách trong một trạng thái tương đương với dự kiến ​​modulo một số luân phiên (dịch chuyển tròn). Nếu bạn đang lập mô hình một danh sách vòng tròn, điều này sẽ ổn. Nhưng nếu bạn muốn đầu ra chính xác như trong ví dụ của bạn, bạn sẽ phải đếm lại, để tìm đúng điểm để xoay. Tôi sẽ tránh điều này, vì nó là thời gian tuyến tính.

Lưu ý rằng không cần chia tách, bởi vì đảo ngược được đặt tại chỗ. Ngoài ra, hoạt động

l.splice(l.begin(), l, e, l.end()); 

là không đổi.

Kiểm tra live example.