Find non duplicate Triangle Triplets from a list of given numbers- version 3

Question

It is a continuation of my previous question:

Find non duplicateTriangle Triplets from a list of given numbers

After I realized triplet structure using less space than std:vector<int> and there is a simple way to remove duplicates from the triplets list by modifying loops index I rewrote the code again. On top of that it may be impossible to write a \$O(N^2)\$ solution for a three dimensional problem in this case. There are a few additional changes also: using lambda to avoid a function call and a few direct initialization attempts instead depending on assignment operations.

#include<vector>
#include<iostream>

struct Triplet 
{
    int first;
    int second;
    int third;
};

std::vector<Triplet> findTriangleTriplets( std::vector<int>& vec_input ) 
{
    std::vector<Triplet> triplets;
    unsigned int size = vec_input.size();

    for( unsigned int i=0; i < size; ++i ) 
    {
        for( unsigned int j = i; j < size; ++j ) 
        {
            for( unsigned int k = j; k < size; ++k)
            {
                int first  ( vec_input.at( i ) );
                int second ( vec_input.at( j ) );
                int third  ( vec_input.at( k ) );

                if( [ &first, &second, &third ] {                    
                       return ( ( second + third  ) > first   )&&
                              ( ( first + third   ) > second  )&&
                              ( ( first + second  ) > third  );                                 
                    }())                 
                {
                    triplets.emplace_back( Triplet{ first, second, third } );
                }
            }
        }
    }
    return triplets;
}

int main()
{
    std::vector<int> vec_input {  2, 4,  5, };

    std::vector<Triplet> triplets = findTriangleTriplets( vec_input );
    for ( auto &x : triplets )
    {
        std::cout<<x.first<<" "<<x.second<<" "<<x.third<<"\n";
    }
    return 0;
}

Answer 1

I have followed your previous implementations and I don't think there is much else you can change, code-wise. The next step is probably optimizing the algorithm, just like you've said.

Some nitpicking:

• I personally didn't like your in-place lambda. It looks basically like a raw conditional, but with more boilerplate around it. Either make it a proper function or just leave the conditional as it was in the first iteration. Your hybrid approach does not appeal to me.

• If you use push_back() instead of emplace_back(), you'll be able to omit repeating the type Triplet. Effectively, the results will be the same, since we are dealing with plain integers, so there's no way to avoid copying them. Use the DRYer version:

  triplets.push_back( { first, second, third } );
  

• unsigned int is likely smaller than vector::size_type on 64bit platforms. Realistically speaking, you probably don't need 64bit indexing, but a safer approach would be to use std::size_t or vector::size_type itself.

• You can sprinkle a few consts here and there, such as for size, first, second and third. Right now the function is small, so it is easy to track the variables and see that they are never changed. However, if it were to be expanded in the future, it would aid the reader a lot to have an immutability guarantee when first spotting the variable declaration. Very important though, vec_input, as the name suggests, is input/read-only. So it must not be changed. Definitely make it const!

• Any chance you can "guesstimate" the size of triplets when entering the function to reserve() some memory? If you could, that would potentially save a lot of time wasted with reallocations and copies done by [push|emplace]_back.

Answer 2

Obviously, sorting the array beforehands drives the complexity from \$O(n^3)\$ down to \$O(n^2\log n)\$. The rest is shavings.