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.

• Steephen: @glimpert I recalled a negative comment from Stroustrup regarding the usage of std::vector::reserve for optimization in book "Programming C++". Even before I read it was a suggested optimization from Scott Mayers, in his book 'Effective STL'.
• Steephen: @glimpert stroustrup.com/bs_faq2.html#slow-containers "People sometimes worry about the cost of std::vector growing incrementally. I used to worry about that and used reserve() to optimize the growth. After measuring my code and repeatedly having trouble finding the performance benefits of reserve() in real programs, I stopped using it except where it is needed to avoid iterator invalidation (a rare case in my code). Again: measure before you optimize. "
• glampert: @Steephen, you're absolutely on the money about measuring before optimizing. I really just suggested that because, as you have probably figured by yourself, there isn't much that can be changed to make it more efficient, without taking a whole new approach. Reserving memory is the only possible optimization I can think of, but yes, without measurement, it is a shot in the dark.

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.

• JS1: Not only is this not obvious, it's incorrect. How are you going to output O(N^3) triplets in O(N^2 log N) time? Although if the question were to output the count of valid triangle triplets, you'd be correct.