C ++ STL "Ассоциация Сет / Карта" - PullRequest
Новая
       42

C ++ STL "Ассоциация Сет / Карта"

2 голосов
/ 06 февраля 2012

Я ищу имя определенного вида набора / карты, для которого, как мы надеемся, существует какой-то существующий код, такой как C ++ STL.

Вызов набора A.

Я хотел бы выполнить следующие команды: 

A.associate(3,5)
A.associate(3,6)
A.associate(6,8)
A.associate(8,10)
A.associate(4,9)

И затем иметь возможность задавать следующие вопросы, получая указанные ответы: 

A.is_associated(3,5)  -> True
A.is_associated(5,10) -> True
A.is_associated(10,3) -> True
A.is_associated(4,10) -> False

Знаете ли вы имятакого типа конструкции / набора?

Знаете ли вы, существует ли реализация C / C ++?

Ответы [ 2 ]

8 голосов
/ 06 февраля 2012

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

На основании некоторых пояснений в комментариях: операция is_associated() - это поиск пути в неориентированном графе. В зависимости от потребности графа можно добавить ребро для представления структуры данных таким образом, чтобы is_associated() было постоянным временем за счет стоимости вставки, оценивающей линейное время.

3 голосов
/ 06 февраля 2012

Редактировать: Если вы хотите сделать дополнительный шаг, вам следует подумать об эффективной реализации Несвязанное множество Union-Find .

К сожалению, единственный разумный способ, который я вижу, это сделать std::map более std::sets - вам нужно каждый раз при вставке проверять, находятся ли два элемента в разных подмножествах - если это так, вы объединяете их.

Таким образом, внешний набор хранит все элементы и указывает их на наборы, к которым они принадлежат.

Теперь, если вы добавите новую ассоциацию:

  1. проверка, к каким наборам относятся A и B
  2. если ни один из них не принадлежит ни одному из наборов, создайте новый набор и сопоставьте оба значения этому набору (конец)
  3. если один принадлежит набору, а другой нет, поместите другой в первый набор и отобразите его там (конец)
  4. если оба принадлежат разным наборам, объедините наборы и соответственно обновите сопоставления элементов.

Теперь функция is_associated очень быстрая - просто проверьте, принадлежат ли два элемента одному и тому же набору.

На английском: 

typedef std::map< int, std::set< int >& > assoc_set; // note that you need to 
                 // store the sets somewhere else, maybe in another set

Что-то вроде этого: 

class assoc_set
{
    typedef std::set< int > int_set;
    typedef std::set< int_set > int_set_set;
    typedef std::map< int, int_set_set::iterator > set_map;
public:
    void associate( int a, int b )
    {
        set_set_map::iterator ia = iss.find( a );
        set_set_map::iterator ib = iss.find( b );
        if ( ia == set_set_map::end() )
        {
            if ( ib == set_set_map::end() )
            {
                // create new
                int_set ab;
                ab.insert(a);
                ab.insert(b);
                int_set_set::iterator r = iss.insert( ab ).second;
                smap[a] = r;
                smap[b] = r;
            }
            else
            {
                // add to a
                smap[a] = ib;
                ib->insert( a );
            }
        }
        else
        {
            if ( ib == set_set_map::end() )
            {
                // add to b
                smap[b] = ia;
                ia->insert( b );
            }
            else
            {
                // merge
                ia->insert( ib->begin(), ib->end() );
                // this could be done better
                for ( int_set::iterator i = it->begin(); i != it->end(); ++i )
                {
                    smap[*i] = ia;
                }

            }

        }


    }

    bool is_associated( int a, int b )
    {
        set_set_map::iterator ia = iss.find( a );
        set_set_map::iterator ib = iss.find( b );

        return ia != set_set_map::end() && ia = ib;
    }

private:
    int_set_set iss;
    set_map smap;
}

Будут ошибки и ошибки, у меня есть только блокнот (и я все равно потратил слишком много времени на это).

Добавление составляет O(n) (но может быть уменьшено до O(log(n)) путем использования дополнительного уровня косвенности (и избавления от глупого цикла карты). Запрос - O(log(n)).

Используя unordered_set/unordered_map, вы можете уменьшить оба значения до O(1).

...