Determine whether one vector is a prefix of the other

Question

Exercise 5.17:

Given two vectors of ints, write a program to determine whether one vector is a prefix of the other. For vectors of unequal length, compare the number of elements of the smaller vector. For example, given the vectors containing 0, 1, 1, and 2 and 0, 1, 1, 2, 3, 5, 8, respectively your program should return true.

This executes correctly, but I just want to get this double-checked.

#include <iostream>
#include <vector>

using std::vector; using std::cout; using std::endl;

int main()
{
vector<int> v1{ 0, 1, 1, 2, 3, 5, 8 };
vector<int> v2{ 0, 1, 1, 2 };
if (v1.size() < v2.size()){
    cout << "Using v1 as the prefix to v2" << endl;
    for (int smallIndex = 0, largeIndex = 1; smallIndex != v1.size(); ++smallIndex, ++largeIndex){
        if (v1[smallIndex] == v2[largeIndex])
            cout << "v1 at position " << smallIndex << " is a prefix for v2 at postion " << largeIndex << endl;
    }
}
else if (v1.size() > v2.size()){
    cout << "Using v2 as the prefix to v1" << endl;
    for (int smallIndex = 0, largeIndex = 1; smallIndex != v2.size(); ++smallIndex, ++largeIndex){
        if (v2[smallIndex] == v1[largeIndex])
            cout << "v2 at position " << smallIndex << " is a prefix for v1 at position " << largeIndex << endl;
    }
}
else {      //  v1.size() == v2.size() only comparing the first as the prefix to the second
    cout << "Size of v1 and v2 are the same, using v1 as the prefix to v2" << endl;
    for (int smallIndex = 0, largeIndex = 1; largeIndex != v1.size(); ++smallIndex, ++largeIndex){
        if (v1[smallIndex] == v2[largeIndex])
                cout << "v1 at position " << smallIndex << " is a prefix for v2 at postion " << largeIndex << endl;
        }
    }
}

Answer 1

For a prefix search, you can use std::mismatch() in <algorithm>.

bool isPrefix(const std::vector<int>& v1, const std::vector<int>& v2) {
    if (v1.size() > v2.size()) {
        return v2.end() == std::mismatch(v2.begin(), v2.end(), v1.begin()).first;
    }
    return v1.end() == std::mismatch(v1.begin(), v1.end(), v2.begin()).first;
}

Answer 2

Right now your code has quite a bit of repetition--basically three repetitions, for v1 shorter than v2, v2 shorter than v1, and v1/v2 being the same length.

It seems like it would be easier to find the shorter of the two, then compare from zero to that size:

bool is_prefix(std::vector<int> const &v1, std::vector<int> const &v2) { 
    size_t len = std::min(v1.size(), v2.size());

    for (size_t i=0; i<len; i++)
        if (v1[i] != v2[i])
            return false;
    return true;
}

You can also use std::equal to do most of the work:

    size_t len = std::min(v1.size(), v2.size());

    return std::equal(v1.begin(), v1.begin()+len, 
                      v2.begin(), v2.begin()+len);

Of course, you can also make it generic so it can handle different container types and/or different contained types, but I'll leave that discussion for another day.

Other details:

1. Rather than printing out a running commentary for every position in the arrays, I'd rather see (as above) a single result to indicate whether one is a prefix of the other or not.
2. I'd avoid using endl. All you really want here is a new-line, so just print out '\n'.
3. As shown above, it looks to me like the intended logic is rather simpler than what your code uses.

Answer 3

Offhand, this doesn't look 100% correct. For example, if both vectors are empty, it will loop forever on the bottom for loop (I ran it with 2 empty lists and it segfaults). Also, your program prints out a lot, but never actually says if the vector is a prefix of the other vector.

You should make a function like

bool isPrefixOf(vector<int> v1, vector<int> v2){}

and then call that in the main method with your two vectors.

The logic in your code seems off too. You're comparing the wrong values of the vectors (There shouldn't be a smallIndex and a largeIndex since you should be comparing them at the same index.) If you're looking to actually find if it's a prefix, put them like so in the function (this is the last loop)

    for (int smallIndex = 0; smallIndex != v1.size(); ++smallIndex){
        if (v1[smallIndex] != v2[smallIndex])
            return false;
    }
    return true;