Find Triangle Triplets from a list of given numbers

If a triplet of segments A, B and C are triangle triplets if and only if

• A + B > C
• A + C > B
• B + C > A

Is there a better implementation for this problem?

#include<vector>
#include<iostream>

void findTriangleTriplets( std::vector<int>& vec_input, std::vector<std::vector<int>>& triplets)
{
int size =  vec_input.size();
for(int i = 0; i < size; ++i)
{
for(int j = i+1; j < size; ++j)
{
for(int k = 0; k < size; ++k)
{
if( ( ( vec_input.at( i ) + vec_input.at( j ) ) > vec_input.at( k ) ) &&
( ( vec_input.at( i ) + vec_input.at( k ) ) > vec_input.at( j ) ) &&
( ( vec_input.at( j ) + vec_input.at( k ) ) > vec_input.at( i ) ) )
{
std::vector<int> temp;
temp.emplace_back( vec_input.at( i ) );
temp.emplace_back( vec_input.at( j ) );
temp.emplace_back( vec_input.at( k ) );
triplets.emplace_back( temp );
}
}
}
}
}

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

findTriangleTriplets( vec_input,  triplets);
for ( auto &x : triplets)
{
std::cout<<x.at(0)<<" "<<x.at(1)<<" "<<x.at(2)<<"\n";
}

return 0;
}


First thing to comment on after copying and pasting into my IDE, the following line gives a warning:

int size = vec_input.size();


Implicit conversion loses integer precision: 'size_type' (aka 'unsigned long') to 'int'

Apparently, the size() method of Vector returns an unsigned long, and we should use this type for our size, rather than int.

unsigned long size = input.size();


Functions that return void but accept (and modify) an argument passed by reference are always a warning sign for me. Here, I don't think there's a particularly good reason to do so.

Here, I can't see any good reason to be doing so. We create and return a vector within the function, and only accept the input argument.

Another problem I see: the result we're giving the caller is a vector of vectors, and the inner vectors are supposed to always have exactly 3 values in it. Why don't we create a struct to represent the triplets?

struct Triplet {
int a;
int b;
int c;
}


Now we can return a vector of these.

I would also abstract that complex conditional into its own function.

bool isTriplet(int a, int b, int c) {
return ((a + b) > c) && ((a + c) > b) && ((b + c) > a);
}


Now, putting all that together, without changing the algorithm or any of the logic, the code looks like this:

#include<vector>
#include<iostream>

struct Triplet {
int a;
int b;
int c;
};

bool isTriplet(int a, int b, int c) {
return ((a + b) > c) && ((a + c) > b) && ((b + c) > a);
}

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

for(int i=0;i<size;++i) {
for(int j=i+1;j<size;++j) {
for(int k=0;k<size;++k) {
int a = input.at(i);
int b = input.at(j);
int c = input.at(k);

if(isTriplet(a, b, c)) {
Triplet t = Triplet{a,b,c};
triplets.emplace_back(t);
}
}
}
}

return triplets;
}

int main()
{
std::vector<Triplet> triplets;
std::vector<int> vec_input { 1, 2, 3, 4, 5, 6 };

triplets = findTriangleTriplets(vec_input);
for ( auto &x : triplets)
{
std::cout<<x.a<<" "<<x.b<<" "<<x.c<<"\n";
}

return 0;
}

• Yes, vector<T>::size() returns vector<T>::size_type, which is more likely a typedef to std::size_t than to unsigned long. However, in this case, auto would have been the ideal usage: auto size = vec_input.size();. Let the compiler figure that out. Good review, nevertheless. Apr 4, 2015 at 17:41
• @glampert Yeah, I'm not C++ expert. My IDE was warning me that it was unsigned long, so that's what I used. auto does seem like it would be good indeed (I really didn't know what it did, but I think I got it now...) size_t is probably typedef'd to unsigned long? Apr 4, 2015 at 18:49
• This warning is present in g++, clang was not showing this warning Apr 4, 2015 at 19:57
• Yep, size_t is usually uint or ulong. stackoverflow.com/a/4849646/1198654 Apr 4, 2015 at 22:19
• @Steephen, indeed clang seems to miss this even with -Wall and -Wextra. If you try compiling with the -Weverything flag, you'll see that clang does this value narrowing diagnostic under the -Wshorten-64-to-32 flag. Apr 4, 2015 at 22:27