Thread: string

  1. #1
    Registered User
    Join Date
    Jan 2010


    string s1,s2;
    cin >> s1 >> s2;
    cout << "yes" << endl;
    cout << "no" << endl;

    can someone tell me which algorithm is used in comparison of strings s1==s2 and what is its complexity?

  2. #2
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    New Zealand
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  3. #3
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Anyway, if you really want to know, the algorithm is implementation defined and its time complexity is O(n^3), where ^ denotes exponentiation.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  4. #4
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Northern Virginia/Washington DC Metropolitan Area
    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==
    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 ( == 0);
    This calls the "compare" function for basic_string objects (defined in the xstring header). The <xstring> header contains the following relevant sections:
    	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)
    		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.
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. OOP Question DB Access Wrapper Classes
    By digioz in forum C# Programming
    Replies: 2
    Last Post: 09-07-2008, 04:30 PM
  2. Message class ** Need help befor 12am tonight**
    By TransformedBG in forum C++ Programming
    Replies: 1
    Last Post: 11-29-2006, 11:03 PM
  3. Something is wrong with this menu...
    By DarkViper in forum Windows Programming
    Replies: 2
    Last Post: 12-14-2002, 11:06 PM
  4. Classes inheretance problem...
    By NANO in forum C++ Programming
    Replies: 12
    Last Post: 12-09-2002, 03:23 PM
  5. Warnings, warnings, warnings?
    By spentdome in forum C Programming
    Replies: 25
    Last Post: 05-27-2002, 06:49 PM