Efficiently scanning through a vector.

This is a discussion on Efficiently scanning through a vector. within the C++ Programming forums, part of the General Programming Boards category; Hello all, again. I have the following code that searches a vector for a particular item. If it exists already ...

  1. #1
    Professional Chef leeor_net's Avatar
    Join Date
    Apr 2004
    Location
    Charles Town, WV
    Posts
    147

    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.
    Last edited by leeor_net; 09-24-2009 at 08:55 PM.
    - Leeor

  2. #2
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,699
    The first comparison really isn't necessary, the code in the second block is sufficient. Anyway, you could use an std::map, using whatever the type of 'target' is as the key. Otherwise, just keep the array sorted at all times and use binary-search to locate the item (search complexity would be eqivalent to a perfectly balanced binary tree, eg O(log n)).

  3. #3
    Registered User
    Join Date
    Jun 2005
    Posts
    6,252
    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.
    Right 98% of the time, and don't care about the other 3%.

  4. #4
    Professional Chef leeor_net's Avatar
    Join Date
    Apr 2004
    Location
    Charles Town, WV
    Posts
    147
    Quote Originally Posted by Sebastiani View Post
    Why do you have two separate threads for this?
    I don't have two separate threads. The other thread was about finding an appropriate container. This one is about an efficient method of checking a specific container, in this case a vector, to see if a matching entry exists and, if it does, to not add it to the vector. These are also two different problems in different sections of the code.

    These are two entirely different questions.

    grumpy, thanks, but that doesn't answer my question at all.
    - Leeor

  5. #5
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by leeor_net View Post
    I don't have two separate threads. The other thread was about finding an appropriate container. This one is about an efficient method of checking a specific container, in this case a vector, to see if a matching entry exists and, if it does, to not add it to the vector. These are also two different problems in different sections of the code.

    These are two entirely different questions.

    grumpy, thanks, but that doesn't answer my question at all.
    Then perhaps you should edit your other post so that it doesn't ask the same question as this one (as of this instant when I'm typing this reply, it does ask the same question -- how to search through a vector, not "what container is really good for finding things").

    And the proof of that is the fact that the answer to the question you've elaborated above ("how to search this specific container for an item") is given in that thread -- keep your vector sorted if you need to find things in it quickly.

  6. #6
    Professional Chef leeor_net's Avatar
    Join Date
    Apr 2004
    Location
    Charles Town, WV
    Posts
    147
    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?
    - Leeor

  7. #7
    3735928559
    Join Date
    Mar 2008
    Location
    RTP
    Posts
    839
    Quote Originally Posted by leeor_net View Post
    I don't have two separate threads. The other thread was about finding an appropriate container. This one is about an efficient method of checking a specific container, in this case a vector, to see if a matching entry exists and, if it does, to not add it to the vector. These are also two different problems in different sections of the code.

    These are two entirely different questions.

    grumpy, thanks, but that doesn't answer my question at all.
    i think what grumpy may be getting at is that you may find another STL container better for your application.

    std::map does more or less exactly the job you're describing, and its access time is O(log(N))

  8. #8
    Professional Chef leeor_net's Avatar
    Join Date
    Apr 2004
    Location
    Charles Town, WV
    Posts
    147
    <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.
    Last edited by leeor_net; 09-24-2009 at 10:39 PM.
    - Leeor

  9. #9
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by leeor_net View Post
    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.
    Last edited by tabstop; 09-24-2009 at 10:34 PM.

  10. #10
    Professional Chef leeor_net's Avatar
    Join Date
    Apr 2004
    Location
    Charles Town, WV
    Posts
    147
    Actually, the entry is not by a string, it's by a particular value of an object which can change over time. But like I said above, I realized I actually don't need unique entries.

    Quote Originally Posted by tabstop View Post
    Then perhaps you should edit your other post so that it doesn't ask the same question as this one (as of this instant when I'm typing this reply, it does ask the same question -- how to search through a vector, not "what container is really good for finding things").

    And the proof of that is the fact that the answer to the question you've elaborated above ("how to search this specific container for an item") is given in that thread -- keep your vector sorted if you need to find things in it quickly.
    And just to make a point, my last thread was about "What's a better container for this particular problem given these criteria", not "How can I make this bit of code cleaner." Like I said, two different questions.
    - Leeor

  11. #11
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    If you remove the restriction on unique entries, then, well, I guess that's good.

    Just to be clear, the other thread I'm referring to is this one where you specifically ask for a more efficient method for finding an entry in a vector and never at all wonder whether a vector is the right container. If you've got a thread on whether a vector is the right container, then by all means I'd like to read it.

  12. #12
    Professional Chef leeor_net's Avatar
    Join Date
    Apr 2004
    Location
    Charles Town, WV
    Posts
    147
    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.
    Last edited by leeor_net; 09-24-2009 at 11:09 PM.
    - Leeor

  13. #13
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,598
    The duplicate thread has been deleted.

    Quote 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.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  14. #14
    Professional Chef leeor_net's Avatar
    Join Date
    Apr 2004
    Location
    Charles Town, WV
    Posts
    147
    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).
    Last edited by leeor_net; 09-25-2009 at 01:54 AM.
    - Leeor

  15. #15
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,598
    Quote 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.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. can some one please tell me the cause of the error ?
    By broli86 in forum C Programming
    Replies: 8
    Last Post: 06-26-2008, 08:36 PM
  2. syntax help?
    By scoobygoo in forum C++ Programming
    Replies: 1
    Last Post: 08-07-2007, 10:38 AM
  3. Vector class
    By Desolation in forum C++ Programming
    Replies: 2
    Last Post: 05-12-2007, 05:44 PM
  4. Need some help/advise for Public/Private classes
    By nirali35 in forum C++ Programming
    Replies: 8
    Last Post: 09-23-2006, 12:34 PM
  5. Certain functions
    By Lurker in forum C++ Programming
    Replies: 3
    Last Post: 12-26-2003, 12:26 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21