set c language

Discussion in 'LANGS.C' started by srm, Jul 26, 2011.

  1. srm

    srm New Member

    Blog Posts:
    0
    Joined:
    Jun 14, 2011
    Messages:
    189
    Здравствуйте. Есть ли стандартные библиотеки для работы с множествами в С (не в С++)?
     
  2. qqwe

    qqwe New Member

    Blog Posts:
    0
    Joined:
    Jan 2, 2009
    Messages:
    2,914
    что тут есть "множества"?
     
  3. srm

    srm New Member

    Blog Posts:
    0
    Joined:
    Jun 14, 2011
    Messages:
    189
    qqwe
    в плюсах std::set
     
  4. qqwe

    qqwe New Member

    Blog Posts:
    0
    Joined:
    Jan 2, 2009
    Messages:
    2,914
    вы говорите чего вы хотите от этого всего. или пишите на известном вам фреймворке.

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

    есть и либы, но сперва надо знать что вы сделать хотите. желательно подробно.
     
  5. Vilco

    Vilco Vitaly

    Blog Posts:
    0
    Joined:
    Mar 5, 2007
    Messages:
    190
    Location:
    Nsk, Russia
    Битовые маски? Стандартных средств в Си нет (вроде).
    Объединить - | , пересечь - &. Проверка на принадлежность i-того элемента - через сдвиг единицы (либо хранить сдвинутые значения в массивчике, если скорость критичнее) + &.
    Нужно правда будет все элементы универсума занумеровать.
     
  6. qqwe

    qqwe New Member

    Blog Posts:
    0
    Joined:
    Jan 2, 2009
    Messages:
    2,914
    Vilco
    а это разве не стандартные средства?
    + к вашему
    ~ -- not
    ^ -- xor

    всякие маски и константы задаются, обычно

    enum {
    ...
    MASK_n = N,
    MASK_m = M,
    ...
    };

    итд (а я то думал)
     
  7. Vilco

    Vilco Vitaly

    Blog Posts:
    0
    Joined:
    Mar 5, 2007
    Messages:
    190
    Location:
    Nsk, Russia
    qqwe
    Человек, насколько я понял, искал готовые решения.
    Если элементов достаточно много (или вообще переменное число), то enum заведомо не годится. Но можно один раз посчитать все 1 << i и сложить их в массив, хотя смысла не очень много, ведь чтобы извлечь это значение потом из массива требуется примерно столько же времени сколько и для того, чтобы сдвинуть.
     
  8. srm

    srm New Member

    Blog Posts:
    0
    Joined:
    Jun 14, 2011
    Messages:
    189
    Что-то я не понял, при чём здесь битовые маски? Множества обычно ведь на основе красно чёрных деревьев реализуются.
     
  9. Dmitry_Milk

    Dmitry_Milk Member

    Blog Posts:
    0
    Joined:
    Nov 20, 2007
    Messages:
    540
    Если заранее известны всевозможные члены множества и их количество не превышает битовый размер нативного целого (например, 32), то используют битовые поля.

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

    srm New Member

    Blog Posts:
    0
    Joined:
    Jun 14, 2011
    Messages:
    189
    Dmitry_Milk, нет, мне нужно строки хранить в множестве. Тут никакие битовые маски не спасут.
     
  11. Booster

    Booster New Member

    Blog Posts:
    0
    Joined:
    Nov 26, 2004
    Messages:
    4,860
    Была подобная тема. К примеру в gtk есть, гуглите и найдёте.
     
  12. Dmitry_Milk

    Dmitry_Milk Member

    Blog Posts:
    0
    Joined:
    Nov 20, 2007
    Messages:
    540
    ТОгда относительно оптимальным вариантом может оказаться хэш-таблица строк. Или еще лучше - хэш таблица указателей на связные списки строк.