• Advertisement
Sign in to follow this  

std::string search

This topic is 3475 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi I have made a search function which compares two strings from list searching if two strings are equal. Function is working perfectly, but I'm concerned about speed in case when I will have thousands of string data.
struct custom
{
     int id;
     std::string stringData;
};
std::list<custom> m_stringList;
custom* search(std::string strExt)
	{
		for(std::list<custom>::iterator it=m_stringList.begin();it!=m_stringList.end();it++)
		{
			if((*it).stringData== strExt)
				return &(*it);
		}
		return 0;
	}

As you see I have one list container of 'custom' data, and I'm searching by string value to get id value. Can this string search be made faster? thanks in advance

Share this post


Link to post
Share on other sites
Advertisement
It looks like what you are trying to do is look up a Custom by string, you should be using a std::map for this. Here is a link to Wikipedia that explains how it works and gives an example of how to use it.

Hope that helps,

Share this post


Link to post
Share on other sites
Great!

almost the same thing I wanted to use. But again I would like to ask how fast is this? I need fastest algorithm possible, because I'm performing lot of searches in real-time application, and I don't really want user to wait because application needs to iterate through thousands and thousand of entries.

Share this post


Link to post
Share on other sites
The look up time for a std::map is definitely going to be fast enough for your needs and in fact most peoples needs.

Share this post


Link to post
Share on other sites
If in doubt, profile it and see. It should be trivial to come up with some speed tests. But as Dave said, it'll be plenty fast.

Share this post


Link to post
Share on other sites
Quote:
Original post by Dave
The look up time for a std::map is definitely going to be fast enough for your needs and in fact most peoples needs.


std::map has O(log n) lookup time. In your case, I'd use unordered_map/hash_map with average O(1) lookup time.

Share this post


Link to post
Share on other sites
hash_map is the natural choice here, but in some cases you can do better. If the set of strings that are used as keys doesn't change very often and the strings are short, the fastest structure I know is a trie.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement