Re: 請問一個關於iterator的問題...

看板C_and_CPP (C/C++)作者khoguan (Khoguan Phuann)時間19年前 (2005/08/08 15:08)推噓3(3推 0噓 1→)

留言4則, 3人參與討論串2/3 (看更多)

※ 引述《UNARYvvv (有趣生活)》之銘言： : 推 slchen:謝謝啦~~~... 220.141.56.156 07/29 : 推 UNARYvvv:哈..話說我先前也看不出來為何會錯..原來是同名 61.70.137.117 07/29 : → UNARYvvv:不過若是這種情況，不是應該先以引數型別完全相 61.70.137.117 07/29 : → UNARYvvv:同的 non-template function match 到嗎?? 61.70.137.117 07/29 : → UNARYvvv:因為照說他們是在同一個 overloaded set 裡面吧 61.70.137.117 07/29 : → UNARYvvv:不知道為何反而編譯器會選擇 Standard 版的呢?? 61.70.137.117 07/29 : 推 otpgoodop:namespace不同.... 59.115.76.234 08/06 : (沒想到過了好幾天居然又有新推文~) : 的確 namespace 不同沒錯 : 但不知道這對我的疑問..有解釋到什麼呢?? : 請教一下~謝了 U大還記得這個問題，好學精神，令人感佩。我先重述並稍微簡化一下原po的問題： #include <vector> #include <iostream> int distance(std::vector<int> v1, std::vector<int> v2) { return v1.size() - v2.size(); } int main() { std::vector<int> v1(3), v2(1); // 再宣告一次，希望讓編譯器選用，結果沒有 :( int distance(std::vector<int> v1, std::vector<int> v2); int d1 = distance(v1, v2); std::cout << "d1=" << d1 << '\n'; return 0; } 編譯錯誤訊息： /usr/lib/gcc/i686-pc-cygwin/3.4.4/include/c++/bits/ stl_iterator_base_types.h: In instantiation of `std::iterator_traits<std::vector<int, std::allocator<int> > >': test.cpp:12: instantiated from here /usr/lib/gcc/i686-pc-cygwin/3.4.4/include/c++/bits/ stl_iterator_base_types.h:129: error: no type named `iterator_category' in `class std::vector<int, std::allocator<int> >' 問題：為什麼它不直接採用我們自定的 global non-template distance() 就好，卻和 std::distance() 夾纏不清呢？我在 comp.lang.c++.moderated 上提了這個問題，結果引來近五十篇討論。這個問題頗為複雜，所以我遲遲未來向大家報告討論的一些結果，現在既然 U大問起，我試著整理、說明看看。真正的問題點並不發生在這個決定要選哪一個函式(也就是 overload resolution)的時間點上，而是在更早之前。也就是編譯過程根本就還沒進行到 overload resolution的階段就出錯了。首先編譯器遇到這個 distance() 函式名稱時，就會開始去一些地方找它的宣告，哪些地方呢？包括 locally visible 的函式宣告，例如在 local block 裡宣告的，或是在local block 的任何一個外層宣告而沒有被裡層蓋掉(hide)的，例如global namespace scope 宣告的函式名字。另外，因為我們呼叫這個 distance() 時，並沒有給它一個 qualifier, 如 ::distance() 或是 std::distance()，這種 unqualified name編譯器還會去一個重要的地方尋找它的宣告，也就是「宣告參數的型別」所在的 namespace 的地方，這就是所謂的 ADL(Argument Dependent Lookup)又稱 Koenig lookup, 這是由 Andrew Koenig 所提出的做法。最初是為了解決 overloaded operator 能夠被方便的呼叫使用。這個我就不再多解釋了。所以除了原po定義的那個 global scope distance() 以外，編譯器還會去找到 std namespace 中的 distance(), 因為原po在呼叫 distance 時，所給的參數是 vector<int> 而 vector 又是宣告於 std namespace 中，所以被直接或間接 include 進來的 std namespace中所有的函式名稱，只要叫做 distance() 都會被找到。因為找到的 distance() 是個 function template, 所以要先做 template argument deduction 推導成功後，才會將產生的 template instantiation 加到 candidate functions set中，準備進一步做 overload resolution. 現在先將 std::distance() 的宣告式完整的寫出來，方便說明。 template<class InputIterator> typename iterator_traits<InputIterator>::difference_type distance(InputIterator first, InputIterator last); 其中的第二行 typename ...... 一整行就是 return type 在做引數推導(template argument deduction)的過程中，first 和 last 這兩個參數的 InputIterator 被用 vector<int> 來取代完後， return type 接著也要被取代，才能產生一個「正常的」宣告式，以便在隨後加入 candidate functions set中，於是就變成 iterator_traits<vector<int> >::difference_type 編譯器需要確定這個東西到底是不是有效的 type, 如果最終的結果是無效的 type 那麼 template argument deduction 就失敗，這個函式就不會加入 candidate functions set中，這種「失敗」並不會產生編譯錯誤。問題是為了確定它有沒有效，編譯器必須先做一個動作，就是用 vector<int> 來 instantiate iterator_traits<> 這個 class template, 然後再看產生的 class 中有沒有宣告 differenct_type 這個型別。這是 iterator_traits<> 的定義： template<typename _Iterator> struct iterator_traits { typedef typename _Iterator::iterator_category iterator_category; typedef typename _Iterator::value_type value_type; typedef typename _Iterator::difference_type difference_type; typedef typename _Iterator::pointer pointer; typedef typename _Iterator::reference reference; }; 當它用 vector<int> 代入時，就在定義中的第一行發現錯誤： typedef typename vector<int>::iterator_category iterator_category; vector<int>中並沒有宣告 iterator_category，所以編譯器就發出編譯錯誤的訊息。不 instantiate 則已，一做 instantiate, 這種過程中的錯誤，編譯器都會發出「抱怨」，不讓你過。很有趣的，如果我們偷偷的在 vector<> 中加入一個 iterator_category 的 typedef template</*...*/> vector { public: typedef int iterator_category; // ... }; 讓 iterator_traits 的具現化可以順利完成，而且在緊接著的 distance() 的 return type 的取代動作中，也確實有 difference_type可用 (vector<> 中有 difference_type)，於是 std::distance() 會加入 overload functions set，但最後仍然還是原po定義的那個 distance() 會被採用。甚至於，如果我們除了上述那一個動作以外，還多做了一個動作，就是偷偷的將上面 iterator_traits 定義中的第三行拿掉： //typedef typename _Iterator::difference_type difference_type; 讓 iterator_traits 的具現化可以順利完成，但是在緊接著的 distance() 的 return type 的取代動作中，找不到 difference_type可用，導致 argument type deduction失敗，這種失敗，上面說了，不會造成編譯錯誤。這是所謂的 SFINAE (Substitution Failure Is Not An Error). 以上的說明，但願能提供不一樣的思考方向。 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ※ 編輯: khoguan 來自: 61.227.252.148 (08/08 15:20)