C++ STL之查找函数总结_c++查找函数

STL中更有很多函数十分常用，其中查找是使用最高频的函数之一，以下针对C++11的查找进行总结。

1.查找（find）

1.1 std::find()

1.1.1 常用形式

//C++20前
template< class InputIt, class T >
InputIt find( InputIt first, InputIt last, const T& value );

//C++20前
template< class InputIt, class UnaryPredicate >
InputIt find_if( InputIt first, InputIt last, 
                 UnaryPredicate p );
                 
//C++11起，C++20前
template< class InputIt, class UnaryPredicate >
InputIt find_if_not( InputIt first, InputIt last, 
                     UnaryPredicate q );
1
2
3
4
5
6
7
8
9
10
11
12
13

针对顺序容器，STL并没有提供相应的find方法，所以需要使用std::find()，其时间复杂度可以认为是为 O(n) 。其实现可以认为是：

template<class InputIt, class T>
InputIt find(InputIt first, InputIt last, const T& value)
{
    for (; first != last; ++first) {
        if (*first == value) { //因为使用了==操作符比较，所以自定义类型需要重载==
            return first;
        }
    }
    return last;
}
1
2
3
4
5
6
7
8
9
10

1.1.2 使用示例

顺序容器vector,deque,list,forward_list和array本身都没有find方法，可以使用std::find来进行查找。

1.内置类型

//vector
vector<int> v1{1,2,3,4,5,6,7,8,9};
vector<int>::iterator v1It = std::find(v1.begin(),v1.end(), 5);

//deque
deque<int> d1{ 1,2,3,4,5,6,7,8,9 };
deque<int>::iterator d1It = std::find(d1.begin(), d1.end(), 3);

//list
list<int> l1{ 1,2,3,4,5,6,7,8,9 };
list<int>::iterator l1It = std::find(l1.begin(), l1.end(), 7);

//forward_list
forward_list<int> l2{ 1,2,3,4,5,6,7,8,9 };
forward_list<int>::iterator l2It = std::find(l2.begin(), l2.end(), 6);

//array
array<int, 10> a1{ 1,2,3,4,5,6,7,8,9,10 };
array<int, 10>::iterator a1It = std::find(a1.begin(), a1.end(), 10);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

2.自定义类型

struct Node {
	int a;
	int b;
	Node(int a, int b) {
		this->a = a;
		this->b = b;
	}

	//使用std::find()需要要重载==操作符
	bool operator== (const Node& right) const {
		if (a == right.a)
		{
			return b == right.b;
		}
		else {
			return a == right.a;
		}
	}
};

//vector
vector<Node> v2;
v2.push_back(Node(0, 1));
v2.push_back(Node(0, 2));
v2.push_back(Node(0, 3));
v2.push_back(Node(1, 1));
v2.push_back(Node(1, 2));
v2.push_back(Node(1, 3));

vector<Node>::iterator v2It = std::find(v2.begin(), v2.end(), Node(0,2));
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

1.2 set::find()

1.2.1 常用形式

iterator find( const Key& key );

const_iterator find( const Key& key ) const;
1
2
3

其时间复杂度可认为是 O(log(n)),即拥有对数复杂度。
查找的逻辑实际上如下：

1. 首先找到set中不大于（<=）给定key的第一个元素 _where ；
2. _where与给定的key等价（这里的等价含义详见严格弱序）则返回 _where,否则返回 end();

实际上STL的关联容器set，map，multiset和multimap中的元素都应该满足严格弱序（stick weak ordering）,详见 C++严格弱序。

1.2.2 使用示例

1. 内置类型

set<int> s1{ 1,2,3,4,5,6,7,8,9 };
set<int>::iterator s1It = s1.find(5); //找到5

set<double> s2{ 1.1, 2.54, 3.6, 4.421, 5.87, 6.213, 7.321, 8.0, 9.5 };
set<double>::iterator s2It = s2.find(2.5); //找不到2.5
1
2
3
4
5

2. 自定义类型

struct Node {
	int a;
	int b;
	Node(int a, int b) {
		this->a = a;
		this->b = b;
	}

	//使用set::find()需要要重载<操作符,使之满足严格弱序
	bool operator< (const Node& right) const {
		if (a == right.a)
		{
			return b < right.b;
		}
		else {
			return a < right.a;
		}
	}
};

set<Node> s3;
s3.insert(Node(0, 1));
s3.insert(Node(0, 2));
s3.insert(Node(0, 3));
s3.insert(Node(1, 1));
s3.insert(Node(1, 2));
s3.insert(Node(1, 3));

set<Node>::iterator s3It = s3.find(Node(1, 1)); 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

1.3 map::find()

1.3.1 常用形式

iterator find( const Key& key );

const_iterator find( const Key& key ) const;
1
2
3

因为map和set的底层实际上都是红黑树，所以底层的实现一致，其时间复杂度也可认为是 O(log(n)),即拥有对数复杂度。
查找的逻辑也与set一致。

1.3.2 使用示例

1. 内置类型

map<int, int> m1{ {0,0}, {1,0}, {2,0}, {3,0} };
map<int, int>::iterator m1It = m1.find(1);

map<char, int> m2{ { 'a',1 },{ 'b',2 },{ 'c',3 },{ 'd',4 } };
map<char, int>::iterator m2It = m2.find('d');
1
2
3
4
5

2. 自定义类型

struct Node {
	int a;
	int b;
	Node(int a, int b) {
		this->a = a;
		this->b = b;
	}

	//使用map::find()需要要重载<操作符,使之满足严格弱序
	bool operator< (const Node& right) const {
		if (a == right.a)
		{
			return b < right.b;
		}
		else {
			return a < right.a;
		}
	}
};

map<Node, int> m3;
m3.insert(make_pair(Node(0, 1), 1));
m3.insert(make_pair(Node(0, 2), 1));
m3.insert(make_pair(Node(0, 3), 1));
m3.insert(make_pair(Node(1, 1), 1));
m3.insert(make_pair(Node(1, 2), 1));
m3.insert(make_pair(Node(1, 3), 1));

map<Node, int>::iterator m3It = m3.find(Node(1, 2));
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

1.4 multiset::find()

1.4.1 常用形式

//查找给定键的元素，若容器中有数个拥有 key 的元素，则可能返回任意一者。
iterator find( const Key& key );
const_iterator find( const Key& key ) const;

/*返回容器中所有拥有给定关键的元素范围。
范围以二个迭代器定义，一个指向首个不小于（>=）key 的元素，另一个指向首个大于（>）key 的元素。
首个迭代器可以换用 lower_bound() 获得，而第二迭代器可换用 upper_bound() 获得。*/
std::pair<iterator,iterator> equal_range( const Key& key );
std::pair<const_iterator,const_iterator> equal_range( const Key& key ) const;

//返回指向首个不小于（>=）给定键的元素的迭代器 
iterator lower_bound( const Key& key );
const_iterator lower_bound( const Key& key ) const;

//返回指向首个大于（>）给定键的元素的迭代器 
iterator upper_bound( const Key& key );
const_iterator upper_bound( const Key& key ) const;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

其时间复杂度可认为是 O(log(n)),即拥有对数复杂度。

1.4.2 使用示例

1. 内置类型

multiset<int> ms1{ 1,1,1,2,3,4,5,5,5,6,7,8,9 };
using It = multiset<int>::iterator;
using PairIt = pair<It, It>;
It ms1It = ms1.find(1);
It ms1It1 = ms1.lower_bound(1);
It ms1It2 = ms1.upper_bound(1);
PairIt pairIt = ms1.equal_range(1);
for (It it = pairIt.first; it != pairIt.second; it++)
{
	cout << *it << endl;
}

1
2
3
4
5
6
7
8
9
10
11
12

2. 自定义类型

struct Node {
	int a;
	int b;
	Node(int a, int b) {
		this->a = a;
		this->b = b;
	}

	//使用multiset::find()需要要重载<操作符,使之满足严格弱序
	bool operator< (const Node& right) const {
		if (a == right.a)
		{
			return b < right.b;
		}
		else {
			return a < right.a;
		}
	}
};

multiset<Node> ms2;
ms2.insert(Node(0, 1));
ms2.insert(Node(0, 1));
ms2.insert(Node(0, 2));
ms2.insert(Node(1, 1));
ms2.insert(Node(1, 1));
ms2.insert(Node(1, 1));
using It = multiset<Node>::iterator;
using PairIt = pair<It, It>;
It ms2It = ms2.find(Node(1, 1));
It ms2It1 = ms2.lower_bound(Node(1, 1));
It ms2It2 = ms2.upper_bound(Node(1, 1));
PairIt pairIt = ms2.equal_range(Node(1, 1));
for (It it = pairIt.first; it != pairIt.second; it++)
{
	Node node = *it;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

1.5 multimap::find()

1.5.1 常用形式

//寻找拥有等于 key 的键的元素。若容器中有数个拥有 key 的元素，则可能返回任意一者。
iterator find( const Key& key );
const_iterator find( const Key& key ) const;

/*返回容器中所有拥有给定关键的元素范围。
范围以二个迭代器定义，一个指向首个不小于（>=） key 的元素，另一个指向首个大于（>）key 的元素。
首个迭代器可以换用 lower_bound() 获得，而第二迭代器可换用 upper_bound() 获得。*/
std::pair<iterator,iterator> equal_range( const Key& key );
std::pair<const_iterator,const_iterator> equal_range( const Key& key ) const;

//返回指向首个不小于（>=）给定key的元素的迭代器 
iterator lower_bound( const Key& key );
const_iterator lower_bound( const Key& key ) const;

//返回指向首个大于（>）给定key的元素的迭代器 
iterator upper_bound( const Key& key );
const_iterator upper_bound( const Key& key ) const;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

其时间复杂度可认为是 O(log(n)),即拥有对数复杂度。

1.5.2 使用示例

1. 内置类型

multimap<int, int> mm1{ { 0,0 },{ 1,0 },{ 1,0 },{ 1,0 } };
using It = multimap<int, int>::iterator;
using PairIt = pair<It, It>;
It mm1It = mm1.find(1);
It mm1It1 = mm1.lower_bound(1);
It mm1It2 = mm1.upper_bound(1);
PairIt pairIt = mm1.equal_range(1);
for (It it = pairIt.first; it != pairIt.second; it++)
{
	cout << it->second << endl;
}
1
2
3
4
5
6
7
8
9
10
11

2. 自定义类型

struct Node {
	int a;
	int b;
	Node(int a, int b) {
		this->a = a;
		this->b = b;
	}

	//使用multimap::find()需要要重载<操作符,使之满足严格弱序
	bool operator< (const Node& right) const {
		if (a == right.a)
		{
			return b < right.b;
		}
		else {
			return a < right.a;
		}
	}
};

multimap<Node, int> mm2;
mm2.insert(make_pair(Node(0, 1), 0));
mm2.insert(make_pair(Node(0, 1), 0));
mm2.insert(make_pair(Node(0, 2), 0));
mm2.insert(make_pair(Node(1, 1), 0));
mm2.insert(make_pair(Node(1, 1), 0));
mm2.insert(make_pair(Node(1, 1), 0));
using It = multimap<Node, int>::iterator;
using PairIt = pair<It, It>;
It mm1It = mm2.find(Node(1, 1));
It mm1It1 = mm2.lower_bound(Node(1, 1));
It mm1It2 = mm2.upper_bound(Node(1, 1));
PairIt pairIt = mm2.equal_range(Node(1, 1));
for (It it = pairIt.first; it != pairIt.second; it++)
{
	cout << it->second << endl;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38