Как избежать повторений при сравнении двух векторов по блокам - PullRequest
Новая
       39

Как избежать повторений при сравнении двух векторов по блокам

0 голосов
/ 27 апреля 2018

Я пытаюсь сравнить два вектора, которые имеют размер, кратный 4, и данные представлены в виде блоков (4 элемента). Каждый векторный блок имеет уникальный номер, например, {0,0,0,0}, {0,0,0,1}, {0,0,0,2} или {0,0,0,0,0, 0,0,1,0,0,0,2} и {0,0,0,2,0,0,0,1} и т. Д. Я использую итератор, который увеличивает i + = 4 каждый раз. Я написал небольшую функцию, которая выполняет работу, но блоки имеют тенденцию повторяться. Я не уверен, как удалить повторение этих блоков. например, vector_A {0,0,0,0,0,0,0,1} vector_B {0,0,0,1,0,0,0,0,0,0,0,2} он должен дать local_vector1 { 0,0,0,2} вместо этого я получаю локальный вектор_1 {0,0,0,1,0,0,0,2,0,0,0,0,0,0,0,2} 

void comparing_vectors_by_block(std::vector<int> vector_A, std::vector<int> 
vector_B)
{
const int blockSize = 4;
std::vector<int> local_vector1;
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 it_A = std::begin(vector_A); it_A != std::end(vector_A); it_A+=4)
{
    for (auto it_B = std::begin(vector_B); it_B != std::end(vector_B); it_B += 4)
    {
        bool match = equal(it_A, it_A + blockSize, it_B, it_B + blockSize);
        if (!match)
        {
            std::cout << "match :" << std::endl;
            local_vector1.insert(local_vector1.end(), it_B, it_B + blockSize);
        }
        else
        {
            std::cout << "not matched :" << std::endl;
        }
    }
}

Ответы [ 2 ]

0 голосов
/ 27 апреля 2018

Если я вас правильно понял, вы хотите получить симметричную разность двух векторов блоков. То есть для A = {0,0,0,3,0,0,0,0,0,0,0,1} и B = {0,0,0,1,0,0,0,0,0, 0,0,2} вы хотите, чтобы local_vector1 = {0,0,0,3,0,0,0,2}.

В вашей реализации вы сравниваете каждый блок вектора A с каждым блоком вектора B - конечно, вы получите дополнительные несоответствия. Мое (также не оптимизированное) решение: 

std::vector<int> get_blocked_vectors_diff( const std::vector<int>& vector_A, const std::vector<int>& vector_B )
{
    const int blockSize = 4;
    std::vector<int> local_vector;
    for ( auto it_A = std::begin( vector_A ); it_A != std::end( vector_A ); it_A += 4 )
    {
        bool found_in_B = false;
        for ( auto it_B = std::begin( vector_B ); !found_in_B && it_B != std::end( vector_B ); it_B += 4 )
        {
            found_in_B = std::equal( it_A, it_A + blockSize, it_B, it_B + blockSize );
        }
        if ( !found_in_B )
        {
            local_vector.insert( local_vector.end( ), it_A, it_A + blockSize );
        }
    }

    return local_vector;
}

void comparing_vectors_by_block(std::vector<int> vector_A, std::vector<int> vector_B)
{
    auto A_mines_B = get_blocked_vectors_diff( vector_A, vector_B );
    auto B_mines_A = get_blocked_vectors_diff( vector_B, vector_A );
    auto local_vector1( A_mines_B );
    local_vector1.insert( local_vector1.end(), B_mines_A.begin( ), B_mines_A.end( ) );

    for ( auto a : local_vector1 )
    {
         std::cout << a << " ";
    }
    std::cout << std::endl;
}

Обратите внимание, что нам нужны две части ответа: A \ B и B \ A, поэтому get_blocked_vectors_diff вызывается дважды.

Если вы измените свою структуру данных, как предложил Петр Велев, вы сможете сократить функцию get_blocked_vectors_diff: 

std::vector<int> get_blocked_vectors_diff( const std::vector<Block>& vector_A, const std::vector<Block>& vector_B )
{
    std::vector<Block> local_vector;
    for ( auto& x : vector_A )
    {
        if ( std::find( vector_B.begin( ), vector_B.end( ), x ) == vector_B.end( ) )
        {
            local_vector.push_back( x );
        }
    }

    return local_vector;
}

Лучшие решения могут быть получены, если вы сначала отсортируете свои векторы блоков.

0 голосов
/ 27 апреля 2018

Используйте вектор массивов из четырех целых для представления данных. std::vector<std::array<int,4>> vect1;

Если эти данные имеют другое значение. Лучше использовать способ ООП и создать структура или класс для представления данных четырех чисел. Затем реализуйте оператор == и другие полезные методы для структуры / класса. 

struct foo{
    int a;
    int b;
    int c;
    ind d;
};
bool foo::operator==(const X& lhs, const X& rhs){ /* do actual comparison */ }

Затем просто итерируйте вектор и сравните элементы, используя ==, как если бы вектор был типа int, например. 

for(auto& x : vector_A)
{
    if(std::find(vector_B.begin(), vector_B.end(), x) != vector_B.end()) {
         local_vector1.append(x);
    }
}
...