迭代器尾後元素的設計是出於什麼意圖?

標準庫不用容器的最後一個元素而用最後元素之後的「尾後」元素。

  1. 這樣的設計是出於什麼意圖?
  2. 這麼做在性能上有哪些優點?


左閉右開區間是一個約定,都這麼用代碼會很清晰明了


左閉右開區間是個好東西,結尾的元素或迭代器直接當成哨兵。表示遍歷結束。

區間描述的自然,用迭代器遍歷區間演算法也能寫的簡練。

另外考慮一下相鄰區間的連接

[1,2) + [2,4) = [1,4)

很自然

[1,2] + [2,4] = 啥?

[1,2] + [3 ,4] = 啥?

參考:編程原本 (豆瓣)


1、容器沒有元素怎麼辦?

2、沒有優點。


可以把更多的corner case變成common case,以一個很簡單的標準庫演算法為例:

template &
ForwardIterator find(ForwardIterator first, ForwardIterator last, Value const value);

如果last是指向尾元素而非尾後元素,實現就是這樣的:

if (first != ++last) { // 排除區間為空的情況
while (!(*first == value) ++first != last) { }
}
return first;

為了排除空區間的情況,最簡潔的方法還是一上來就讓last指向尾後。不光麻煩在這裡,調用find的時候如何確定到底找到沒有又成了一件很麻煩的事情:

auto result = find(container.begin(), container.end(), value);
if (result != next(container.end())) {
// do something
}

如果一開始就規定區間是半閉半開,上述代碼都可以變得更簡潔。find的實現:

while (first != last !(*first++ == value)) { }
return first;

調用:

auto result = find(container.begin(), container.end(), value);
if (result != container.end()) {
// do something
}


如果不是用尾後元素,而是用最後一個元素的話。那當begin()==end()的時候就無法判斷是沒有元素還是只有一個元素了


當然得有尾後元素,因為一個大小為n的容器,尾元素其實是第n-1個元素,尾後元素才是第n個元素。如果沒有尾後元素,循環條件就沒法寫了。不信你試試用尾元素寫一個遍歷容器的循環式試試。

所謂容器沒有尾後元素無法表達空容器的問題其實是上述問題的真子集, 因為真正面臨的問題是在大小為0的容器中尾元素是第-1個元素,因此無法表達。這也就指出了如果就是不能表達尾後元素,應該怎麼解決這一問題:認為元素編號從1開始,把首前元素認為是0,每次遍歷從後向前循環。


尾後元素無法避免,即便你不用顯示的元素表示,你也必須通過另一種方式表明尾元素是尾元素,這種方式,不論是什麼,都等價於尾後元素。


推薦閱讀:

關於C++中的override?
C++中有哪些設計精良的部分(精華),還有哪些是不值得花費很多時間探究的知識點?
C++類對象內存大小的計算?

TAG:面向對象編程 | C |