Thread: Efficiently scanning through a vector.

Hello all, again.

I have the following code that searches a vector for a particular item. If it exists already in the vector, it doesn't add the current entry. Otherwise, it adds it:

Code:

if(mMapLinks.size() == 0)
	mMapLinks.push_back(new mapLink(mFilesystem, target, type, x, y, width, height, dstx, dsty));
else
{
	vector<mapLink*>::iterator i = mMapLinks.begin();
	bool exists = false;
	for(; i != mMapLinks.end(); i++)
	{
		if((*i)->getTargetMap() == target)
		{
			exists = true;
			break;
		}
	}

	if(!exists)
		mMapLinks.push_back(new mapLink(mFilesystem, target, type, x, y, width, height, dstx, dsty));
}

where mMapLinks is defined as 'vector<mapLink*> mMapLinks' and target is defined as 'string'.

This code does the job but feels clunky and potentially inefficient. I'd like to stick with a vector as I need very fast linear iteration although I'm not opposed to other suggestions.

Container usage invariably involves trade-off of requirements: for example, efficient scanning for duplicates often requires a different type of container (eg a set, a list, a map) than one (eg vector) which supports linear times to access random elements.

That is why multiple types of containers exist - there is no single container type that supports all operations in an optimal manner.

Bottom line: you need to decide which performance characteristics are most important to you, and accept the trade-off that other operations may be less efficient.

<sigh>

Oh well. Map is not at all what I'm looking for but thanks anyway for all the suggestions.

I realized all of a sudden that I don't need unique entries.

Originally Posted by leeor_net

Okay, I thought I was pretty clear but here goes again.

The above code. Can I write it in a better, cleaner, smaller way? If so, what would it look like?

Since you claim this thread is vector-only, then I would say "why not use std::find"? Granted it may well have the same speed.

And if what you claim is true (that you only want one entry with a given string) than that's what map is: a container where you can only have one entry with a given key, easily searchable, and still iterable. Unless there's a meaning to the index numbers that you're not telling us.

EDITEDITEDIT: Sorry, I meant find_if, not find.

Oh, that. Yeah, my internet connection hiccuped. I didn't know that even went through so now I understand why everyone is asking about a duplicate question. I thought you were referring to a question I had posted a few days ago about what would be the most appropriate container for the particular problem I was looking at. I apologize for the misunderstanding and I really do appreciate the help and advice that everybody here is so willing to offer.

The duplicate thread has been deleted.

Originally Posted by leeor_net

I realized all of a sudden that I don't need unique entries.

But if you still need more efficient search than linear search, consider using a std::multimap or std::multiset. If you have a TR1 implementation available, you could also consider unordered_multiset and unordered_multimap.

You could say that my use of the word 'efficient' is incorrect -- I'm less worried about the speed of a linear iteration versus the number of lines of code. I've never been very good at articulating exactly what I means so I find myself in these kinds of misunderstandings sometimes... -_-

Using the above code as an example, if I pulled out the unnecessary test for an empty vector, it would look like this:

Code:

vector<mapLink*>::iterator i = mMapLinks.begin();
bool exists = false;
while(i != mMapLinks.end())
{
	if((*i)->getTargetMap() == target)
	{
		exists = true;
		break;
	}

	i++;
}

if(!exists)
	mMapLinks.push_back(new mapLink(mFilesystem, target, type, x, y, width, height, dstx, dsty));

This still looks clunky to me. Is there a way I can further reduce lines or rewrite this section of code in a better way or am I just grappling at a pipe-dream now? (at this point it's purely for reference purposes for future uses where I might not want the overhead of a map).

Originally Posted by leeor_net

This still looks clunky to me. Is there a way I can further reduce lines or rewrite this section of code in a better way

As tabstop suggested, you could use std::find_if.