4
\$\begingroup\$

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;
}
\$\endgroup\$
5
\$\begingroup\$

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;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – glampert Apr 4 '15 at 17:41
  • \$\begingroup\$ @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? \$\endgroup\$ – nhgrif Apr 4 '15 at 18:49
  • \$\begingroup\$ This warning is present in g++, clang was not showing this warning \$\endgroup\$ – Steephen Apr 4 '15 at 19:57
  • \$\begingroup\$ Yep, size_t is usually uint or ulong. stackoverflow.com/a/4849646/1198654 \$\endgroup\$ – glampert Apr 4 '15 at 22:19
  • \$\begingroup\$ @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. \$\endgroup\$ – glampert Apr 4 '15 at 22:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.