Looping through std::vector to find matches from std::string array, easier way?

Question

I am looping through std::vector and std::string array to find matches from the vector.

Example:

#include <iostream>
#include <vector>
#include <string>


int main()
{

    std::cout << "Searching...\n";

    std::vector<std::string> myVector;

    myVector.push_back("Word");
    myVector.push_back("Word2");
    myVector.push_back("Word4");
    myVector.push_back("Word6");
    myVector.push_back("Word7");


    std::string myStringArr[] = 
    {
        "Word",
        "Word1",
        "Word2",
        "Word3",
        "Word4",
        "Word5",
        "Word6",
        "Word7"
    };

    for (auto Vec : myVector)
    {
        for(auto Str : myStringArr)
        {
            if(Vec == Str)
            {
                std::cout << "Found: " << Vec << std::endl;
            }
        }
    }


    std::cin.ignore(2);
    return 0;
}

This works fine. But I am coming from C language(trying to get into C++ 11), and not sure if this is the best solution.

Platform is windows, and I do not (currently) use any external libraries like boost, as you can see from the code.

Is there a better / cleaner way to achieve the same result?

Answer 1

Your solution works fine and is good as long as the vector and the string array are not too long.
Little improvement on the code: don't use auto for simple types, it's just less readable (you could use const string& instead).

You could do something more efficient: Your algorithm complexity is O(NxM) with N and M the sizes of the vector and array.
Storing the values of the vector in a hash_set and then checking if they are in the array would be O(N+M).

Answer 2

If your array and vector are sorted, you can use std::set_intersection. According to cplusplus.com, the complexity is Up to linear in 2*(count1+count2)-1 (where countX is the distance between firstX and lastX): Compares and assigns elements. If they are not, you can sort them first, which only take O(nlog(n) + mlog(m)) (with n being the number of elements in the vector, and m in the array (or vice versa)) time, before linear for the range (this is better than your O(n*m) solution).

Here how it looks like :

#include <iostream>     // std::cout
#include <algorithm>    // std::set_intersection, std::sort
#include <vector>       // std::vector


  std::vector<std::string> intersection(myVector.size()); //needs to be allocated

  std::sort (myVector.begin(),myVector.end());    
  std::sort (myStringArr,myStringArr+10);   

  auto it = std::set_intersection (myVector.begin(), myVector.end(), //first range
                                   myStringArr, myStringArr+10, // second range
                                   intersection.begin()); // the result range

  v.resize(it-v.begin());                      

  std::cout << "The intersection has " << (v.size()) << " elements:\n";

Answer 3

Yes, you can use std::find_first_of for this:

auto itVec = myVector.begin();
for (;;) {
  itVec = std::find_first_of(itVec, myVector.end(), std::begin(myStringArr), std::end(myStringArr);
  if (itVec == myVector.end())
    break;
  std::cout << "Found: " << *itVec << '\n';
  ++itVec;
}

Answer 4

Since, in general case, both vector and array are not sorted, you have to iterate over every element. Therefore that is the best way.

Only one small thing. for (auto Vec : myVector) is going to make a copy of each element. Since std::string makes shallow copy, you will not notice. But in some other case, it may be noticable. Better way would be to use a reference :

for (const auto& Vec : myVector)

Answer 5

Use std::find_first_of:

for (auto str : myStringArr)
{
    if (std::find_first_of(str, std::begin(myVector). std::end(myVector))
    {         
        std::cout << "Found: " << str << std::endl;
    }
}

Answer 6

You can use std::set to store your strings:

std::set<std::string> myStringSet 
{
    "Word",
    "Word1",
    "Word2",
    "Word3",
    "Word4",
    "Word5",
    "Word6",
    "Word7"
};

for (auto Vec : myVector)
{
    if( myStringSet.count( Vec ) )
        {
            std::cout << "Found: " << Vec << std::endl;
        }
    }
}

Another solution is to sort your vector and use std::binary_search:

std::vector<std::string> myStringArr 
{
    "Word",
    "Word1",
    "Word2",
    "Word3",
    "Word4",
    "Word5",
    "Word6",
    "Word7"
};
std::sort( myStringArr.begin(), myStringArr.end() );

for (auto Vec : myVector)
{
    if( std::binary_search( myStringArr.begin(), myStringArr.end(), Vec ) {
        std::cout << "Found: " << Vec << std::endl;
    }
}

Answer 7

The std::set_intersection algorithm does what you want.

Sort your two data structures using std::sort (or use sorted data structures instead) :

std::sort(myVector.begin(), myVector.end());
std::sort(myStringArr, myStringArr + 8);

And then use std::set_intersection :

std::set_intersection(
    myVector.begin(), myVector.end(),
    myStringArr, myStringArr + 8,
    std::ostream_iterator<std::string>(std::cout, "\n"));

Note the use of std::ostream_iterator for printing the result on std::cout.