1.8 Другая реализация — Bag

Можно изменить реализацию без изменения видимого интерфейса в Set.h. На этот раз мы используем динамическую память и представим наборы и объекты в виде структур:

struct Set { unsigned count; };

struct Object { unsigned count; struct Set * in; };

count отслеживает количество элементов в наборе. Для элемента же count фиксирует сколько раз этот элемент был добавлен в набор. Если count уменьшается каждый раз, когда элемент передаётся в drop(), и удаление элемент происходит только когда count равен нулю, получается Bag, то есть набор, где элементы имеют счётчик ссылок.

Так как для представления наборов и объектов будет использоваться динамическая память, необходимо проинициализировать дескрипторы Set и Object, чтобы new() могла знать, сколько памяти резервировать:

static const size_t _Set = sizeof(struct Set);

static const size_t _Object = sizeof(struct Object);

const void * Set = & _Set;

const void * Object = & _Object;

new() теперь намного проще:

void * new (const void * type, ...) {

    const size_t size = * (const size_t *) type;

    void * p = calloc(1, size);

    assert(p);

    return p;

}

delete() может передать свой аргумент непосредственно в free() — в ANSI-C в free() может быть передан нулевой указатель.

add() вынуждена более или менее доверять аргументам своего указателя. Она увеличивает счётчик ссылок элемента и количество элементов в наборе:

void * add (void * _set, const void * _element) {

    struct Set * set = _set;

    struct Object * element = (void *) _element;

    assert(set);

    assert(element);

    if (! element -> in)

        element -> in = set;

    else

        assert(element -> in == set);

    ++ element -> count, ++ set -> count;

    return element;

}

find() по-прежнему проверяет, указывает ли элемент на соответствующий набор:

void * find (const void * _set, const void * _element) {

    const struct Object * element = _element;

    assert(_set);

    assert(element);

    return element -> in == _set ? (void *) element : 0;

}

contains() опирается на find() и остаётся неизменной.

Если drop() находит данный элемент в наборе, она уменьшает счётчик ссылок элемента и количество элементов в наборе. Если счётчик ссылок достигает нуля, элемент удаляется из набора:

void * drop (void * _set, const void * _element) {

    struct Set * set = _set;

    struct Object * element = find(set, _element);

    if (element) {

        if (-- element -> count == 0)

            element -> in = 0;

        -- set -> count;

    }

    return element;

}

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

unsigned count (const void * _set) {

    const struct Set * set = _set;

    assert(set);

    return set -> count;

}

Конечно, было бы проще позволить приложению считывать компонент .count непосредственно, но мы настаиваем на нераскрытии представления наборов. Накладные расходы на вызов функции незначительны по сравнению с опасностью того, что приложение будет способно перезаписать критическое значение.

Bag-и (множества) ведут себя иначе, чем set-ы (наборы): элемент может быть добавлен несколько раз; он исчезнет из множества только после того, как будет удалён столько раз, сколько был добавлен. Наше приложение в разделе 1.6 добавило объект a в набор дважды. После того, как он удаляется из набора один раз, contains() по-прежнему найдёт его в этом множестве. Тестовая программа теперь выводит

ok

drop?