Concatenate multiple std::vectors taking duplicates into account in c++17

Question

Even though it is straight-forward to concatenate two std::vectors in C++, especially with ranges, I have a slightly different problem.

Say I have the following vectors: {1,2,6}, {6, 8, 9}, {9, 8, 10}, and so on. If the tail of one vector is the same as the head of the next vector that is being concatenated to, I want only one element to be in the final vector, something like this:

conc({1,2,6}, {6,8,9}, {9,8,10}, {0, 1}) = {1,2,6,8,9,8,10,0,1}

I was able to do this using if conditions, but I do not think it is efficient as I have to do this hundreds of thousands of times, preferably using STL and no external libraries.

In case it might help, there will always be only 4 vectors that have to be concatenated.

Edit: There might or might not be the same elements at the end and beginning of the vectors that are being concatenated.

#include <vector>
#include <iostream>

int main()
{
    std::vector<int> v1{1,2,6};
    std::vector<int> v2{6,8,9};
    std::vector<int> v3{9,8,10};
    std::vector<int> v4{0, 1};

    std::vector<int>V{v1};
     
    

    if (v1.back() == v2.front())
    {
        for(auto it= v2.begin()+1; it != v2.end(); ++it)
        {
            V.push_back(*it);
        }
    }
    else
    {
         for(auto it= v2.begin(); it != v2.end(); ++it)
        {
            V.push_back(*it);
        }
    }

    //repeat the above prcess for other vectors
    
}

Answer 1

Another solution is to use an auxiliary container such as a std::deque:

#include <iostream>
#include <deque>
#include <vector>

std::vector<int> concat(const std::vector<std::vector<int>>& v2d)
{
    std::deque<int> sDeque;
    for (auto& v : v2d)
    {
        for (auto v2 : v)
        {
            if (sDeque.empty())
                sDeque.push_front(v2);
            else
            if ( sDeque.front() != v2 )
                sDeque.push_front(v2);
        }
    }
    return { sDeque.rbegin(), sDeque.rend() };
}

int main()
{
    auto v = concat({ {1,2,6}, {6,8,9}, {9,8,10}, {0, 1} });
    for (auto i : v)
        std::cout << i << " ";
}

Output:

1 2 6 8 9 8 10 0 1 

Answer 2

You can do something like the following.

#include <iostream>
#include <vector>
#include <iterator>

int main() 
{
    std::vector<int> v1 = {1,2,6}, v2 = {6,8,9}, v3 = {9,8,10}, v4 = {0, 1};
    
    for ( auto p : { &v2, &v3, &v4 } )
    {
        auto it = std::begin( *p );

        if ( v1.back() == p->front() )
        {
            std::advance( it, 1 );
        }           

        v1.insert( std::end( v1 ), it, std::end( *p ) );
    }
    
    for ( const auto &item : v1 )
    {
        std::cout << item << ' ';
    }
    std::cout << '\n';
    
    return 0;
}

The program output is

1 2 6 8 9 8 10 0 1

Or you can preliminary reserve enough space in the vector v1. For example

#include <iostream>
#include <vector>
#include <iterator>

int main() 
{
    std::vector<int> v1 = {1,2,6}, v2 = {6,8,9}, v3 = {9,8,10}, v4 = {0, 1};
    
    std::vector<int>::size_type n = v1.size();
    auto last = v1.back();
    
    for ( auto p : { &v2, &v3, &v4 } )
    {
        n += last == p->front() ? p->size() - 1 : p->size();
        last = p->back();
    }
    
    v1.reserve( n );
    
    for ( auto p : { &v2, &v3, &v4 } )
    {
        auto it = std::begin( *p );

        if ( v1.back() == p->front() )
        {
            std::advance( it, 1 );
        }           

        v1.insert( std::end( v1 ), it, std::end( *p ) );
    }
    
    for ( const auto &item : v1 )
    {
        std::cout << item << ' ';
    }
    std::cout << '\n';
    
    return 0;
}