Khi tiêu đề yêu cầu.Tại sao push_back hoặc push_front vô hiệu hóa trình lặp của deque?
Sự hiểu biết của tôi về một deque là nó phân bổ "khối". Tôi không thấy cách phân bổ thêm không gian làm mất hiệu lực các trình vòng lặp, và nếu có điều gì, người ta sẽ nghĩ rằng các trình vòng lặp của deque sẽ có nhiều sự đảm bảo hơn là các vectơ, không ít hơn.
Tiêu chuẩn C++ không chỉ định cách triển khai thực hiện deque. Không cần thiết phải phân bổ không gian mới bằng cách phân bổ một đoạn mới và chuỗi nó vào những cái trước đó, tất cả những gì được yêu cầu là chèn ở mỗi đầu được phân bổ thời gian cố định.
Vì vậy, trong khi thật dễ dàng để xem cách triển khai deque sao cho nó đảm bảo bạn muốn [*], đó không phải là cách duy nhất để làm điều đó.
[*] Bộ lặp có tham chiếu đến một phần tử, cộng với tham chiếu đến khối đó để chúng có thể tiếp tục chuyển tiếp/lùi lại các đầu của khối khi chúng tiếp cận chúng. Cộng với tôi giả sử một tham chiếu đến deque chính nó, do đó operator+ có thể được thời gian không đổi như mong đợi cho iterator truy cập ngẫu nhiên - sau một chuỗi các liên kết từ khối để chặn là không đủ tốt.
deque không phải là danh sách, các khối không bị xích! – curiousguy
Ngay cả khi bạn đang phân bổ theo khối, chèn sẽ khiến đoạn cụ thể đó được phân bổ lại nếu không có đủ không gian (như trường hợp với vectơ).
Phân bổ lại là chìa khóa ở đây. – curiousguy
Điều quan trọng là không thực hiện bất kỳ giả định nào chỉ xử lý trình lặp như thể nó sẽ bị vô hiệu.
Ngay cả khi nó hoạt động tốt, phiên bản sau của trình biên dịch hoặc trình biên dịch cho một nền tảng khác có thể đi cùng và ngắt mã của bạn. Ngoài ra, một đồng nghiệp có thể đi cùng và quyết định biến deque của bạn thành một véc tơ hoặc danh sách liên kết.
Điều thú vị hơn nữa là push_back và push_front sẽ không vô hiệu hóa tài liệu tham khảo bất kỳ đến các yếu tố của một deque. Chỉ các trình vòng lặp được giả định là không hợp lệ.
Tiêu chuẩn, theo hiểu biết của tôi, không nêu rõ lý do. Tuy nhiên nếu một iterator được thực hiện đã nhận thức được hàng xóm ngay lập tức của nó - như một danh sách là - iterator đó sẽ trở thành không hợp lệ nếu nó trỏ đến một phần tử ở cả cạnh của deque và cạnh của một khối.
Một lý do khác mà tôi nghĩ là trình lặp có thể được thực hiện bằng cách giữ một chỉ mục của một phần tử. Nếu một cái gì đó được chèn vào đầu/cuối của deque, chỉ mục đó bây giờ không hợp lệ nữa (off-by-one), mặc dù bất kỳ con trỏ/tham chiếu đến phần tử mà nó trỏ đến vẫn còn hợp lệ, vì không có sự tái phân bổ xảy ra, khóa học). Tương tự khi chúng ta giữ trong chỉ mục vào một mảng các con trỏ khối (như tôi đoán trong bình luận của tôi về câu hỏi). –
Xem [answer] của tôi (http://stackoverflow.com/a/39420347/3903076) để có giải thích về điều này dựa trên việc thực hiện đơn giản. – filipos
Vì tiêu chuẩn cho biết có thể. Nó không ủy quyền rằng deque được thực hiện như một danh sách các khối. Nó yêu cầu một giao diện cụ thể với các điều kiện trước và sau cụ thể và mức độ phức tạp thuật toán cụ thể tối thiểu.
Người triển khai được tự do triển khai thực hiện mọi thứ theo bất kỳ cách nào họ chọn, miễn là nó đáp ứng tất cả các yêu cầu đó. Việc triển khai hợp lý có thể sử dụng danh sách các khối hoặc có thể sử dụng một số kỹ thuật khác với các lần cân bằng khác nhau.
Có thể không thể nói rằng một kỹ thuật hoàn toàn tốt hơn một kỹ thuật khác cho tất cả người dùng trong mọi tình huống. Đó là lý do tại sao tiêu chuẩn này cho phép người triển khai một số quyền tự do lựa chọn.
Tôi không nghĩ rằng bạn có nghĩa là một danh sách (ví dụ, std :: danh sách) của khối, như sau đó truy cập ngẫu nhiên iterators không thể là O (1). –
Một lướt qua lướt qua tại một triển khai cho thấy rằng một deque là giống như một std :: vector
Đoán của tôi. push_back/push_front có thể cấp phát một khối bộ nhớ mới. Một trình vòng lặp deque phải biết khi nào toán tử tăng/giảm nên nhảy vào khối tiếp theo. Việc thực hiện có thể lưu trữ thông tin đó trong bản thân trình lặp. Tăng/giảm một trình lặp cũ sau push_back/push_front có thể không hoạt động như dự định.
Mã này có thể hoặc không thể thất bại với lỗi thời gian chạy. Trên Visual Studio của tôi nó không thành công trong chế độ gỡ lỗi nhưng chạy đến kết thúc trong chế độ phát hành. Trên Linux nó gây ra lỗi phân đoạn.
#include <iostream>
#include <deque>
int main() {
std::deque<int> x(1), y(1);
std::deque<int>::iterator iterx = x.begin();
std::deque<int>::iterator itery = y.begin();
for (int i=1; i<1000000; ++i) {
x.push_back(i);
y.push_back(i);
++iterx;
++itery;
if(*iterx != *itery) {
std::cout << "increment failed at " << i << '\n';
break;
}
}
}
Trình lặp không chỉ là tham chiếu đến dữ liệu. Nó phải biết cách tăng, v.v.
Để hỗ trợ truy cập ngẫu nhiên, việc triển khai sẽ có một mảng con trỏ động cho các khối. Trình vòng lặp deque sẽ trỏ vào mảng động này. Khi deque phát triển, một đoạn mới có thể cần phải được phân bổ. Mảng động sẽ phát triển, làm mất hiệu lực các vòng lặp của nó và do đó, các trình vòng lặp của deque.
Vì vậy, nó không phải là khối được phân bổ lại, nhưng mảng con trỏ đến các khối có thể được. Thật vậy, như Johannes Schaub đã lưu ý, tài liệu tham khảo không bị vô hiệu.
Cũng lưu ý rằng đảm bảo vòng lặp của deque không nhỏ hơn của véc tơ, cũng không hợp lệ khi vùng chứa phát triển.
iirc, việc thực hiện deque của gcc giữ một mảng các con trỏ tới các khối đó ... Nếu mảng cần phải được phân bổ lại thì các trình vòng lặp có thể trở nên không hợp lệ. Có lẽ đó là lý do? Tôi không chắc ... Điều đó ít nhất là giải thích tại sao việc chèn thêm vào một trong hai đầu lặp lại không hợp lệ, nhưng không phải là các tham chiếu/con trỏ tới các phần tử. –