yohhoyの日記

技術的メモをしていきたい日記

forward_listはsizeメンバ関数を持たない

C++

C++11標準ライブラリで新しく追加されたstd::forward_listシーケンスコンテナは、要素数を返すsizeメンバ関数を提供しない。（空判定のemptyメンバ関数は提供される。）

#include <forward_list>
std::forward_list<int> fl = /*...*/;

size_t n = fl.size();  // NG: ill-formed

// OK: 計算量O(n)で要素数を計算
#include <iterator>
size_t n = std::distance(fl.begin(), fl.end());

C++11(N3337) 23.3.4.1/p2より該当箇所を引用。

A forward_list satisfies all of the requirements of a container (Table 96), except that the size() member function is not provided. (snip)

forward_list導入の提案文書N2543では、“O(N) のsize実装” や “O(1) のsize実装” と比較したうえで、“sizeを提供しない” 設計を選択している。唯一sizeの計算量が線形時間 O(n) であったstd::listコンテナも、C++11標準ライブラリでは定数時間 O(1) 保証に変更されたことで、全ての標準コンテナでsize計算量が定数時間 O(1) となったことが背景にある。

関連URL