Thread: string

Sorry you're not quite going to trick me into answering your homework for you.
I had one of those "this is too easy" moments before I realised that the only reason you would want to know this is for an answer to homework.

Anyway, if you really want to know, the algorithm is implementation defined and its time complexity is O(n^3), where ^ denotes exponentiation.

1. Open up your string header.
2. Find "operator==".
3. Look at what it's doing.
4. Determine the complexity.
5. Collect underpants
6. ...
7. Profit

You may have to do some detective work but, for example, the MS Visual Studio 2005 <string> header includes the following for operator==

Code:

template<class _Elem,
	class _Traits,
	class _Alloc> inline
	bool __CLRCALL_OR_CDECL operator==(
		const basic_string<_Elem, _Traits, _Alloc>& _Left,
		const basic_string<_Elem, _Traits, _Alloc>& _Right)
	{	// test for string equality
	return (_Left.compare(_Right) == 0);
	}

This calls the "compare" function for basic_string objects (defined in the xstring header). The <xstring> header contains the following relevant sections:

Code:

	int __CLR_OR_THIS_CALL compare(const _Myt& _Right) const
		{	// compare [0, _Mysize) with _Right
		return (compare(0, _Mysize, _Right._Myptr(), _Right.size()));
		}

...

	int __CLR_OR_THIS_CALL compare(size_type _Off,
		size_type _N0, const _Elem *_Ptr, size_type _Count) const
		{	// compare [_Off, _Off + _N0) with [_Ptr, _Ptr + _Count)
		_DEBUG_POINTER(_Ptr);
		if (_Mysize < _Off)
			_String_base::_Xran();	// _Off off end
		if (_Mysize - _Off < _N0)
			_N0 = _Mysize - _Off;	// trim _N0 to size

		size_type _Ans = _Traits::compare(_Myptr() + _Off, _Ptr,
			_N0 < _Count ? _N0 : _Count);
		return (_Ans != 0 ? (int)_Ans : _N0 < _Count ? -1
			: _N0 == _Count ? 0 : +1);
		}

For that last one, you have to do a bit more digging but it basically does something similar to strncmp... and again this is the MS Visual Studio 2005 version of things, your mileage may vary.