C++ std :: vector <> :: iterator không phải là một con trỏ, tại sao?

Question

Chỉ cần một chút giới thiệu, với những từ đơn giản. Trong C++, các trình vòng lặp là "thứ" mà bạn có thể viết ít nhất toán tử dereference *it, toán tử tăng ++it và cho các trình vòng lặp hai chiều nâng cao hơn, số giảm --it và cuối cùng nhưng không kém phần quan trọng. chỉ số it[] và có thể cộng và trừ.

"Những thứ" như vậy trong C++ là đối tượng của các loại có quá tải theo toán tử hoặc các con trỏ đơn giản và đơn giản.

std::vector<> là một lớp chứa bao quanh một mảng liên tục, vì vậy con trỏ như trình vòng lặp có ý nghĩa. Trên lưới, và trong một số tài liệu bạn có thể tìm thấy vector.begin() được sử dụng như một con trỏ.

Lý do để sử dụng con trỏ là chi phí thấp hơn, hiệu suất cao hơn, đặc biệt nếu trình biên dịch tối ưu phát hiện lặp lại và thực hiện điều đó (hướng dẫn vector và nội dung). Sử dụng trình vòng lặp có thể khó hơn cho trình biên dịch để tối ưu hóa.

Biết điều này, câu hỏi của tôi là tại sao việc triển khai STL hiện đại, giả sử MSVC++ 2013 hoặc libstdC++ trong Mingw 4.7, sử dụng lớp đặc biệt cho trình lặp vector?

Answer 1

Bởi vì STL được thiết kế với ý tưởng rằng bạn có thể viết một cái gì đó lặp trên một iterator, dù iterator đó chỉ tương đương với một con trỏ đến một phần tử của mảng bộ nhớ tiếp giáp (như std::array hoặc std::vector) hoặc một cái gì đó như danh sách được liên kết, một bộ khóa, thứ gì đó được tạo khi đang di chuyển, v.v.

Ngoài ra, đừng bị lừa: Trong trường hợp vectơ, dereferencing có thể (không có tùy chọn gỡ lỗi) không thể khắc phục con trỏ dereference, do đó, thậm chí sẽ không có chi phí sau khi biên dịch!

Answer 2

Việc triển khai trình lặp là triển khai được xác định, miễn là đáp ứng các yêu cầu của tiêu chuẩn. Nó có thể là một con trỏ cho vector, có thể hoạt động. Có nhiều lý do để không sử dụng con trỏ;

• nhất quán với các vật chứa khác.
• gỡ lỗi và kiểm tra lỗi hỗ trợ
• độ phân giải quá tải, lặp lớp dựa cho phép quá tải để làm việc phân biệt chúng từ gợi ý đơn giản

Nếu tất cả các vòng lặp là con trỏ, sau đó ++it trên map sẽ không tăng nó để phần tử tiếp theo vì bộ nhớ không bắt buộc phải không tiếp giáp. Quá khứ bộ nhớ tiếp giáp của std:::vector hầu hết các thùng chứa tiêu chuẩn yêu cầu con trỏ "thông minh hơn" - do đó lặp.

Yêu cầu vật lý của vòng lặp dove rất phù hợp với yêu cầu logic mà chuyển động giữa các thành phần đó là "thành ngữ" được xác định rõ ràng của chúng, không chỉ di chuyển đến vị trí bộ nhớ tiếp theo.

Đây là một trong những yêu cầu thiết kế ban đầu và mục tiêu của STL; mối quan hệ trực giao giữa các thùng chứa, các thuật toán và kết nối hai thông qua các vòng lặp.

Bây giờ chúng là các lớp, bạn có thể thêm toàn bộ máy chủ kiểm tra lỗi và kiểm tra độ chính xác để gỡ lỗi mã (và sau đó xóa nó để có mã phát hành tối ưu hơn).

---

Với lớp khía cạnh tích cực lặp dựa mang, tại sao nên hay nên bạn không chỉ cần sử dụng con trỏ cho std::vector lặp - nhất quán. Việc triển khai sớm std::vector đã thực sự sử dụng con trỏ đồng bằng, bạn có thể sử dụng chúng cho vector. Một khi bạn phải sử dụng các lớp cho các trình vòng lặp khác, với các giá trị tích cực mà chúng mang lại, áp dụng cho vector trở thành một ý tưởng tốt.

Answer 3

Bạn hoàn toàn chính xác rằng vector::iterator có thể được thực hiện bởi một con trỏ đơn giản (xem here) - trên thực tế khái niệm về trình lặp được dựa trên con trỏ tới phần tử mảng. Đối với các vùng chứa khác, chẳng hạn như map, list hoặc deque, tuy nhiên, con trỏ sẽ không hoạt động. Vậy tại sao điều này không được thực hiện? Dưới đây là ba lý do tại sao một lớp thực hiện là thích hợp hơn một con trỏ thô.

1. Thực hiện một iterator as type riêng biệt cho phép chức năng bổ sung (ngoài những gì được yêu cầu của tiêu chuẩn này), ví dụ (thêm vào trong chỉnh sửa sau Quentins bình luận) khả năng để thêm khẳng định khi dereferencing một iterator, ví dụ , trong chế độ gỡ lỗi.

2. độ phân giải quá tải Nếu iterator là một con trỏ T*, nó có thể được thông qua như là đối số hợp lệ để một chức năng chụp T*, trong khi điều này sẽ không thể xảy ra với một loại iterator. Do đó, làm cho con trỏ trên thực tế thay đổi hành vi của mã hiện tại. Xem xét, ví dụ,

   template<typename It> 
   void foo(It begin, It end); 
   void foo(const double*a, const double*b, size_t n=0); 
   
   std::vector<double> vec; 
   foo(vec.begin(), vec.end()); // which foo is called? 
   

3. tra cứu luận phụ thuộc vào (ADL; chỉ ra bởi juanchopanza) Nếu bạn thực hiện cuộc gọi không đủ tiêu chuẩn, ADL đảm bảo rằng chức năng trong namespace std sẽ được tìm kiếm chỉ nếu đối số là các loại định nghĩa trong namespace std. Vì vậy,

   std::vector<double> vec; 
   sort(vec.begin(), vec.end());    // calls std::sort 
   sort(vec.data(), vec.data()+vec.size()); // fails to compile 
   

   std::sort không tìm thấy nếu vector<>::iterator là một con trỏ đơn thuần.

Answer 4

Lý do cho việc sử dụng một con trỏ ít overhead, hiệu suất cao hơn, đặc biệt là nếu một trình biên dịch tối ưu hóa phát hiện lặp và làm việc của nó (hướng dẫn vector và các công cụ). Sử dụng trình vòng lặp có thể khó hơn cho trình biên dịch để tối ưu hóa.

Đây là sự hiểu lầm ở trung tâm của câu hỏi. Việc triển khai lớp cũng được tạo thành sẽ không có phí, và hiệu năng giống hệt nhau vì trình biên dịch có thể tối ưu hóa việc trừu tượng hóa và xử lý lớp lặp như chỉ là một con trỏ trong trường hợp std::vector.

Điều đó nói rằng,

MSVC++ 2013 hoặc libstdC++ trong MinGW 4.7, sử dụng một lớp đặc biệt dành cho vector lặp

vì họ xem đó thêm một lớp trừu tượng class iterator để xác định khái niệm lặp trên một std::vector là lợi hơn so với việc sử dụng một con trỏ thông thường cho mục đích này.

Tóm tắt có một bộ chi phí khác so với lợi ích, thường được thêm vào phức tạp thiết kế (không nhất thiết liên quan đến hiệu suất hoặc chi phí) để đổi lấy tính linh hoạt, kiểm chứng trong tương lai, ẩn chi tiết triển khai. Các trình biên dịch trên đã quyết định sự phức tạp thêm này là một chi phí thích hợp để trả cho những lợi ích của việc có một sự trừu tượng hóa.

Answer 5

Lý do cho việc sử dụng một con trỏ ít overhead, hiệu suất cao hơn, đặc biệt là nếu một trình biên dịch tối ưu hóa phát hiện lặp và làm việc của nó (hướng dẫn vector và các công cụ). Sử dụng trình vòng lặp có thể khó hơn cho trình biên dịch để tối ưu hóa.

Có thể, nhưng không phải vậy. Nếu thực hiện của bạn không phải là hoàn toàn shite, một cấu trúc gói một con trỏ sẽ đạt được cùng một tốc độ. Với ý nghĩ đó, thật đơn giản khi thấy các lợi ích đơn giản như các thông điệp chẩn đoán tốt hơn (đặt tên cho trình lặp thay vì T *), độ phân giải quá tải tốt hơn, ADL và kiểm tra gỡ lỗi làm cho cấu trúc trở thành người chiến thắng rõ ràng hơn con trỏ. Con trỏ thô không có lợi thế.

Answer 6

Tôi nhận được xung quanh trở ngại pesky này bởi dereferencing và ngay lập tức tham chiếu đến iterator một lần nữa. Có vẻ vô lý, nhưng nó thỏa mãn MSVC ...

class Thing { 
    . . . 
}; 

void handleThing(Thing* thing) { 
    // do stuff 
} 

vector<Thing> vec; 
// put some elements into vec now 

for (auto it = vec.begin(); it != vec.end(); ++it) 
    // handleThing(it); // this doesn't work, would have been elegant .. 
    handleThing(&*it); // this DOES work