Constructing an argument for two functions for their being equivalent

The question is belonging to the two functions find_1 and find_2, and says:
Are you sure those two definitions are logically equivalent? How would you be sure? Try constructing an argument for their being equivalent. That done, try both on some data.

What does "constructing an argument for their being equivalent" mean? Is that argument the std::vector in the code? I wrote the following simple project but not sure how to be sure if they're logically equivalent, as written in the question!

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
39
40
#include <iostream>
#include <vector>

template<typename In, typename T>
// requires Input_iterator<In>()
// && Equality_comparable<Value_type<T>>()

In find_1(In first, In last, const T& val)
// find the first element in [first,last) that equals val
{
	while (first != last && *first != val) ++first;
	return first;
}

template<typename In, typename T>
// requires Input_iterator<In>()
// && Equality_comparable<Value_type<T>>()

In find_2(In first, In last, const T& val)
// find the first element in [first,last) that equals val
{
	for (In p = first; p != last; ++p)
		if (*p == val) return p;
	return last;
}

int main() {

	std::vector<std::string> vs{ {"one"}, {"two"}, {"three"}, {"four"}, {"five"} };
	if (find_1(vs.begin(), vs.end(), "three") != vs.end())
		std::cout << "(find_1) Found!\n";
	else std::cout << "(find_1) Not found\n";

	if (find_2(vs.begin(), vs.end(), "three") != vs.end())
		std::cout << "(find_2) Found!\n";
	else std::cout << "(find_2) Not found\n";

	system("pause");
	return 0;
}
Last edited on
What does "constructing an argument for their being equivalent" mean?


It means "convince me in human words, as if we were having a conversation, that two functions are 'equivalent' - tell me in words what it means for two functions to be 'equivlent'".
Aha, I thought it was parameter-argument!

Anyhow, in human words I'd say they are not equal but not that distinguished too.
find_1 works with iterators well enough whilst find_2 creates a local iter p, which is a wrapped pointer. Probably, there will be a tiny memory leak but it's not big deal. Agree? Of course we haven't used new there, so not sure.
Last edited on
Any memory leak is potentially a big issue if it happens repeatedly, and you have software that is meant to run for days on end. But I don't see why you think a memory leak is happening here. An iterator is just a local stack variable, and it will be popped off the stack correctly like any other variable.

What I interpret 'equivalent' as is that both functions produce the same output, given the same input, for all possible input. As a further restriction, one might add that both functions need to have the same runtime/space complexity. (Both of the algorithms are simply linear runtime and only use a constant amount of iterators, so that is not an issue here, unless the == operator is significantly different from the != operator on the input data.)
Last edited on
Topic archived. No new replies allowed.