current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 6 down vote favorite

There are some things I am not sure of from a professional standpoint about the "correct" way to write C++ code. I have been looking through source code produced by various opensource projects, as well as other code posted here and on Stack Overflow.

So let's just leave it at this. Let's say I am interviewing for company A over the phone. Not white board yet. They ask me to write the code below and turn it in a hour. This is a hypothetical situation, however it parallels how most "big" companies are interviewing nowadays. Would this code "get me the job"? If not, what would you change, or what can you coach me with so I can get a job programming?

#include <iostream>
#include <queue>
#include <algorithm>
#include <iterator>
/* 
 * This program reads a sequence of pairs of nonnegative integers
 * less than N from standard input (interpreting the pair p q to
 * mean "connect object p to object q") and prints out pair 
 * representing objects that are not yet connected. It maintains an
 * array id that has an entry for each object, with the property
 * that id[p] and id[q] are equal if and only if p and q are 
 * connected.
 */

static const int N = 10;
int main( int argc, char *argv[ ] )
{
    /*
     * Ease the type of long types
     */ 
    typedef std::ostream_iterator<int> output_data;
    typedef typename std::vector<int>::iterator v_it;

    /*
     * Generate Test Data
     */
    std::pair<int,int> pairs[12] = { 
                                    std::pair<int,int>( 3,4 ),
                                    std::pair<int,int>( 4,9 ),
                                    std::pair<int,int>( 8,0 ),
                                    std::pair<int,int>( 2,3 ),
                                    std::pair<int,int>( 5,6 ),
                                    std::pair<int,int>( 2,9 ),
                                    std::pair<int,int>( 5,9 ),
                                    std::pair<int,int>( 7,3 ),
                                    std::pair<int,int>( 4,8 ),
                                    std::pair<int,int>( 5,6 ),
                                    std::pair<int,int>( 0,2 ),
                                    std::pair<int,int>( 6,1 )
                                  };
    /*
     * Load Test Data onto Queue
     */ 
    std::queue<std::pair<int,int> > queue;
    for( int x=0;x<12;x++ )
    {
        queue.push( pairs[x] );
    }

    /*
     * Data strucutre to represent nodes in graph.
     * An index in the vector is an id for a node.
     */  
    std::vector<int> id;

    /*
     * Start the nodes as not being connected
     */  
    id.reserve( N );
    for( int i = 0;i<N;i++ ) id.push_back( i );
    std::cout << "p q\t";

    /*
     * Output the data
     */  
    copy( id.begin( ), id.end( ), output_data( std::cout, " " ) );
    std::cout << std::endl;
    std::cout << "------------------------------------";
    std::cout << std::endl;

    /*
     * Algorithm to find out if wheter or not any two
     * given pair p-q is connected. It does not show
     * how they are connected.
     */
    v_it start = id.begin( );
    while( !queue.empty( ) )
    {
        std::pair<int,int> &pair = queue.front( );
        int p = pair.first;
        int q = pair.second;
        int t = *(start+p);
        if( t == *(start+q) ) 
        {
        }
        else
        {
            for( v_it i = id.begin( ); i < id.end( ); i++ ) 
            {
                if( *(i) == t )
                {
                    *(i) = *(start+q);
                }
            }
        }
        std::cout << p << " " << q << "\t";
        copy( &id[0], &id[N], output_data( std::cout, " " ) );
        std::cout << std::endl;
        queue.pop( );
    }
}

The output and arguments to gcc would look like this:

[mehoggan@desktop robert_sedgewick]$ g++ -o qf -Wall ./quick_find.cpp 
[mehoggan@desktop robert_sedgewick]$ ./qf 
p q 0 1 2 3 4 5 6 7 8 9 
------------------------------------
3 4 0 1 2 4 4 5 6 7 8 9 
4 9 0 1 2 9 9 5 6 7 8 9 
8 0 0 1 2 9 9 5 6 7 0 9 
2 3 0 1 9 9 9 5 6 7 0 9 
5 6 0 1 9 9 9 6 6 7 0 9 
2 9 0 1 9 9 9 6 6 7 0 9 
5 9 0 1 9 9 9 9 9 7 0 9 
7 3 0 1 9 9 9 9 9 9 0 9 
4 8 0 1 0 0 0 0 0 0 0 0 
5 6 0 1 0 0 0 0 0 0 0 0 
0 2 0 1 0 0 0 0 0 0 0 0 
6 1 1 1 1 1 1 1 1 1 1 1

Update

I made the changes but I have a few questions about semantics. I am going to ask those questions on Stack Overflow, so as to not pollute this post. Anyways here is the updated code (minus those filthy macros).

#include <iostream>
#include <queue>
#include <algorithm>
#include <iterator>
/* 
 * This program reads a sequence of pairs of nonnegative integers
 * less than N from standard input (interpreting the pair p q to
 * mean "connect object p to object q") and prints out pair 
 * representing objects that are not yet connected. It matains an
 * array id that has an entry for each object, with the property
 * that id[p] and id[q] are equal if and only if p and q are 
 * connected.
 */

static const int N = 10;
/*
 * Ease the type of long types
 */ 
typedef std::ostream_iterator<int> output_data;
typedef std::vector<int> graph;
typedef graph::iterator v_it;

template <class T>
void display( T p, T q, const graph &id )
{
    std::cout << p << " " << q << "\t";
    std::copy( id.begin( ), id.end( ), output_data( std::cout, " " ) );
    std::cout << '\n';
}

template <class T>
class sequence : public std::iterator<std::forward_iterator_tag, T>
{
private:
    T val;
public:
    sequence(T init) : val(init) { }
    T operator *( ) { return val; }
    sequence &operator++( ) { ++val; return *this; }
    bool operator != ( const sequence &other ) { return val != other.val; }
};

template <class T>
sequence<T> gen_seq( const T &val ) 
{
    return sequence<T>( val );
}

class process_node_quick_find
{
private:
    graph &id;
public:
    process_node_quick_find( graph &id ) : id( id ) { }
    void operator( )( const std::pair<int,int> &pair )
    {
        int p = pair.first;
        int q = pair.second;
        int o = id[p];
        int n = id[q];
        /* Union Portion of Algorithm */
        if( o != n ) 
        {
            std::replace( id.begin( ), id.end( ), o, n );
        }
        display( p, q, id );
    }
};

class process_node_quick_union
{
private:
    graph &id;
public:
    process_node_quick_union( graph &id ) : id( id ) { }
    void operator( )( const std::pair<int,int> &pair )
    {
        int p = pair.first;
        int q = pair.second;
        int i,j = 0;
        /* Find */
        for( i = p; i != id[i]; i = id[i] );
        for( j = q; j != id[j]; j = id[j] );
        /* Union */
        if( i != j )
        {
            id[i] = j;
        }
        display( p, q, id );
    }
};

int main( int argc, char *argv[ ] )
{
    std::pair<int,int> data[ ] = { 
                                    std::make_pair( 3,4 ),
                                    std::make_pair( 4,9 ),
                                    std::make_pair( 8,0 ),
                                    std::make_pair( 2,3 ),
                                    std::make_pair( 5,6 ),
                                    std::make_pair( 2,9 ),
                                    std::make_pair( 5,9 ),
                                    std::make_pair( 7,3 ),
                                    std::make_pair( 4,8 ),
                                    std::make_pair( 5,6 ),
                                    std::make_pair( 0,2 ),
                                    std::make_pair( 6,1 )
                                 };
    int M = sizeof(data)/sizeof(int)/2.0;
    std::cout << "Going to insert " << M << " nodes" << std::endl;

    graph id1( gen_seq(0), gen_seq( N ) );
    display( 'p', 'q', id1 );
    std::cout << std::string( N*3, '-' ) << std::endl;
    std::for_each( &data[0], &data[M], process_node_quick_find( id1 ) );
    std::cout << std::endl;
    graph id2( gen_seq(0), gen_seq( N ) );
    display( 'p', 'q', id2 );
    std::cout << std::string( N*3, '-' ) << std::endl;
    std::for_each( &data[0], &data[M], process_node_quick_union( id2 ) );
}
share|improve this question
add comment

3 Answers

up vote 5 down vote accepted

I have a few more comments. I think you had a good idea adding typedefs to keep some of the names shorter and more meaningful, but I think I'd add even more than that.

typedef std::ostream_iterator<int> output_data;
typedef std::vector<int> graph;

// As Martin said, `typename` isn't required (or really even allowed) here.
typedef graph::iterator v_it; 
typedef std::pair<int, int> dt;

Since you have code to show p, q and id in a couple of different places, and it's important that they match up with each other, I'd move that into a little function named display or something on that order. In one place, you need to display the names p and q, and in others their values, so we want to make this a template parameterized on the types of p and q:

template <class T>
void display(T p, T q, graph const &id) { 
    std::cout << p << " " << q << "\t";
    std::copy( id.begin( ), id.end( ), output_data( std::cout, " " ) );
    std::cout << '\n';
}

For example, when we use this from main to display the initial state, we use code something like this:

display('p', 'q', id);
std::cout << std::string(N*3, '-') << "\n";

As a general rule, I prefer to create a vector already initialized, rather than creating, then filling it with data. Since filling a vector (or whatever) with a sequence of values is something that comes up all the time, I have a sequence class and gen_seq front end for exactly that purpose. It would probably be overkill to write gen_seq just for this purpose, but I think it's worth having around anyway, and when you do, you might as well use it. The header looks like this:

#ifndef GEN_SEQ_INCLUDED_
#define GEN_SEQ_INCLUDED_

template <class T>
class sequence : public std::iterator<std::forward_iterator_tag, T>
{ 
    T val;
public:
    sequence(T init) : val(init) {}
    T operator *() { return val; }
    sequence &operator++() { ++val; return *this; }
    bool operator!=(sequence const &other) { return val != other.val; }
};

template <class T>
sequence<T> gen_seq(T const &val) {
    return sequence<T>(val);
}
#endif

With this, you can create and initialize id like this: 

#include "gen_seq"

graph id(gen_seq(0), gen_seq(N));

I also keep a couple of macros around that are handy when you're initializing a vector from an array. There are templates that are (at least theoretically) better, but I've never quite gotten around to switching over to them. The macros look like this:

#define ELEMENTS_(x) (sizeof(x)/sizeof(x[0]))
#define END(array) ((array)+ELEMENTS_(array))

With these, the typedefs above, and (as sort of suggested by @Nim) using a vector instead of a queue, initializing your test data looks like this:

dt pairs[] = { 
    dt( 3,4 ), dt( 4,9 ), dt( 8,0 ), dt( 2,3 ), dt( 5,6 ), dt( 2,9 ), 
    dt( 5,9 ), dt( 7,3 ), dt( 4,8 ), dt( 5,6 ), dt( 0,2 ), dt( 6,1 )
};

std::vector<dt> data((pairs), END(pairs));

Instead of putting all the code to process the nodes into main, I'd move most of it out to a process_node function object. I'd also note that this:

       for( v_it i = id.begin( ); i < id.end( ); i++ ) 
        {
            if( *(i) == t )
            {
                *(i) = *(start+q);
            }
        }

...is essentially the same as std::replace(id.begin(), id.end(), t, *(start+q));. Taking that into account, process_node comes out looking something like this:

class process_node { 
    graph &id;
public: 
    process_node(graph &id) : id(id) {}

    void operator()(dt const &pair) { 
        int p = pair.first;
        int q = pair.second;
        int o = id[p];
        int n = id[q];
        if(o != n) 
            std::replace(id.begin(), id.end(), o, n);
        display(p, q, id);
    }
};

Since we now have a vector to iterate through, and a function object to process each item, we can switch from an explicit loop to a standard algorithm:

std::for_each(data.begin(), data.end(), process_node(id));

[...and yes, for those find that unusual, this is a noteworthy day: I actually used std::for_each -- truly a rarity. ]

That, however, brings up another point: there are still a few things about this code that don't excite me much. One, in particular, is that fact that it combines processing a node with displaying a row of results. We'd have to do a fair amount of extra work to avoid that, so I haven't bothered, but if we fixed that, std::for_each probably wouldn't be the right choice any more.

share|improve this answer
add comment
up vote 8 down vote

Looks good:

Here typename is not required:

typedef typename std::vector<int>::iterator v_it;

So this:

typedef std::vector<int>::iterator v_it;

Here I would not specify the size:

std::pair<int,int> pairs[12] = {

This is because you have to manually validate that the element count matches the size (this can cause subtle errors). So rather just let the compiler work it out:

std::pair<int,int> pairs[]   = {

Rather then specify the long winded and fully qualified type for the std::pair let the compiler deduce the type for you use std::make_pair.

std::pair<int,int> pairs[] = { 
                                std::make_pair( 3,4 ),
                                std::make_pair( 4,9 ),

I would not use an empty main branch in an if statement.

    if( t == *(start+q) ) 
    {
    }

The one thing I would note is; that even though you may be using the standard library well, you are not writing encapsulated code.

I would have written the code so that the test could have been applied to the code in the same way that real data could be applied to the code. This mean you have to define an interface to your algorithm. Think about what the inputs are (how real data and test data can be provided).

Here you just have a loop inside main(). As a result you are not really showcasing your ability to write good encapsulated code.

share|improve this answer
add comment
up vote 4 down vote

The questions I would ask are:

  1. why queue? Do you really need the push/pop functionality?
  2. It seems you are familiar with the available algorithms, but I wonder if there is something you can use to replace the for loop in your search phase?

Besides that (and Martin's fixes), I think your code is in good shape...

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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