0
\$\begingroup\$

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;
}
\$\endgroup\$

closed as off-topic by Der Kommissar, Phrancis, Stephen Rauch, Sᴀᴍ Onᴇᴌᴀ, rolfl Apr 27 '18 at 1:13

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Code not implemented or not working as intended: Code Review is a community where programmers peer-review your working code to address issues such as security, maintainability, performance, and scalability. We require that the code be working correctly, to the best of the author's knowledge, before proceeding with a review." – Der Kommissar, Phrancis, Stephen Rauch, Sᴀᴍ Onᴇᴌᴀ, rolfl
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 5
    \$\begingroup\$ I would argue code that segfaults is not working as intended. \$\endgroup\$ – yuri Apr 26 '18 at 19:21
  • \$\begingroup\$ Can you clarify some inputs that this works on so that we have real test-cases? \$\endgroup\$ – Der Kommissar Apr 26 '18 at 19:26
  • \$\begingroup\$ vector_A {0,0,0,0,0,0,0,1,0,0,0,2} vector_B {0,0,0,2,0,0,0,1} \$\endgroup\$ – Zeeshan Hayat Apr 26 '18 at 20:15
  • \$\begingroup\$ Have you tried running under the debugger to find the segmentation fault? \$\endgroup\$ – JDługosz Apr 26 '18 at 20:22
  • \$\begingroup\$ @JDługosz upvoting is a privilege that requires 15 reputation, see also the vote up privilege. As such if they can't upvote, how would they? :) \$\endgroup\$ – Vogel612 Apr 27 '18 at 9:53
0
\$\begingroup\$
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).

\$\endgroup\$
  • \$\begingroup\$ Thanks for this. It is clear now. Clearly, I need to improve my coding skills :) \$\endgroup\$ – Zeeshan Hayat Apr 26 '18 at 20:14
  • \$\begingroup\$ Everybody does! Good coders realize that. That’s why I’m spending time here: as part of an effort to update and review my coding skills in light of language and library changes. \$\endgroup\$ – JDługosz Apr 26 '18 at 20:24
1
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ Sorting will distort the block and we will lose the information. It is important to compare in blocks. \$\endgroup\$ – Zeeshan Hayat Apr 26 '18 at 19:28
  • \$\begingroup\$ No, it will not. We have a vector of blocks, so each block will retain its original data. I.e., the order of items within each block remains unchanged. Only the order of the blocks is modified (and note that I passed the vectors in by value, so the sorting won't affect the original vectors either). \$\endgroup\$ – Jerry Coffin Apr 26 '18 at 19:30
  • \$\begingroup\$ it makes sense now. \$\endgroup\$ – Zeeshan Hayat Apr 26 '18 at 19:54

Not the answer you're looking for? Browse other questions tagged or ask your own question.