Mức độ phức tạp của std :: list :: splice và các container danh sách khác

Question

Tôi có một số mã giao dịch với các đối tượng std :: list khác nhau và hiện tại tôi đang sử dụng phương pháp chuyển giao nội dung không hiệu quả giữa chúng các phần tùy ý của một danh sách và di chuyển từng phần tử vào danh sách thứ hai). Tôi đã viết mã này một thời gian trước khi tôi đã nhận thức được chức năng std :: Danh mục :: nối, mà bây giờ tôi có ý định thay thế mã của tôi với, ví dụ:

list<string> list1, list2; 

list1.push_back("a"); 
list1.push_back("b"); 
list1.push_back("c"); // list1: "a", "b", "c" 

list<string>::iterator iterator1 = list1.begin(); 
iterator1++: // points to "b" 

list2.push_back("x"); 
list2.push_back("y"); 
list2.push_back("z"); // list2: "x", "y", "z" 

list<string>::iterator iterator2 = list2.begin(); 
iterator2++; // points to "y" 

list1.splice(iterator1, list2, iterator2, list2.end()); 

// list1: "a", "y", "z", "b", "c" 
// list2: "x" 

Tôi có một câu hỏi liên quan đến sự phức tạp của chức năng nối. Theo nguồn tin này:

http://www.cplusplus.com/reference/stl/list/splice/

Nó cần phải có độ phức tạp tuyến tính trong phạm vi giữa các yếu tố đầu tiên và cuối cùng được ghép trong (iterator2 và list2.end() trong ví dụ của tôi), và là nguồn gợi ý rằng điều này là do trước của trình lặp. Tôi có thể sống với điều này nhưng tôi đã hy vọng cho sự phức tạp liên tục.

giả định của tôi (trước khi tôi tìm thấy nguồn này) là các chức năng hàn làm một cái gì đó như thế này:

1. Sever mối liên hệ giữa "x" và "y"
2. Sever mối liên hệ giữa "z" và list2.end()
3. Hình thành một mối liên hệ giữa "x" và list2.end()
4. Sever mối liên hệ giữa "a" và "b"
5. Mẫu một mối liên hệ giữa "a" và "y"
6. Tạo liên kết giữa "y" và "b"

Do đó, khôi phục cả hai danh sách thành chuỗi hoàn chỉnh.

Nguyên tắc tương tự sẽ áp dụng cho các danh sách có kích thước tùy ý. Tôi không chắc chắn tôi thấy nơi có sự cần thiết cho các chức năng nối để thúc đẩy bất kỳ iterators, kể từ khi tôi cung cấp nó với tất cả các iterators nó cần phải làm công việc của nó.

Vì vậy, câu hỏi của tôi là, làm thế nào để đặc tả C++ đối phó với điều này? Liệu nó phá vỡ và tái tạo các liên kết chỉ ở điểm bắt đầu và kết thúc của mối nối, hay nó tiến lên từng liên kết từng cái một? Nếu sau này, có bất kỳ thùng chứa danh sách nào khác (ví dụ: từ QT) cung cấp trước đây không? Mã của tôi nằm bên trong vòng lặp bên trong của một chương trình mô phỏng, do đó, cho nó liên tục chứ không phải là sự phức tạp tuyến tính sẽ khá có giá trị.

Answer 1

Đây là một chủ đề rất gây tranh cãi trong quá trình chuẩn hóa C++ 11. Vấn đề là tất cả các thùng chứa tiêu chuẩn, kể cả danh sách, cũng có hoạt động size không đổi.

Trước C++ 11, nhiều lần triển khai thực hiện size thời gian tuyến tính và splice giữa các danh sách khác nhau theo thời gian cố định. C++ 11 hiện yêu cầu size không đổi và splice là tuyến tính.

Vấn đề là, nếu độ dài của phạm vi ghép không được tính từng cái một, thì các vùng chứa không thể theo dõi số lượng phần tử đã được xóa và thêm vào, và cuộc gọi tiếp theo tới size sẽ cần phục hồi thông tin này trong thời gian O (N) - sử dụng N lớn hơn của toàn bộ chuỗi, không chỉ là phần ghép nối.

Vùng chứa không chuẩn list có thể cung cấp hoạt động mong muốn, vì miễn là bạn không cần O (1) size, đối số của bạn là chính xác.

Đối với các thư viện khác ... Tôi không biết một, nhưng Boost nên có một. (Tôi đã kiểm tra, nó không, vì vậy một người nào đó bắt đầu!) Vì bạn hiểu rõ cách viết của riêng bạn, làm như vậy có thể ít nỗ lực hơn so với tranh chấp với một thư viện lớn như Qt.

Nếu bạn không cần an toàn luồng, bạn có thể triển khai trình bao bọc xung quanh std::list trong đó mỗi vùng chứa chỉ sở hữu một phần phụ của một danh sách đơn. Điều này sẽ loại bỏ hầu hết các nỗ lực lập trình trong việc tái tạo giao diện chuẩn.