Выбор контейнера/алгоритма - C/C++

Имеется набор элементов. На нем определена операция сравнения, но довольно бедная: не "<" и ">", а только "==" и "!=". Одна задача: разбить этот набор на классы эквивалетнтости. Вторая — от каждого класса оставить только по одному элементу. Получается, что мне нужно что-то вроде std::multiset (для первой задачи) и std::set (для второй) на множестве, в котором не задан порядок. В STL таких контейнеров нет. Может вам известны библиотеки, реализующую данную функциональность?
Спасибо.

Здравствуйте, pasenger, Вы писали:

P>Имеется набор элементов. На нем определена операция сравнения, но довольно бедная: не "<" и ">", а только "==" и "!=". Одна задача: разбить этот набор на классы эквивалетнтости. Вторая — от каждого класса оставить только по одному элементу. Получается, что мне нужно что-то вроде std::multiset (для первой задачи) и std::set (для второй) на множестве, в котором не задан порядок. В STL таких контейнеров нет. Может вам известны библиотеки, реализующую данную функциональность?
P>Спасибо.

Если оператор == производит сравнение на принадлежность к тому или иному классу, то задача может быть решена за O(NxC), где N число объектов, а С — число классов, причем в результирующее "множество" попадут первые попавшие представители класса:

    std::vector<object> source;
    std::vector<object> result;

    for(std::vector<object>::const_iterator is = source.begin(), es = source.end(); is!=es; is++) 
    {
        bool found = false;
        for(std::vector<object>::iterator ir = result.begin(), er=result.end(); ir!=er; ir++)
            if( (found = *is == *ir) )
                break;
        if( !found )
            result.push_back(*is);

    }

Здравствуйте, Анатолий Широков, Вы писали:

АШ>

АШ>    std::vector<object> source;
АШ>    std::vector<object> result;

АШ>    for(std::vector<object>::const_iterator is = source.begin(), es = source.end(); is!=es; is++) 
АШ>    {
АШ>        bool found = false;
АШ>        for(std::vector<object>::iterator ir = result.begin(), er=result.end(); ir!=er; ir++)
АШ>            if( (found = *is == *ir) )
АШ>                break;
АШ>        if( !found )
АШ>            result.push_back(*is);

АШ>    }
АШ>

Вот к чему приводит боязнь goto…

Хотя здесь можно обойтись и без goto, и без флага:

for(Container::const_iterator i = source.begin(); i != source.end(); ++i)
{
    if(std::find(result.begin(), result.end(), *i) == result.end())
    {
        result.push_back(*i);
    }
}

Кстати, странно, что в STL нет find_first_not_of.

RO>Вот к чему приводит боязнь goto…

А по существу дела у вас есть что сказать?

Здравствуйте, Roman Odaisky, Вы писали:

RO>

RO>for(Container::const_iterator i = source.begin(); i != source.end(); ++i)
RO>{
RO>    if(std::find(result.begin(), result.end(), *i) == result.end())
RO>    {
RO>        result.push_back(*i);
RO>    }
RO>}
RO>

RO>Кстати, странно, что в STL нет find_first_not_of.

А вы не знаете, буст мне здесь чем-нибудь может помочь?

Здравствуйте, Roman Odaisky, Вы писали:

RO>Кстати, странно, что в STL нет find_first_not_of.
find_first_of + std::not?

Здравствуйте, Анатолий Широков, Вы писали:

АШ>Если оператор == производит сравнение на принадлежность к тому или иному классу, то задача может быть решена за O(NxC), где N число объектов, а С — число классов, причем в результирующее "множество" попадут первые попавшие представители класса:

<skiped />

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

Здравствуйте, Анатолий Широков, Вы писали:

АШ>

АШ>    std::vector<object> source;
АШ>    std::vector<object> result;

АШ>    for(std::vector<object>::const_iterator is = source.begin(), es = source.end(); is!=es; is++) 
АШ>    {
АШ>        bool found = false;
АШ>        for(std::vector<object>::iterator ir = result.begin(), er=result.end(); ir!=er; ir++)
АШ>            if( (found = *is == *ir) )
АШ>                break;
АШ>        if( !found )
АШ>            result.push_back(*is);

АШ>    }
АШ>

а без found не лучше?

        if( ir==er )
            result.push_back(*is);

Здравствуйте, pasenger, Вы писали:

P>Имеется набор элементов.
А можно ли определить хеш-функцию?
Если до то тогда можно использовать хеш-таблицы что будет гораздо быстрее тупого перебора.
Они хоть еще и не попали в тандарт но есть во многих реализациях STL.
См hash_set, hash_multiset, hash_map, hash_multimap.

... << RSDN@Home 1.2.0 alpha rev. 745>>

Здравствуйте, Анатолий Широков, Вы писали:

RO>>Вот к чему приводит боязнь goto…
АШ>А по существу дела у вас есть что сказать?

По существу я вообще-то привел свой вариант реализации алгоритма, более оптимальный.

std::vector<object> source;
std::vector<object> result;

struct helper
{
    std::vector<object> tmp;
    bool operator()(const object& obj)
    {
        if (std::find(tmp.begin(), tmp.end(), obj) == tmp.end())
        {
            tmp.push_back(obj);
            return false; // не помню, вроде, нужна инверсия предиката
        }
        return true;
    }
};

helper heper_obj;
std::remove_copy_if(source.begin(), source.end(), std::back_inserter(result), heper_obj);

... << RSDN@Home 1.1.4 stable SR1 rev. 568>>

Здравствуйте, Аноним, Вы писали:

RO>>Кстати, странно, что в STL нет find_first_not_of.
А>find_first_of + std::not?

std::not2(std::equal_to<X>()) не является предикатом эквивалентности.

Здравствуйте, Roman Odaisky, Вы писали:

RO>Здравствуйте, Анатолий Широков, Вы писали:

RO>>>Вот к чему приводит боязнь goto…
АШ>>А по существу дела у вас есть что сказать?

RO>По существу я вообще-то привел свой вариант реализации алгоритма, более оптимальный.

Вы привели более кратную реализацию алгоритма, возможно, но оптимальную ли?

P>>Имеется набор элементов.
WH>А можно ли определить хеш-функцию?
Или хотя бы оператор <. Попробуй посмотреть на реализацию operator== у айтема, может возникнут какие-то идеи. Без оператора < в худшем случае разбиение на классы эквивалентности будет O(N^2) (если в каждом классе всего по одному элементу). С оператором < сможешь использовать std::multiset, и будешь иметь сложность O(N*logN).

... << RSDN@Home 1.2.0 alpha rev. 717>>

Здравствуйте, WolfHound, Вы писали:

WH>Здравствуйте, pasenger, Вы писали:

P>>Имеется набор элементов.
WH>А можно ли определить хеш-функцию?
WH>Если до то тогда можно использовать хеш-таблицы что будет гораздо быстрее тупого перебора.
WH>Они хоть еще и не попали в тандарт но есть во многих реализациях STL.
WH>См hash_set, hash_multiset, hash_map, hash_multimap.

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

Здравствуйте, Анатолий Широков, Вы писали:

WH>>А можно ли определить хеш-функцию?
WH>>Если до то тогда можно использовать хеш-таблицы что будет гораздо быстрее тупого перебора.
WH>>Они хоть еще и не попали в тандарт но есть во многих реализациях STL.
WH>>См hash_set, hash_multiset, hash_map, hash_multimap.

АШ>Хеш-функция это частность. Более общая постановка вопроса сводится к следующему: можно ли изменить интерфейс объекта так, чтобы каждый объект сообщал о классе, к которому он принадлежит. В этом случае, можно было построить и хеш-функцию и оператор < и пр.

К сожалению, это всё COM: и элементы, и оператор "==" (ф-я equal, если точнее)

Здравствуйте, frogkiller, Вы писали:

F>

F>std::vector<object> source;
F>std::vector<object> result;

F>struct helper
F>{
F>    std::vector<object> tmp;
F>    bool operator()(const object& obj)
F>    {
F>        if (std::find(tmp.begin(), tmp.end(), obj) == tmp.end())
F>        {
F>            tmp.push_back(obj);
F>            return false; // не помню, вроде, нужна инверсия предиката
F>        }
F>        return true;
F>    }
F>};

F>helper heper_obj;
F>std::remove_copy_if(source.begin(), source.end(), std::back_inserter(result), heper_obj);
F>

Спасибо, что в этом роде сделаю.

> Или хотя бы оператор <. Попробуй посмотреть на реализацию operator== у айтема, может возникнут какие-то идеи. Без оператора < в худшем случае разбиение на классы эквивалентности будет O(N^2) (если в каждом классе всего по одному элементу). С оператором < сможешь использовать std::multiset, и будешь иметь сложность O(N*logN).

Если я ничего не перепутал, то O(N*logN) у сета/мультисета получается только в среднем, в худшем случае будет тоже O(N^2).

Posted via RSDN NNTP Server 2.1 beta

Здравствуйте, Sergey, Вы писали:

>> Или хотя бы оператор <. Попробуй посмотреть на реализацию operator== у айтема, может возникнут какие-то идеи. Без оператора < в худшем случае разбиение на классы эквивалентности будет O(N^2) (если в каждом классе всего по одному элементу). С оператором < сможешь использовать std::multiset, и будешь иметь сложность O(N*logN).

S>Если я ничего не перепутал, то O(N*logN) у сета/мультисета получается только в среднем, в худшем случае будет тоже O(N^2).

Перепутал.

>> Или хотя бы оператор <. Попробуй посмотреть на реализацию operator== у айтема, может возникнут какие-то идеи. Без оператора < в худшем случае разбиение на классы эквивалентности будет O(N^2) (если в каждом классе всего по одному элементу). С оператором < сможешь использовать std::multiset, и будешь иметь сложность O(N*logN).

S>Если я ничего не перепутал, то O(N*logN) у сета/мультисета получается только в среднем, в худшем случае будет тоже O(N^2).
В set-multiset поиск имеет логарифмическую сложность всегда. Поэтому квадрата не получится в любом случае. Получится O(N*logN) в хужшем случае (в каждом классе всего по одному элементу) и O(N) в лучшем (все элементы принадлежат одному классу).

... << RSDN@Home 1.2.0 alpha rev. 717>>

	От:	pasenger
	Дата:	08.10.07 05:28
	Оценка:

	От:	Анатолий Широков
	Дата:	08.10.07 06:06
	Оценка:	1 (1)

	От:	Roman Odaisky
	Дата:	08.10.07 08:01
	Оценка:

	От:	Анатолий Широков
	Дата:	08.10.07 08:14
	Оценка:

	От:	pasenger
	Дата:	08.10.07 09:12
	Оценка:

	От:	frogkiller
	Дата:	08.10.07 14:37
	Оценка:	29 (2)

	От:	Sergey
	Дата:	09.10.07 10:25
	Оценка:

	От:	Left2
	Дата:	09.10.07 10:48
	Оценка: