Xác định iterator của container của riêng tôi

Question

Tôi bị nhầm lẫn với một số khái niệm về việc xác định iterator của riêng tôi:

Từ này: http://www.cs.northwestern.edu/~riesbeck/programming/c++/stl-iterator-define.html, mà dường như đề nghị sử dụng lớp iterator bên trong đó xác định các nhà khai thác. Nhiều người khác kế thừa lớp cơ sở iterator để xác định lại các toán tử.

Tôi khá bối rối về phương pháp nào nên được sử dụng. Tại sao có

typedef ptrdiff_t difference_type; 

ví dụ: ở đầu định nghĩa lớp container?

Cảm ơn bạn rất nhiều!

Answer 1

Đặc tả C++ về chính xác một vùng chứa STL là nhiệm vụ mà bất kỳ loại vùng chứa STL nào có sẵn một số trường khác nhau. Một số, như begin() và end(), là các hàm, trong khi các số khác, chẳng hạn như iterator, là các loại. Những hạn chế này cũng áp dụng cho các trình vòng lặp. Điều này cho phép các hàm mẫu C++ nhìn vào các kiểu đối số của chúng để tìm kiếm nhiều thuộc tính hơn. Ví dụ, tất cả các kiểu vòng lặp STL phải định nghĩa một trường iterator_category có chứa kiểu mã hóa khả năng của chúng. Bằng cách này, các thuật toán STL có thể có các triển khai khác nhau của các hàm khác nhau dựa trên sức mạnh của các trình vòng lặp mà chúng chấp nhận. Ví dụ lớp là hàm distance, có hai trình lặp và trả về số khoảng trắng giữa chúng. Nếu đầu vào thấp hơn ForwardIterator hoặc BidirectionalIterator, điều này hoạt động bằng cách di chuyển các trình vòng lặp về phía trước và đếm số bước đã được thực hiện, chạy trong O (n). Nếu đầu vào là RandomAccessIterator thì các trình vòng lặp có thể được trừ để nhận kết quả trong O (1).

May mắn thay, bạn thường không phải liệt kê rõ ràng tất cả các typedef. Có một loại tiện ích trong tiêu đề <iterator> được gọi là iterator được tham số hóa trên nhiều đối số khác nhau. Nếu bạn xác định một loại trình vòng lặp tùy chỉnh, bạn có thể kế thừa từ iterator để tự động nhập tất cả thông tin này. Về cơ bản, đây là cách nhanh nhất để có tất cả các typedef s tại chỗ.

Đối với các nhà khai thác những gì bạn cần để quá tải, ở một mức tối thiểu bạn cần phải nhận được ++ (tiền tố và hậu tố), ==, !=, * (con trỏ dereference), và -> xác định. Tất cả các loại trình vòng lặp đều hỗ trợ điều này. Đối với các trình vòng lặp hai chiều hoặc cao hơn, bạn cũng cần có -- được xác định (tiền tố và hậu tố). Cuối cùng, cho lặp ngẫu nhiên truy cập, bạn nên hỗ trợ [], +, +=, - (sao lưu nhiều bước và trừ hai vòng lặp), -=, <, >, <=, và >=.

Hy vọng điều này sẽ hữu ích!

Answer 2

Mặc dù câu trả lời của @ templattypedef là chính xác, có lẽ tôi có thể làm rõ tình hình một chút.

Trình lặp thường được định nghĩa là lớp lồng nhau bên trong vùng chứa. std::iterator thường được sử dụng như một lớp cơ sở để giúp bạn dễ dàng xác định lớp trình vòng lặp của mình. Bạn không bao giờ thực sự có để sử dụng std::iterator - nó chỉ ở đó để làm cho công việc dễ dàng hơn một chút và (đặc biệt) giảm số lượng mã bạn cần nhập.

Answer 3

Mặc dù sử dụng std::iterator có thể trợ giúp với typedef s, nó chắc chắn không giúp ích gì cho việc triển khai thực tế.

Thư viện Boost.Iterator có rất nhiều điều tốt cho điều này, và tôi sẽ đề nghị đọc về boost::iterator_adaptor giúp giảm đáng kể số lượng mã bạn cần nhập để xác định trình lặp mới trên đầu trang của một cái cũ.