Các quy tắc cho Iterator Invalidation

Question

Các quy tắc thông thường cho việc vô hiệu hóa Iterator khi vận hành trên các lớp chứa STL (Vector, Dequeue, danh sách, bản đồ, multimap, set, multiset) là gì. Có thể phân loại và tổng hợp một số quy tắc/nguyên tắc chung mà một lập trình viên C++ STL phải biết khi làm việc với các thùng chứa và các bộ lặp của chúng không?

Answer 1

Các quy tắc này là vùng chứa cụ thể. Trên thực tế, đây là những tiêu chí quan trọng để quyết định bạn sử dụng vùng chứa nào. Ví dụ, các trình vòng lặp đến một std::vector có thể bị vô hiệu khi đối tượng được chèn vào (phụ thuộc vào vị trí đối tượng được chèn vào và nếu sự tái phân bổ xảy ra), và chúng bị vô hiệu khi một đối tượng bị xóa trước trình lặp. An std::list không có vấn đề này. Chèn và loại bỏ các đối tượng (ngoại trừ đối tượng mà trình vòng lặp trỏ tới) không làm mất hiệu lực trình lặp.

SGI cung cấp tốt documentation về điều này.

Answer 2

Quy tắc vô hiệu được lấy cảm hứng từ Cấu trúc dữ liệu và thuật toán được sử dụng để triển khai các vùng chứa này. Nếu bạn không có kế hoạch để tìm hiểu các nguyên tắc cơ bản, sau đó bạn sẽ cần phải nhớ tài liệu về vòng lặp của trái tim.

Chuẩn C++ xác định hành vi của iterator theo cách làm cho nó có thể để triển khai với các con trỏ C đơn giản. Nó không yêu cầu thư viện thực sự sử dụng con trỏ; nó chỉ đơn giản là làm cho nó có thể làm như vậy.

Về cơ bản, một iterator không còn giá trị nếu một hoạt động gây ra một yếu tố cơ bản lưu trữ (một mảng đống sử dụng trong một vector, một nút danh sách liên kết được sử dụng trong một list, hoặc một nút cây được sử dụng trong một map hoặc set) là deallocated, hoặc shifed vào một vị trí bộ nhớ khác nhau.

A vector thường được triển khai bằng cách phân bổ mảng từ bộ nhớ động (đống). Để giảm số lượng phân bổ lại, mảng luôn được phân bổ với một số dấu gạch ngang, tức là không gian không sử dụng ban đầu. Khi các phần tử được thêm vào mảng, không gian chùng được sử dụng hết. Khi tất cả các không gian slack đã được đưa lên và một phần tử mới cần được chèn vào, thì một mảng mới có kích thước lớn hơn sẽ được cấp phát. Điều này sẽ gây ra sự vô hiệu của tất cả các trình vòng lặp trỏ đến mảng cũ.

Tương tự, khi một phần tử bị xóa khỏi một vector, điều này sẽ làm cho tất cả các phần tử tiếp theo được sao chép về phía trước. Một trình vòng lặp trỏ đến các phần tử đã dịch chuyển sẽ vẫn tham chiếu cùng một chỉ mục trong mảng, nhưng chỉ mục đó bây giờ chứa một phần tử khác. Đây cũng là một ví dụ về sự vô hiệu.

Đối với list, map và set, nút cây hoặc nút danh sách vẫn hợp lệ cho đến khi phần tử chứa trong đó bị xóa. Lưu ý rằng một trình vòng lặp trỏ đến một nút bị vô hiệu hóa không thể được sử dụng cho bất cứ điều gì; thậm chí không tăng/giảm số lần lặp. Điều này là do trong danh sách liên kết hoặc thực thi cây, trình vòng lặp phụ thuộc vào các con trỏ được lưu trữ trong chính nút đó.

Để luôn đảm bảo hoạt động chính xác, tiêu chuẩn được diễn đạt một cách hạn chế hơn là sử dụng cấu trúc dữ liệu đơn giản (điều này mang lại tự do hơn cho người triển khai thư viện để sử dụng cấu trúc dữ liệu nâng cao hơn). Ví dụ: xem http://c2.com/cgi/wiki?IteratorInvalidationProblem và http://www.threadingbuildingblocks.org/codesamples.php.