CODEWITHSUNDEEP
c++arrayswindowsc++11vector
Okkaaj
Okkaaj

Reputation: 125

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

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?

Upvotes: 2

Views: 717

Answers (7)

BЈовић
BЈовић

Reputation: 64273

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)

Upvotes: 0

Nicolas Defranoux
Nicolas Defranoux

Reputation: 2676

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

Upvotes: 1

Kiroxas
Kiroxas

Reputation: 921

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

Upvotes: 1

Sander De Dycker
Sander De Dycker

Reputation: 16243

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.

Upvotes: 0

Slava
Slava

Reputation: 44268

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;
    }
}

Upvotes: 0

Paul Evans
Paul Evans

Reputation: 27577

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;
    }
}

Upvotes: 0

Angew is no longer proud of SO
Angew is no longer proud of SO

Reputation: 171167

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;
}

Upvotes: 0

Related Questions