Điều gì cho phép gỡ lỗi vòng lặp STL thực sự làm gì?

Question

Tôi đã kích hoạt iterator gỡ lỗi trong một ứng dụng bằng cách định nghĩa

_HAS_ITERATOR_DEBUGGING = 1 

tôi đã mong đợi này để thực sự chỉ cần kiểm tra giới hạn vector, nhưng tôi có cảm giác nó đang làm một nhiều hơn thế nữa. Những gì kiểm tra, vv thực sự đang được thực hiện?

Dinkumware STL, nhân tiện.

Answer 1

Có một số hoạt động với vòng lặp mà dẫn đến hành vi không xác định, mục tiêu của cò này là để kích hoạt kiểm tra thời gian chạy để ngăn chặn nó từ xảy ra (sử dụng khẳng định).

Vấn đề

Các hoạt động rõ ràng là sử dụng một iterator không hợp lệ, nhưng vô hiệu này có thể phát sinh từ nhiều lý do:

• Unitialized iterator
• Iterator đến một yếu tố đó đã bị xóa
• Iterator đến một yếu tố có vị trí thực đã thay đổi (phân bổ lại cho vector)
• Iterator ngoài [begin, end)

Các tiêu chuẩn chính xác chi tiết đớn cho mỗi container hoạt động làm mất hiệu lực mà iterator.

Có một lý do nào đó ít rõ ràng mà mọi người có xu hướng quên: trộn lặp để container khác nhau:

std::vector<Animal> cats, dogs; 

for_each(cats.begin(), dogs.end(), /**/); // obvious bug 

này liên quan đến một vấn đề tổng quát hơn: tính hợp lệ của dãy truyền cho thuật toán.

• [cats.begin(), dogs.end()) không hợp lệ (trừ trường hợp một là một bí danh cho người khác)
• [cats.end(), cats.begin()) không hợp lệ (trừ khi cats trống ??)

Giải pháp

Các giải pháp bao gồm trong việc thêm thông tin vào các trình vòng lặp sao cho tính hợp lệ của chúng và tính hợp lệ của các phạm vi mà chúng đã định nghĩa có thể được khẳng định trong quá trình thực thi do đó ngăn không được xác định hành vi xảy ra.

Biểu tượng _HAS_ITERATOR_DEBUGGING đóng vai trò như một trình kích hoạt cho khả năng này, vì không may làm chậm chương trình. Nó khá đơn giản về mặt lý thuyết: mỗi vòng lặp được tạo thành Observer của vùng chứa được phát hành và do đó được thông báo về sửa đổi.

Trong Dinkumware này được thực hiện bằng hai bổ sung:

• Mỗi iterator mang một con trỏ đến thùng liên quan của nó
• Mỗi container chứa một danh sách liên kết của vòng lặp nó tạo

Và đây giải quyết gọn gàng các vấn đề của chúng tôi:

• Trình lặp đơn lẻ hóa không có thùng chứa chính, hầu hết các hoạt động (ngoài việc phân công và hủy) sẽ kích hoạt xác nhận
• Trình lặp đến một phần tử đã xóa hoặc di chuyển đã được thông báo (nhờ danh sách) và biết tính vô hiệu của nó
• Khi tăng và giảm một trình lặp nó có thể kiểm tra nó nằm trong giới hạn
• Kiểm tra 2 vòng lặp thuộc về cùng một vùng chứa đơn giản như việc so sánh các con trỏ cha của chúng
• Kiểm tra tính hợp lệ của một phạm vi cũng đơn giản như việc kiểm tra chúng ta đến cuối phạm vi trước khi chúng tôi đến cuối thùng chứa (hoạt động tuyến tính cho những thùng chứa không thể truy cập ngẫu nhiên, do đó hầu hết trong số đó)

Chi phí

Chi phí là nặng, nhưng không đúng đắn có giá? Chúng ta có thể phá vỡ các chi phí mặc dù:

• cấp phát bộ nhớ thêm (danh sách thêm vòng lặp duy trì): O(NbIterators)
• quá trình thông báo về hoạt động đột biến: O(NbIterators) (Lưu ý rằng push_back hoặc insert không nhất thiết làm mất hiệu lực lặp, nhưng erase không)
• phạm vi hiệu lực kiểm tra: O(min(last-first, container.end()-first))

Hầu hết các thuật toán thư viện đã đương nhiên được thực hiện f hoặc hiệu quả tối đa, thông thường kiểm tra được thực hiện một lần và cho tất cả ở đầu thuật toán, sau đó một phiên bản không được kiểm soát được chạy.Tuy nhiên, tốc độ có thể làm chậm nghiêm trọng xuống, đặc biệt là với vòng tay bằng văn bản:

for (iterator_t it = vec.begin(); 
    it != vec.end();    // Oups 
    ++it) 
// body 

Chúng tôi biết Oups dòng là hương vị xấu, nhưng ở đây nó thậm chí còn tồi tệ hơn: tại mỗi lần chạy vòng lặp, chúng ta tạo ra một mới iterator sau đó phá hủy nó có nghĩa là phân bổ và deallocating một nút cho danh sách các vòng lặp của vec ... Tôi có phải gạch chân chi phí phân bổ/deallocating bộ nhớ trong một vòng lặp chặt chẽ?

Tất nhiên, for_each sẽ không gặp phải vấn đề như vậy, đây là một trường hợp hấp dẫn khác đối với việc sử dụng thuật toán STL thay vì các phiên bản được mã hóa bằng tay.

Answer 2

Theo như tôi hiểu:

_HAS_ITERATOR_DEBUGGING sẽ hiển thị một hộp thoại vào thời gian chạy để khẳng định việc sử dụng lặp không chính xác bao gồm:

1) Vòng lặp được sử dụng trong một container sau khi một phần tử được xoá hoàn toàn

2) Vòng lặp được sử dụng trong các vectơ sau một .push() hoặc .insert() hàm được gọi

Answer 3

Theo http://msdn.microsoft.com/en-us/library/aa985982%28v=VS.80%29.aspx

Tiêu chuẩn C++ mô tả các hàm thành viên nào gây ra trình vòng lặp cho vùng chứa để trở thành không hợp lệ. Hai ví dụ là:

• Xóa phần tử khỏi vùng chứa làm cho trình biến đổi thành phần tử không hợp lệ.
• Tăng kích thước của vec-tơ (đẩy hoặc chèn) khiến các trình vòng lặp vào vùng chứa vector trở nên không hợp lệ.