U++ forum: Welcome to the forum

Re: Why doesn't Vector have Find? [message #45570 is a reply to message #45569]

Sat, 05 December 2015 11:28

mirek
Messages: 13984
Registered: November 2005

Ultimate Member

Mindtraveller wrote on Fri, 04 December 2015 19:43

There is a common Find() template to achieve what you want. It is applied to a number of containers, not only Vector.
But I doubt if slow sequential search is a good idea at all. If you want Vector and you want to have quick search, make it sorted. Add items by using FindUpperBound()-like calls, then you may search with FindBinary() which costs O(log(n)), not O(n) as for sequential search.

Actually, I think this might not be that bad idea, in fact I was thinking about it too.

Thing is that sometimes you know that you only have a limited number of elements to find, but you want to conserve memory. Index consumes quite a lot of auxiliary memory for hashing. In that case, I often use simple Vector with FindIndex. Anyway, sometimes later it is needed to convert (or copy/paste) code to Index. Having Find as method would save some typing.

BTW, if you are about to insert items by FindUpperBound, you might consider using Sorted* kind of container Smile

Mirek

[Updated on: Sat, 05 December 2015 11:46]

Report message to a moderator