What is the nicest way to find a specific string in vector?

Question

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?

Solution 1

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.

Solution 2

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.

Solution 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.

Solution 4

You could also use a Map of Lists

Solution 5

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"));

View more solutions

Comments

[Anonymous]

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.

[Kiran Kumar]

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

[Anonymous]

Right, both interpretations seem plausible ;)