How to compare two arrays and return non matching values in C++

Question

I would like to parse through two vectors of strings and find the strings that match each other and the ones that do not.

Example of what I want get:
input vector 1 would look like: [string1, string2, string3]
input vector 2 would look like: [string2, string3, string4]

Ideal output:
string1: No Match
string2: Match
string3: Match
string4: No Match

At the moment I use this code:

vector<string> function(vector<string> sequences, vector<string> second_sequences){

 for(vector<string>::size_type i = 0; i != sequences.size(); i++) {
  for(vector<string>::size_type j = 0; j != second_sequences.size(); j++){
   if (sequences[i] == second_sequences[j]){
     cout << "Match: " << sequences[i];
    }else{
     cout << "No Match: " << sequences[i];
     cout << "No Match: " << second_sequences[j];
   }
  }
 }  
}

It works great for the ones that match, but iterates over everything so many times,
and the ones that do not match get printed a large number of times.

How can I improve this?

I think `i = i++` should just be `++i` (same with `j` obvs). — Galik, Sep 20 '14 at 04:37
also sorting the first array and doing a binary search vs second array as input should improve your results — Chubosaurus Software, Sep 20 '14 at 04:46
This can be accomplished by sorting and using set_intersection and set_symmetric_difference. See here: http://ideone.com/y0o5St — PaulMcKenzie, Sep 20 '14 at 05:26
Not only is the implementation I linked to works properly, it is faster in time complexity than the double nested loop that you are trying to get working. Bottom line is this -- if you're writing a function that sounds like it has been done before, chances are there are algorithm functions that do the job. Finding mismatch or same items given two sequences is something that is done often, so there are algorithm functions that performs such tasks. — PaulMcKenzie, Sep 20 '14 at 05:38
See: [Why are these constructs undefined behavior?](http://stackoverflow.com/q/949433/315052) — jxh, Sep 20 '14 at 05:57

NGI · Answer 1 · 2014-09-20T18:41:40.337

The best code is the code that you did not have to write.

If you take a (STL) map container it will take care for you of sorting and memorizing the different strings you encounter.

So let the container works for us.

I propose a small code quickly written. You need for this syntax to enable at least the C++ 2011 option of your compiler ( -std=c++11 on gcc for example ). The syntax that should be used before C++11 is much more verbose (but should be known from a scholar point of view ).

You have only a single loop. This is only a hint for you ( my code does not take into account that in the second vector string4 could be present more than once, but I let you arrange it to your exact needs)

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


using namespace std;


vector<string> v1 { "string1","string2","string3"};
vector<string> v2 { "string2","string3","string4"};

//ordered map will take care of "alphabetical" ordering
//The key are the strings
//the value is a counter ( or could be any object of your own
//containing more information )
map<string,int> my_map;

int main()
{
    cout << "Hello world!" << endl;

    //The first vector feeds the map before comparison with
    //The second vector
    for ( const auto & cstr_ref:v1)
        my_map[cstr_ref] = 0;

    //We will look into the second vector ( it could also be the third,
    //the fourth... )
    for ( const auto & cstr_ref:v2)
    {
        auto iterpair = my_map.equal_range(cstr_ref);

        if ( my_map.end() != iterpair.first )
        {
            //if the element already exist we increment the counter
            iterpair.first->second += 1;
        }
        else
        {
            //otherwise we put the string inside the map
            my_map[cstr_ref] = 0;
        }

    }

    for ( const auto & map_iter: my_map)
    {
        if ( 0 < map_iter.second )
        {
            cout  << "Match    :";
        }
        else
        {
            cout  << "No Match :" ;
        }

        cout << map_iter.first << endl;
    }


    return 0;
}

Output:

No Match :string1
Match    :string2
Match    :string3
No Match :string4

score 0 · Answer 2 · answered Aug 23 '17 at 22:25

std::sort(std::begin(v1), std::end(v1));
std::sort(std::begin(v2), std::end(v2));

std::vector<std::string> common_elements;
std::set_intersection(std::begin(v1), std::end(v1)
                    , std::begin(v2), std::end(v2)
                    , std::back_inserter(common_elements));

for(auto const& s : common_elements)
{
    std::cout<<s<<std::endl;
}

How to compare two arrays and return non matching values in C++

2 Answers2