What am I missing in my function?

**Elysia** · 01-14-2011

Honestly, your implementation is so much more complicated that it needs to be. I gave up after looking through it.
Here is a quick implementation I made that works:

Code:

bool containsStr(const string& sourceStr, const string& searchStr)
{
	if (searchStr.size() > sourceStr.size()) 
		return false; //since it is not possible for sourceStr to fully contain searchStr since it is shorter

	const auto src_end = sourceStr.end(), dst_end = searchStr.end();

	for (auto src_it = sourceStr.begin(), dst_it = searchStr.begin(); src_it < src_end; ++src_it)
	{
		if (*src_it == *dst_it)
		{
			++src_it;
			for (auto dst_it2 = dst_it + 1; dst_it2 < dst_end; ++dst_it2, ++src_it)
			{
				if (*dst_it2 != *src_it)
					break;
			}
			return true;
		}
	}
	return false;
}

Now compare that to yours.

**Programmer_P** · 01-14-2011

Originally Posted by Elysia

Honestly, your implementation is so much more complicated that it needs to be. I gave up after looking through it.
Here is a quick implementation I made that works:

Code:

bool containsStr(const string& sourceStr, const string& searchStr)
{
	if (searchStr.size() > sourceStr.size()) 
		return false; //since it is not possible for sourceStr to fully contain searchStr since it is shorter

	const auto src_end = sourceStr.end(), dst_end = searchStr.end();

	for (auto src_it = sourceStr.begin(), dst_it = searchStr.begin(); src_it < src_end; ++src_it)
	{
		if (*src_it == *dst_it)
		{
			++src_it;
			for (auto dst_it2 = dst_it + 1; dst_it2 < dst_end; ++dst_it2, ++src_it)
			{
				if (*dst_it2 != *src_it)
					break;
			}
			return true;
		}
	}
	return false;
}

That's funny...it didn't work. Hmm.
http://codepad.org/Z9mEynoc

Now compare that to yours.

I guess they have the same behavior...i.e. not working.

**tabstop** · 01-14-2011

Originally Posted by Programmer_P

That's funny...it didn't work. Hmm.
C++ code - 40 lines - codepad

I guess they have the same behavior...i.e. not working.

auto is a C++0x feature, so turn on C++0x in your compiler.

**Programmer_P** · 01-14-2011

Originally Posted by tabstop

auto is a C++0x feature, so turn on C++0x in your compiler.

How do I do that?
My compiler is GNU GCC Compiler. I looked in my IDE (Code::Blocks) compiler settings, but didn't see an option.

**tabstop** · 01-14-2011

Originally Posted by Programmer_P

How do I do that?
My compiler is GNU GCC Compiler. I looked in my IDE (Code::Blocks) compiler settings, but didn't see an option.

-std=c++0x

**Programmer_P** · 01-14-2011

Originally Posted by tabstop

-std=c++0x

I added that option to the "Other Options" tab's text field, then pressed Ok, and tried to compile it, but it still says "ISO C++ forbids declaration of 'src_end' with no type.

But, anyway, I can tell just by looking at the inner for loop, that breaking at the first non-match (after a match for searchStr.at(0) was found) without first providing a way to check to see if it broke is not going to work, and will immediately execute that return true statement which directly follows the loop, which means that even if the sourceStr didn't contain the searchStr, it will still return true, which means the function doesn't work.
Btw, I edited the link in that other post you quoted. The code there will do what I want it to do, I believe (if auto would only work)...

**whiteflags** · 01-14-2011

Originally Posted by tabstop

So:
1) Because you have, for bad reasons, tried to split your check-the-rest-of-the-substring up into two pieces, you check [0] against [0], [1] against [1], and then ... [2] against [1], rather than [2] against [2].
2) Since you are fiddling with i in your check-the-rest-of-the-substring part, you completely destroy the ability of your outer for loop to go through the string. Don't do that. Your check-the-rest-of-the-substring part only needs a single auxiliary variable, which will serve as the offset in both the source string and the search string. (Offset from [i] in the one case, and from [0] in the other.)

Tabstop, I have to say, that post makes no sense. What we are arguing is basically a working implementation of strstr() written in terms of strchr() and strncmp().

The call: i = haystack.find(needle[0], i) is made, which searches starting at 0, but may search next time at 5 or what have you, depending on the return value of the previous call to find(). The reason we update i by one is so that we start find() at the earliest possible position you could expect needle[0] to be again, upon the next iteration. If we take the very first use of find as an example: say find(needle[0], 0) returns 4, so on the next call to find it will be find(needle[0], 5). The condition of the loop itself is i != npos. So, what will happen instead of stepping through the entire string is that find() will search for needle[0] in smaller and smaller substrings of haystack. When it can't find needle[0] anywhere the result is a failed search. Stepping through haystack is really not part of the algorithm.

Further, I do not fiddle with i in your check-the-rest-of-the-substring part. By that time, i is the current result of find(), and a purposeful and correct comparison will be made to see if the wanted substring, needle, starts at haystack[i].

**tabstop** · 01-14-2011

Originally Posted by whiteflags

Tabstop, I have to say, that post makes no sense. What we are arguing is basically a working implementation of strstr() written in terms of strchr() and strncmp().

The call: i = haystack.find(needle[0], i) is made, which searches starting at 0, but may search next time at 5 or what have you, depending on the return value of the previous call to find(). The reason we update i by one is so that we start find() at the earliest possible position you could expect needle[0] to be again, upon the next iteration. If we take the very first use of find as an example: say find(needle[0], 0) returns 4, so on the next call to find it will be find(needle[0], 5). The condition of the loop itself is i != npos. So, what will happen instead of stepping through the entire string is that find() will search for needle[0] in smaller and smaller substrings of haystack. When it can't find needle[0] anywhere the result is a failed search. Stepping through haystack is really not part of the algorithm.

Further, I do not fiddle with i in your check-the-rest-of-the-substring part. By that time, i is the current result of find(), and a purposeful and correct comparison will be made to see if the wanted substring, needle, starts at haystack[i].

I think you think I'm referring to the code that you posted, rather than what the OP posted. That is not the case.

**whiteflags** · 01-14-2011

OK. I apologize then.

**tabstop** · 01-14-2011

Originally Posted by whiteflags

OK. I apologize then.

No problem. The threading here is ... odd.

**Elysia** · 01-15-2011

Originally Posted by Programmer_P

I guess they have the same behavior...i.e. not working.

Not quite. The code compiles fine and executes fine. The problem is at your end.

Originally Posted by Programmer_P

How do I do that?
My compiler is GNU GCC Compiler. I looked in my IDE (Code::Blocks) compiler settings, but didn't see an option.

Try upgrading to latest. You need at least GCC 4.3, I believe, to make it compile.
If all else fails, try replacing auto with std::string::const_iterator.
But you really would do yourself a favor to make C++0x code compile. You're missing out on a lot of goodies.

Thread: What am I missing in my function?

Thread Tools

Search Thread

Display

Similar Threads

Compiling Libraries in C

<Gulp>

Problem with Visual C++ Object-Oriented Programming Book.

ras.h errors

c++ linking problem for x11