Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Общие вопросы > Контейнер уникальных значений без operator<

Автор: borisbn 24.6.2011, 10:40

День добрый !
Есть задачка: имеется структура

Код


struct X {
    int a;
    int b;
    bool operator==( const X & that ) const {
        return this->a == that.a && this->b == that.b;
    }
};

нужно хранить в некоем контейнере такие структуры, но только уникальные.
Т.е. чтобы выполнялось условие (псевдокод)

Код

!(s[ i ] == s[ j ]), где i != j

вроде бы идеально подходит std::set, но он требует operator< для структуры, а меня это не устраивает по двум причинам:
1. Мне совершенно не важно, будут ли структуры храниться в отсортированном виде, т.к. их количество будет 20...30 и добавление в контейнер будет происходить только в начале программы. А время поиска конкретного элемента для данной задачи совершенно не критично.
2. Я не знаю как сравнить две структуры на предмет меньше ли одна или нет, т.к. оба поля в принципе равнозначны.

Смотрел на QSet (Qt), но он требует ф-цию хеша из моей структуры, а я тем более не представляю, как её сделать...

Можно, конечно, повелосипедировать: аггрегировать вектор и написать ф-цию добавления и поиска... но хочется сначала выяснить, нет ли готового решения

Спасибо.

P.S. boost просьба не предлагать соответствующего coder'а прошу не обижаться smile

Автор: rudvil 24.6.2011, 10:47

Цитата(borisbn @ 24.6.2011, 10:40

)

но хочется сначала выяснить, нет ли готового решения

Если есть поддержка C++0x

Код

#include <unordered_set>

Автор: Sahab 24.6.2011, 10:49

Цитата(rudvil @ 24.6.2011, 10:47

)

unordered_set

а для него хеш не нужно реализовывать? smile

Автор: rudvil 24.6.2011, 10:55

Цитата(Sahab @ 24.6.2011, 10:49)

Цитата(rudvil @ 24.6.2011, 10:47

)

unordered_set

а для него хеш не нужно реализовывать? smile

Точно... это же не POD.
Спасибо за поправку.

Автор: Sahab 24.6.2011, 10:56

мне только непонятно... если

Цитата

Мне совершенно не важно, будут ли структуры храниться в отсортированном виде

то чем не подходит?

Код


    bool operator < ( const X & that ) const {
       return this->a < that.a && this->b < that.b;
    }

Автор: RastaDja 24.6.2011, 11:06

Цитата(Sahab @ 24.6.2011, 11:56

)

то чем не подходит?
код C++
    bool operator < ( const X & that ) const {
       return this->a < that.a && this->b < that.b;
    }

потому что a и b - несут независимую информацию
например а - масса, b - высота
какой объект больше? - тот что тяжелее, или выше?

Автор: borisbn 24.6.2011, 11:20

Цитата(Sahab @ 24.6.2011, 10:56

)

то чем не подходит?
bool operator < ( const X & that ) const {
return this->a < that.a && this->b < that.b;
}

в принципе, я уже дошёл до этого, но, т.к. мне действительно не важно, то можно и return true сделать...
то, что можно так заюзать set - я уже понял (мало того, уже сделал), но хотелось бы выяснить не будет ли это overhead'ом? Нет ли стандартного (специально обученного, заточенного) решения для этой задачи.

Автор: azesmcar 24.6.2011, 12:58

Цитата(borisbn @ 24.6.2011, 11:20

)

то можно и return true сделать

ни в коем случае.

Цитата

For all algorithms that take Compare, there is a version that uses operator< instead. That is, comp(*i, *j) != false defaults to *i < *j != false.
For the algorithms to work correctly, comp has to induce a strict weak ordering on the values. The term strict refers to the requirement of an irreflexive relation (!comp(x, x) for all x), and the term
weak to requirements that are not as strong as those for a total ordering, but stronger than those for a partial ordering. If we define equiv(a, b) as !comp(a, b) && !comp(b, a), then the requirements
are that comp and equiv both be transitive relations:

— comp(a, b) && comp(b, c) implies comp(a, c)

Автор: borisbn 24.6.2011, 13:11

azesmcar, спасибо. Я правильно понял, что return true нельзя, т.к. set (ну или там алгоритмы поиска - не важно) может вместо operator== создать собственный

Цитата

equiv(a, b) as !comp(a, b) && !comp(b, a)

и тогда он просто не найдёт нужный мне элемент, а при return false будет всегда находить первый ?

Что тогда посоветуете ?

P.S. Откуда цитата ?

Автор: Earnest 24.6.2011, 14:03

Цитата

bool operator < ( const X & that ) const {
return this->a < that.a && this->b < that.b;
}

Это неправильно, нужно так:

Код


 if this->a == that.a return this->b < that.b;
 else return this->a < that.a;

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

Есть много случаев, когда упорядочивание нужно чисто для хранения.
Логический смысл тогда не важен, главное, чтобы упорядочивание было однозначным и непротиворечивым.
Если POD, как у тебя, и не содержит double, тогда я не парюсь, а просто использую memcmp. Условие, которое привел
azesmcar, автоматически выполняется. Кстати, можно тогда не писать свой == (потому что он уже есть - !< && !>).

Кстати, если определить свою структуру через std::pair (вместо именованных членов), то оператор сравнения генерируется автоматически, именно как я написала. Естественно, если сравнение для членов не определено, возникают проблемы...
Другое дело, если стандартный оператор < не подходит, как например для даблов...

Для засовывания в хэш-контейнеры таких структур (из 2 чисел, можно и double) использую комбинацию с простыми числами, типа

Код


    static size_t Hash (const POINT& pt) 
    { 
        return (__int64)pt.x * 2531011 + (__int64)pt.y * 214013;
    }

Могут быть и другие числа (не помню уже откуда, давно содрала и с тех пор счастливо использую); разбрасывает замечательно, даже если точки близки.
Но только имей в виду, что хэш обычно жрет памяти побольше, чем просто map\set. Если это важно.

Автор: borisbn 24.6.2011, 14:12

Earnest, я для примера вривёл 2 поля. На самом деле у меня их 6. Представляешь, что за монстр получится в операторе < ?

Цитата(Earnest @ 24.6.2011, 14:03

)

Кстати, можно тогда не писать свой ==

не то, чтобы можно, а бессмысленно, т.к., судя по всему, std::set использует только меньше. Говорю это потому, что определил только оператор меньше, и у меня всё скомпилялось и добавление и поиск...

Автор: Sahab 24.6.2011, 14:19

Цитата

какой объект больше? - тот что тяжелее, или выше?

это и ежу понятно...
но в данном контексте это было не важно

Автор: borisbn 24.6.2011, 14:23

Цитата(Sahab @ 24.6.2011, 14:19

)

но в данном контексте это было не важно

важно
Sahab,

Цитата(Sahab @ 24.6.2011, 10:56

)

то чем не подходит?
bool operator < ( const X & that ) const {
return this->a < that.a && this->b < that.b;
}

тем, что если a1 < a2, а b1 > b2, то обе структуры будут считаться больше другой. Может и зацикливание произойти.

Автор: Earnest 24.6.2011, 14:30

Цитата(borisbn @ 24.6.2011, 15:12

)

что определил только оператор меньше, и у меня всё скомпилялось и добавление и поиск...

Скомпилировалось - не значит правильно работает. Чего бы не скомпилироваться, если формальный синтаксис соблюден.
Еще раз, приведенный в самом начале оператор < - неправильный, потому что не транзитивный. Можешь нарваться не сразу, и будешь долго ломать голову, откуда лажа.
Грубо говоря, даже уникальность хранения может нарушаться при таком операторе: все зависит от того, в каком состоянии будет дерево и по какому пути пойдет сравнение.
Если членов много, и это POD, можно использовать memcmp, как я писала.

Цитата(borisbn @ 24.6.2011, 15:12

)

не то, чтобы можно, а бессмысленно, т.к., судя по всему, std::set использует только меньше.

set действительно использует только "меньше". Я имела в виду, что может сравнение на равенство нужно тебе зачем-то еще.

Цитата(borisbn @ 24.6.2011, 15:12

)

Представляешь, что за монстр получится в операторе <

Да не намного страшнее, чем оператор проверки равенства - принцип тот же, упорядочиваешь по первой, если она равна - по второй и т.д.
Только удобнее записать немного по-другому:

Код


if first != rhs.first return first < rhs.first
else if second != rhs.second return second < rhs.second
и т.д.

Ну или хэш-контейнеры использовать.

Автор: borisbn 24.6.2011, 14:32

Цитата(Earnest @ 24.6.2011, 14:03

)

тогда я не парюсь, а просто использую memcmp

хммммм. а ведь идея:

Код


bool operator < ( const X & that ) const {
    int a_this[ 6 ];
    a_this[ 0 ] = this->field1;
    ...
    a_this[ 5 ] = this->field6;
    int a_that[ 6 ];
    a_that[ 0 ] = that.field1;
    ...
    a_that[ 5 ] = that.field6;
    return memcmp( a_this, a_that, sizeof( a_this ) ) < 0;
}

Добавлено через 9 минут и 19 секунд

Цитата(Earnest @ 24.6.2011, 14:30

)

это то понятно (чай не первый раз замужем). под "скомпилировалось" я имел в виду, что std::set больше ничего не требует. и не более того.

Цитата(Earnest @ 24.6.2011, 14:30

)

Я имела в виду, что может сравнение на равенство нужно тебе зачем-то еще.

теперь ясно. нет. не нужен.

Цитата(Earnest @ 24.6.2011, 14:30

)

Ну или хэш-контейнеры использовать.

тогда такой вопрос:

Цитата(borisbn @ 24.6.2011, 10:40

)

Смотрел на QSet (Qt), но он требует ф-цию хеша из моей структуры, а я тем более не представляю, как её сделать...

Автор: Earnest 24.6.2011, 14:43

А зачем что-то копировать?
Просто memcmp (this, &that, sizeof (*this)); вполне достаточно.
Если у тебя там есть не POD члены или даблы или указатели или виртуальные функции (ну, последнее вроде не должно мешать, но я обычно все равно делю), то нужно отделить суп от мух: т.е. сделать POD-структуру с простыми полями, которую включить в класс (или унаследоваться). Это по-любому не вредно для дизайна - отделять простые POD-структуры от сложных

Автор: borisbn 24.6.2011, 14:53

Цитата(Earnest @ 24.6.2011, 14:43

)

Просто memcmp (this, &that, sizeof (*this)); вполне достаточно

как справедливо заметил volatile в http://forum.vingrad.ru/index.php?showtopic=332359&view=findpost&p=2363970 из-за мусора при выравнивании такое лучше не использовать. Мало того, мне не по всем полям сравнивать надо.

Цитата(Earnest @ 24.6.2011, 14:43

)

Если у тебя там есть не POD члены

есть (QString), но ради оператора < дробить структуру на две (типа базовая cо сравниваемыми POD'ами и наследник с QString'ом и доп.полями)... ну, может и имеет смысл, но как-то слишком замысловато IMHO

Автор: azesmcar 24.6.2011, 14:54

Цитата(borisbn @ 24.6.2011, 13:11

)

P.S. Откуда цитата ?

из стандарта.

Цитата(borisbn @ 24.6.2011, 13:11

)

Что тогда посоветуете ?

согласен с Earnest по поводу хэш контейнеров.

Автор: Earnest 24.6.2011, 14:56

Цитата(borisbn @ 24.6.2011, 15:32

)

а я тем более не представляю, как её сделать...

Ну, один пример (для 2 чисел) я тебе привела. Можно и развить.

Или так: здесь key - это указатель на строку, идем до ее конца, для массива интов сам напишешь.

Код


       nHash = 0;
       while (*key)
        nHash = (nHash<<5) + nHash + *key++;

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

Добавлено через 3 минуты и 27 секунд

Цитата(borisbn @ 24.6.2011, 15:53

)

из-за мусора при выравнивании такое лучше не использовать

Да, верно, просто я у тебя только инты видела... видимо, для примера упростил. Кроме того, я обычно POD-структурам делаю базовую инициализацию (ZeroMemory), а уже потом поля пихаю. И никакого мусора.

Добавлено через 5 минут и 48 секунд

Цитата(borisbn @ 24.6.2011, 15:53

)

ну, может и имеет смысл, но как-то слишком замысловато IMHO

Ну хотя бы подряд ты их расположить можешь? Т.е. стринг либо сзаду, либо спереду, и сравнивать блок. Есть ведь оператор получения офсета мембера - что-то вроде offsetof.

Автор: borisbn 24.6.2011, 15:12

Цитата(azesmcar @ 24.6.2011, 14:54

)

из стандарта.

упс. до 25.3 Sorting and related operations как-то не добрался. остановился на std::set и find

Цитата(Earnest @ 24.6.2011, 14:56

)

На самом деле, в качестве хэша можно возвращать любое целое число - хоть константу, работать будет (но медленно: свалит все в одну корзину)

хммм... будет работать ??? тогда буду пробовать. да мне быстро и не надо.

Цитата(azesmcar @ 24.6.2011, 14:54

)

согласен с Earnest по поводу хэш контейнеров.

уговорили

спасибо ещё раз всем

тему пока не закрываю - проверю всё - отпишусь.

Автор: azesmcar 24.6.2011, 15:14

Цитата(borisbn @ 24.6.2011, 15:12

)

хммм... будет работать ??? тогда буду пробовать. да мне быстро и не надо.

будет

только сложность будет линейной.

Автор: Earnest 24.6.2011, 15:18

Цитата(borisbn @ 24.6.2011, 16:12

)

будет работать ???

Это только теоретически. А как реализован конкретный контейнер - хз, может и чего-нибудь выкинуть, а я потом виновата буду.
Кроме того, это эквивалентно линейному списку без всякого упорядочивания - т.е. линейный поиск. Для этого дела хэш-контейнер и заводить не стоит.
Короче, это была шутка. smile

И я ведь привела тебе пример, как хэш строить.

Автор: borisbn 24.6.2011, 15:50

ну, что ж, уподобимся янки - ВАУ, Работает ! smile

Код


struct X {
...
    int a;
    int b;
...
    bool operator==( const X & that ) const {
        return this->a == that.a && this->b == that.b;
    }
};
inline uint qHash( const X & ) { return 42; }
typedef QSet< X > XSet;
XSet m_xs;

...

X x1( 1, 2 );
m_xs.insert( x1 );
x1.b = 3;
m_xs.insert( x1 );
XSet::const_iterator found = m_xs.find( X( 1, 2 ) ); // != .end()
bool isIn = m_xs.contains( X( 1, 3 ) ); // true
isIn = m_xs.contains( X( 1, 1 ) ); // false

Автор: borisbn 24.6.2011, 16:12

Цитата(Earnest @ 24.6.2011, 15:18

)

Кроме того, это эквивалентно линейному списку без всякого упорядочивания - т.е. линейный поиск. Для этого дела хэш-контейнер и заводить не стоит.

я уже говорил, что скорость мне не важна, и можно и руками сделать, но

Цитата(borisbn @ 24.6.2011, 10:40

)

Можно, конечно, повелосипедировать: аггрегировать вектор и написать ф-цию добавления и поиска... но хочется сначала выяснить, нет ли готового решения

в принципе hash за небольшим оверхедом - и есть такое решение. исчо раз спасибо.

Цитата(Earnest @ 24.6.2011, 15:18

)

А как реализован конкретный контейнер - хз, может и чего-нибудь выкинуть, а я потом виновата буду.

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

Я тут подумал - даже теоретически не важно, как реализован контейнер (главное, чтоб без ошибок), т.к. ведь может такое случиться, что ключи у двух разных структур пересекутся.... А где у двух, там и у трёх, четырёх ---> у всех smile

Та не, должна работать константа. Тем более такая, как 42 smile

Автор: Earnest 24.6.2011, 16:20

Не, я так не могу... это же вопиющее нарушение мировой гармонии! Даже если 42!
Вот зачем я тебе про константу сказала! Количество мирового зла в виде кривого кода возросло, а тепловая смерть вселенной и так не за горами... Надеюсь, ты просто попробовал, а делать будешь нормально...

Автор: borisbn 24.6.2011, 16:22

Цитата(Earnest @ 24.6.2011, 15:18

)

И я ведь привела тебе пример, как хэш строить.

спасибо. В какой-нить другой задаче обязательно воспользуюсь. В данной конкретной у меня будут 20..30 (ну может 50) уникальных структур. А поиск будет инициироваться по кнопке. СтОит ли заморачиваться ?

Автор: azesmcar 24.6.2011, 16:24

Цитата(borisbn @ 24.6.2011, 16:22

)

ну заведи вектор тогда, зачем использовать хэш контейнер не по назначению? smile

Автор: borisbn 24.6.2011, 16:47

Цитата(azesmcar @ 24.6.2011, 16:24

)

ну заведи вектор тогда, зачем использовать хэш контейнер не по назначению?

Над ним обёртки нужны. Не то, чтобы лень писать (делов то - полчаса с отладкой, да и, возможно, так и сделаю в итоге), просто хотелось узнать нет ли решения, которое идеально мне подходит. Убедился, что нет. Тоже результат smile

Цитата(borisbn @ 24.6.2011, 10:40

)

Автор: borisbn 25.6.2011, 08:33

Цитата(azesmcar @ 24.6.2011, 16:24

)

ну заведи вектор тогда, зачем использовать хэш контейнер не по назначению?

всё-таки решил повелосипедировать, т.к. готового решения конкретно этой задачи нет...
вот что получилось

Код


#include <vector>
#include <algorithm>
#include <functional>

template< class T, class Compare = std::equal_to< T > >
class UniqueContainer
{
private:
    typedef std::vector< T > container_t;
public:
    typedef typename container_t::const_iterator const_iterator;
    typedef typename container_t::iterator iterator;

    bool contains( const T & value ) const {
        return std::find_if( m_container.begin(),
                             m_container.end(),
                             std::bind1st( m_compare, value )
                           ) != m_container.end();
    }

    bool push_back( const T & value ) {
        if ( contains( value ) ) {
            return false;
        }
        m_container.push_back( value );
        return true;
    }
    const_iterator begin() const {
        return m_container.begin();
    }
    iterator begin() {
        return m_container.begin();
    }
    const_iterator end() const {
        return m_container.end();
    }
    iterator end() {
        return m_container.end();
    }
    
private:
    container_t m_container;
    Compare m_compare;
};

//---------------------------------------

struct S {
    int a;
    int b;
    S( int a_a = 0, int a_b = 0 )
        : a( a_a ), b( a_b )
    {
    }
    bool operator==( const S & that ) const {
        return this->a == that.a && this->b == that.b;
    }
};

#include <iostream>
int main() {
    typedef UniqueContainer< S > Container;
    Container v;
    v.push_back( S( 1, 1 ) );
    v.push_back( S( 2, 2 ) );
    v.push_back( S( 1, 1 ) );
    
    for ( Container::const_iterator it = v.begin(); it != v.end(); ++it ) {
        std::cout << (*it).a << " " << (*it).b << std::endl;
    }
}

http://liveworkspace.org/code/33a67804f759aa6f3f03796f9ec3c230

Автор: mes 25.6.2011, 10:47

Цитата(borisbn @ 25.6.2011, 07:33

)

вот что получилось

и охота же было из за одной функции писать целую обертку.. smile

вот что значит _поклоняться_ классам, думая что соблюдаете ООП...

Автор: azesmcar 25.6.2011, 10:57

Цитата(mes @ 25.6.2011, 10:47

)

и охота же было из за одной функции писать целую обертку..

да уж, зачем это надо? почему бы просто не проверять существование элемента при вставке?