Determining whether one vector is a prefix of the other

Question

I am learning from C++ Primer 5th edition. This is 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.

#include <iostream>
#include <string>
#include <vector>
using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;
using std::end;
using std::begin;
int main()
{
 vector<int> i{0,1,1,2}, n{0,1,1,2,3,5,8}, smlr;
 char sml, bgr;
 long j = (i.end()-i.begin()) ,k = (n.end()-n.begin());
 if ( j > k)
 {
 sml = 'n', bgr = 'i', smlr = n;
 }
 else if (j < k)
 {
 sml = 'i', bgr = 'n', smlr = i;
 }
 else if ( j == k)
 {
 cout << "both are of equal length";
 for (vector<int>::size_type a = 0; a < i.size() ; ++a ) {
 if (i[a] != n[a]) {
 cout << "both vectors are unequal and are not prefixes of the other";
 return -1;
 }
 }
 }
 for ( int l = 0; l < smlr.size() && i[l] == n[l]; ++l )
 {
 if(l == (smlr.size()-1))
 {
 cout << sml << " is a prefix of " << bgr;
 return 0;
 }
 }
 cout << sml << " is not a prefix of " << bgr;
 return 0;
}

1. Is my code efficient?
2. Am I using too many variables?
3. Is it better to write more code and use less variables or use less variables and less code?

I am a beginner, so please be harsh.

Answer 1

Ok first, we want to determine if some condition is true or not based on some input. That calls for a boolean function! In particular, our inputs are two vectors. :

bool isPrefixOf(const std::vector<int>& smaller, const std::vector<int>& larger) 
{
 ...
}

I named the first variable smaller, but it might not actually be smaller! Let's make sure that it is:

 if (smaller.size() > larger.size())
 {
 std::swap(smaller, larger); // this very efficiently swaps our vectors
 // in constant time
 }

Now once we got that, the algorithm in your j == k is exactly correct, but pretty hard to read. The convention is to use variables like i, j, k solely as indices in loops, not as important variables. So I'll rewrite it like this:

 for (int i = 0; i < smaller.size(); ++i) 
 {
 if (smaller[i] != larger[i]) 
 {
 return false; // clearly not a prefix
 }
 }
 return true; // we match up, so we must be done!
}

So cool, we got our function that checks if a smaller vector is a prefix of a larger vector, so now our main just has to determine which way we call it:

int main() 
{
 vector<int> vec1{0, 1, 1, 2};
 vector<int> vec2{0, 1, 1, 2, 3, 5, 8};
 cout << "vec1 is a prefix of vec2?: " << isPrefixOf(vec1, vec2) << endl;
}

Which should print true. So in general, your variable names don't line up with convention, and you coded the same logic twice - don't repeat yourself! Take advantage of functions to encode conceptually distinct functionality.

• Deohboeh: Hey! Thanks for the reply! I will take precautions from now on... I am trying to use the code you posted but it keeps showing an error: No matching function for call to ‘swap’ I am using Xcode 4.6.3 and added the header <utility>
• Deohboeh: I added that too but still the same error persists..
• Deohboeh: I copy pasted your code.. I finally replaced std::swap(smaller, larger); with larger.swap(smaller); and still it didn’t work. This helped me figure out the problem.. The arguments for isPrefixOf() are consts but swap cannot have consts as arguments. As its essentially changing both the objects. Phew
• 200_success: If the order of the arguments is interchangeable, then I would prefer to see them named symmetrically. As written, I would assume that it only checks for smaller being a prefix of larger, and not vice versa.
• 200_success: To preserve constness, instead of using std::swap(), have isPrefixOf(a, b) call itself as isPrefixOf(b, a) if a is longer than b.