iterator find(const key_type& x); // (1) C++11
const_iterator find(const key_type& x) const; // (2) C++11
template <class K> iterator find(const K& k); // (3) C++20
template <class K> const_iterator find(const K& k) const; // (4) C++20
概要
コンテナ内で指定されたキーに合致する要素を検索し、見つかった場合はそれへのイテレータを返し、見つからなかった場合は end
(コンテナの最後の要素の次)を指すイテレータを返す。
指定されたキーに合致する要素の範囲を取得するには equal_range
を用いる。
また、指定されたキーに合致する要素が存在するかを調べる場合は count
を用いる。
- (1) : 非
const
な*this
オブジェクトに対する検索 - (2) :
const
な*this
オブジェクトに対する検索 - (3) : 非
const
な*this
オブジェクトに対する透過的な検索 - (4) :
const
な*this
オブジェクトに対する透過的な検索
(3)、(4)の透過的な検索は、Pred::is_transparent
およびHash::is_transparent
が定義される場合に有効になる機能であり、例としてunordered_multiset<string> s;
に対してs.find("key");
のようにstring
型のキーを持つ連想コンテナの検索インタフェースに文字列リテラルを渡した際、string
の一時オブジェクトが作られないようにできる。詳細はstd::hash
クラスのページを参照。
テンプレートパラメータ制約
- (3), (4) :
Pred::is_transparent
型およびHash::is_transparent
型が定義されていること
戻り値
指定されたキーと等価なキーの要素を指すイテレータを返す。そのような要素がない場合には、end()
を返す。
計算量
- 平均: 定数時間
- 最悪:
size
について線形時間
備考
- コンテナが
const
の場合にはconst_iterator
、そうでない場合にはiterator
が返るが、unordered_multiset
の場合には、いずれにせよ読み取り専用イテレータである。 - 指定されたキーと等価なキーの要素が複数あった場合に、どの要素を指すイテレータが返されるかは標準では明確にされていない。ハッシュ関数を使用してバケットに格納するという
unordered_multiset
の要件を考えると、よほどひねくれた実装にしない限りイテレータの走査順で先頭の要素を指すイテレータが返されるものと思われるが、equal_range()
を使えば確実に先頭の要素を指すイテレータを取得することができる。
例
#include <iostream>
#include <unordered_set>
#include <algorithm>
#include <iterator>
int main()
{
std::unordered_multiset<int> ums{ 1, 3, 5, 7, 9, 1, 3, 5, 7, 9, };
std::copy(ums.begin(), ums.end(), std::ostream_iterator<int>(std::cout, ", "));
std::cout << std::endl;
auto it1 = ums.find(5);
if (it1 == ums.end()) {
std::cout << "not found" << std::endl;
} else {
std::cout << "found " << *it1 << " at " << std::distance(ums.begin(), it1) << std::endl;
}
auto it2 = ums.find(8);
if (it2 == ums.end()) {
std::cout << "not found" << std::endl;
} else {
std::cout << "found " << *it2 << " at " << std::distance(ums.begin(), it2) << std::endl;
}
}
27
#include <iostream>
#include <unordered_set>
#include <algorithm>
#include <iterator>
int main()
{
std::unordered_multiset<int> ums{ 1, 3, 5, 7, 9, 1, 3, 5, 7, 9, };
std::copy(ums.begin(), ums.end(), std::ostream_iterator<int>(std::cout, ", "));
std::cout << std::endl;
auto it1 = ums.find(5);
if (it1 == ums.end()) {
std::cout << "not found" << std::endl;
} else {
std::cout << "found " << *it1 << " at " << std::distance(ums.begin(), it1) << std::endl;
}
出力
9, 9, 7, 7, 5, 5, 1, 1, 3, 3,
found 5 at 4
not found
バージョン
言語
- C++11
処理系
- Clang: 3.1 ✅
- GCC: 4.7.0 ✅
- ICC: ?
- Visual C++: ?
関連項目
名前 | 説明 |
---|---|
count |
指定したキーの要素数を取得 |
equal_range |
指定したキーの範囲を取得 |