Comparing two vectors of arbitrary size, block by block [closed]

Question

I am trying to compare two vectors which are of size of multiple of 4. Each vector block has a unique number it e.g {0,0,0,0}, {0,0,0,1}, {0,0,0,2} or {0,0,0,0,0,0,0,1,0,0,0,2} and {0,0,0,2,0,0,0,1} so on. I first divide the vector in block of 4 and than compare it and save the block which is not present in another vector into a global vector. I wrote a small function which do the job but often shows segmentation error.

void comparing_vectors_by_block(std::vector<int> vector_A, std::vector<int> 
vector_B)
{
int blockSize = 4;
std::vector<int>::iterator start_of_A = vector_A.begin();
std::vector<int>::iterator start_of_B = vector_B.begin();

std::vector<int> subList_A;
std::vector<int> subList_B;
std::cout << "size of the vector_A: " << vector_A.size() << std::endl;
std::cout << "size of the vector_B: " << vector_B.size() << std::endl;
for (auto i = 0; i < vector_A.size() / blockSize; i++)
{
    subList_A.assign(start_of_A, start_of_A + blockSize);
    for (auto i = 0; i < vector_B.size() / blockSize; i++)
    {
        subList_B.assign(start_of_B, start_of_B + blockSize);
        if (subList_A != subList_B)
        {

            hold_result.insert(hold_result.begin(), start_of_B, start_of_B + blockSize);
            start_of_B += blockSize;
        }
        else
        {
            start_of_B += blockSize;
            std::cout << "both vectors are not equal: " << std::endl;
        }
    }
    start_of_A += blockSize;
}

Answer 1

void comparing_vectors_by_block(std::vector<int> vector_A, std::vector<int> vector_B)

First of all, why are you passing them by value? Do you really need to copy them into the function? I don’t think so.

Since you use that type a few times, make a handy name for it.

using VecInt = std::vector<int>;

void comparing_by_block (const VecInt& A, const VecInt& B)

You’ll also notice that I don’t restate the types as part of the names. If you have another kind of thing to compare by block, you’ll just overload the function name (or turn it into a template). That’s why you don’t want A and B to be "vector A" as well: you use iterators and don’t worry about the actual type from then on. If you later make it generic, you won’t have meaningless names to change!

---

int blockSize = 4;

Make this const since it never changes. You may later move it to a parameter or elsewhere… that is the kind of way real-world code evolves.

Then, check your requirements.

const int blockSize = 4;

using std::size;
using std::begin;
using std::end;

if (size(A)%blocksize != 0 || size(B)%blocksize != 0)
    throw std::invalid_argument ("wrong⋯");

Note the use of non-member functions for size, begin, end — this is best practice and will make the code suitable for generic-izing. They must be unqualified so the using is necessary. Sorry if that’s a bit advanced for you at the moment; just remember the rules for now.

---

std::vector<int>::iterator start_of_A = vector_A.begin();
std::vector<int>::iterator start_of_B = vector_B.begin();

Use auto (almost everywhere).

auto start_of_A = begin(A);
auto start_of_B = begin(B);

Now isn’t that better? And you didn’t even have to fix it when you changed the function parameters to be const references!

---

for (auto i = 0; i < vector_B.size() / blockSize; i++)

We really want to get rid of legacy for loops, but there is no simple way to do that given the way you wrote the algorithm. Repeating the call to size(B) each time through the loop could be avoided by assigning it to a named variable first, but if B becomes const as indicated in the first item, it won’t matter.

However, I point out that you should get used to writing ++i rather than i++ in these things. For int it doesn’t matter; but you will use iterators most often and you don’t want this one to look funny and make the reader wonder "why is it postfix? Oh, it’s OK for this time.)

Sticking to idiomatic code makes it easier to read and maintain later.

---

To remember a specific range, you do not need to copy the elements into another vector. Just remember the iterator positions.

⋯assign
⋯assign
if (subList_A != subList_B)

becomes

bool match = std::equal (
    start_of_A, start_of_A + blockSize,
    start_of_B, start_of_B + blockSize);
if (!match)

---

hold_result.insert(hold_result.begin(), start_of_B, start_of_B + blockSize);

Is it necessary to add each find to the beginning of the result? It would be faster (and easier) to append instead.

---

So just what is it you’re trying to achieve? I did not understand the paragraph at the beginning of your post.

Let’s decode the code:

For each block in A,
For every block in B that is different from the current block in A, copy it to hold_result. For each block in B that matches the current block in A, output “both vectors are not equal”. That doesn’t make sense to me. You will print this if the vectors are in fact equal, but more generally will print many times, each time a portion of the vectors are equal.

The start_of_B is incremented in both branches, rather than in common code as part of the loop.

The hold_result will contain multiple copies of blocks of B, each time it does not match one of the blocks in A. What is the point of that?

---

Looking for bugs:
You complain of coredump. Looking at the loop bounds, i and start_of_A (and B) are redundant. Your loop is controlled by i but the value of the iterator is what you really care about and what can cause issues if out of range.

Do you update the iterator every time through the loop exactly once? Yes. This would be easier to figure out if the loop was written to use that for iteration directly. Having the B iterator updated in multiple places in branches is a bug waiting to happen, even though it’s OK now.

If the vector lengths are not multiples of the blocksize, the code to rounds down so it ignores the remaining elements. That’s OK — taking an incomplete block ending at start+blocksize would cause an access error, so look carefully there.

I don’t see any access error in the code you posted (noting that hold_result is also a vector).

Answer 2

If at all possible, I'd start from a slightly different direction. I'd start by defining the group of 4 ints as a type:

static const int blocksize = 4;

class block {
    std::array<int, blocksize> data;

    bool operator<(block const &other) { 
        for (int i=0; i<blocksize; i++)
            if (data[i] < other.data[i])
                return true;
            if (other.data[i] < data[i])
                return false;
        }
        return false;
    }
};

Having done that, you can use a standard algorithm to get the desired result:

std::vector<block> find_diff(std::vector<block> a, std::vector<block> b) {
    std::vector<block> difference; // where we'll put the result

    // set operations require sorted inputs   
    std::sort(a.begin(), a.end());
    std::sort(b.begin(), b.end());

    std::set_difference(a.begin(), a.end(), 
                        b.begin(), b.end(), 
                        std::back_inserter(difference));
    return difference;
}