Напечатать пары, представляющие объекты из последовательности неотрицательных целых пар


Есть некоторые вещи, которые я не уверен, с профессиональной точки зрения про "правильный" способ, чтобы написать код на C++. Я искал через исходный код различных проектов с открытым исходным кодом, а также других код размещен здесь и на переполнение стека.

Так что давайте просто оставить его на это. Скажем, я опрашиваю компании по телефону. Не белой доске. Они просят меня написать код ниже и поверните ее по часовой. Это гипотетическая ситуация, но параллели, как большинство "больших" компаний в настоящее время интервьюирования. Бы этот код "дайте мне работу"? Если нет, то что бы вы изменили, или что вы можете тренировать меня, чтобы я смогла получить работу по программированию?

#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( );
    }
}

Вывод и аргументы в GCC будет выглядеть так:

[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


Комментарии
3 ответа

У меня есть несколько замечаний. Я думаю, что это была хорошая идея добавления типов, чтобы сохранить некоторые имена короче и содержательнее, но я думаю добавить еще больше.

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;

Поскольку у вас есть код, чтобы показать, П, Щ и код в несколько разных мест, и это важно, что они совпадают друг с другом, я бы переместить, что в немного функцию дисплея или что-то в этом роде. В одном месте, вам нужно, чтобы отобразить имена П И М, а в других их ценностей, поэтому мы хотим сделать этот шаблон параметризованные по типам р и М:

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';
}

Например, когда мы используем эти из основных для отображения начального состояния, мы используем код что-то вроде этого:

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

Как правило, я предпочитаю создать вектор уже инициализирована, а не к созданию, а затем заполнять ее данными. После заполнения вектора (или любой другой) с последовательностью значений это то, что постоянно приходит на ум, у меня есть последовательность класса и gen_seq переднего плана именно для этой цели. Наверное, будет излишним писать gen_seq только для этой цели, но я думаю, что это стоит того, все равно, и когда вы это сделаете, вы могли бы также использовать его. Заголовок выглядит так:

#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

При этом, вы можете создать и инициализировать код такой:

#include "gen_seq"

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

Я также держу пару макросов вокруг, что удобно, когда вы инициализировать вектор из массива. Есть шаблоны, которые (хотя бы теоретически) лучше, но я никогда не получил вокруг, чтобы переключаться на них. Макросы выглядят так:

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

С их помощью оператора typedefс выше, и (как предложил @ЧПМ) использовать вектор вместо очереди, инициализация тестовых данных выглядит так:

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));

Вместо того, чтобы поместить весь код для обработки узлов в главном, я бы поместить его на process_node функции объекта. Я также отмечу, что это:

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

...по сути такой же, как СТД::заменить(ИД.начать(), идентификатор.конец(), Т *(старт+Щ));. С учетом этого, process_node выглядит примерно так:

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);
}
};

Поскольку теперь у нас есть вектор для перебора, и объект функции для обработки каждого элемента, мы можем перейти от явного цикла в стандартный алгоритм:

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

[...и да, для тех, Это кажется необычным, это важный день: я на самом деле использовать с std::for_each -- действительно редкость. ]

Что, впрочем, еще один момент: есть еще несколько вещей об этом коде, что не сильно меня волнуют. Один, в частности, является тот факт, что она сочетает обработку узла с отображением строки результатов. Мы должны сделать изрядное количество дополнительной работы, чтобы избежать этого, поэтому я не заморачивался, но если мы это исправили, и std::for_each , вероятно, не быть правильным выбором больше.

5
ответ дан 19 августа 2011 в 04:08 Источник Поделиться

Выглядит хорошо:

Здесь typename не требуется:

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

Так это:

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

Вот я бы не укажите размер:

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

Это потому, что вы должны вручную проверить, что количество элементов соответствует размеру (это может привести к тонким ошибкам). Так что лучше просто позволить компилятору получается:

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

А затем укажите занудный и полностью определенного типа для класса std::пара пусть компилятор вывести тип для вас использовать std::например, make_pair.

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

Я бы не использовать пустую главную ветвь в операторе if.

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

Одна вещь, я хотел бы отметить, что даже если вы можете быть с использованием стандартной библиотеки, вы не пишете инкапсулированный код.

Я бы написал этот код так, чтобы тест можно было бы применить к код таким же образом, что реальные данные могут быть применены к коду. Это означает, что вы должны определить интерфейс для вашего алгоритма. Подумайте о том, что входные данные (как реальные данные и проверить данные могут быть предоставлены).

Здесь вы просто петли внутри main(). В результате вы не демонстрируете свои способности писать хорошие инкапсулированный код.

8
ответ дан 19 августа 2011 в 08:08 Источник Поделиться

Вопросы, которые я хотел задать:


  1. почему очереди? Вы действительно нуждаетесь в пуш/поп - функциональность?

  2. Кажется, вы знакомы с алгоритмами, но я интересно, если есть что-то, вы можете использовать, чтобы заменить цикл for в стадии поиска?

Кроме того (и исправления Мартина), я думаю, что ваш код находится в хорошей форме...

4
ответ дан 19 августа 2011 в 08:08 Источник Поделиться