3

For instance. I have some structure:

s_Some{
  std::string lable;
  s_some_junk some_junk;
};

And a vector:

std::vector<s_Some> mSome;

And then I fill this vector with a lot of s_Somes.

I need to find an iterator for a single s_Some in this vector, which has a specific lable. So far I just iterate through all of this junk and match every lable with the one wanted. This looks a little bit stupid to me. Is there a better way to do so?

akalenuk
  • 3,815
  • 4
  • 34
  • 56
  • http://stackoverflow.com/questions/6277646/c-how-to-check-if-stdvectorstring-contains-a-value – Ben Nov 08 '12 at 02:27

5 Answers5

10

Option 1) If you are compelled to use the std::vector, but once the vector is filled it stays unchanged, then you could sort the vector and use the binary search. The only cost would be the sorting then and there will be no additional overhead. Searching time is logarithmic O(logN).

Option 2) If you have the freedom and can choose different data structure, then consider using the map (also logarithmic) or unordered_map ( expected O(1), worst O(n) ).

I have just noticed that you said you wanted to match every label with the one being looked for. So I conclude you can have duplicate labels. Then for point 2 use corresponding multi_map containers, while for point 1 things get a bit messier.

Anonymous
  • 18,162
  • 2
  • 41
  • 64
5

If you are to search only a few times or if your vector is likely to have different content every time you search, there's unfortunately no alternative; you will have to iterate through the whole vector.

If however your vector is not going to change once created and you have to run a large number of searches, do this:

  1. Sort the vector in the ascending order of strings (the way they lie in the dictionary, that is).
  2. Once thus sorted, use binary search algorithm for all searches.

This will be far quicker.

G S
  • 35,511
  • 22
  • 84
  • 118
3

Use a 

std::multimap< string, s_Some > mSome;

and 

mSome.insert( std::make_pair( aSome.lable, aSome ) );

Find the first instance of the value of lable you want by

mSome.find( lable_you_want );

The next instance will be found by incrementing the iterator.

cf. http://www.cppreference.com/wiki/stl/multimap/start

That is, unless you're required to use a std::vector.

Rob K
  • 8,757
  • 2
  • 32
  • 36
1

You could also use a Map of Lists

Tom Ritter
  • 99,986
  • 30
  • 138
  • 174
1

You can find_if algorithm to do this. Define a predicate some thing like this:

struct isEqual
{
    isEqual(const std::string& s): m_s(s)
    {}
    bool operator()(S_Some& l)
    {
        return l.lable == m_s;
    }

    std::string m_s;
};

And while searching you can use

std::vector<S_Some>::iterator iter = std::find_if(mSome.begin(),
                                                  mSome.end(),
                                                  isEqual(std::string("AAAA"));
Martin York
  • 257,169
  • 86
  • 333
  • 562
Naveen
  • 74,600
  • 47
  • 176
  • 233
  • But this is just a nicer way of writing the for loop. The complexity will be still linear, no improvement. STL find_if will just traverse the vector from the begin till match/end. – Anonymous Feb 03 '09 at 17:03
  • Yes, I thought (from the question header) he wants to avoid writing the loop him self..Probably I didn't understand the question correctly, I thought we have to use the vector – Naveen Feb 03 '09 at 17:05
  • Right, both interpretations seem plausible ;) – Anonymous Feb 03 '09 at 17:09
  • Now when I read it again with the performance perspective, I see the sentence "This looks a little bit stupid to me. Is there a better way to do so?" in a totally different way.. – Naveen Feb 03 '09 at 17:33