工学1号馆

在《C面向对象编程–抽象数据类型》一文中，提出了set抽象数据类型以及相应的实现，其中set.h的接口如下:

extern const void * Set;

void * add (void * set, const void * element);
void * find (const void * set, const void * element);
void * drop (void * set, const void * element);
int contains (const void * set, const void * element);
unsigned count (const void * set);

这次使用动态存储来实现set与object，使用结构体：

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

这里的count跟踪set的元素的数量，例如，count记录set中添加元素的次数，调用drop函数移除元素直到数量为0，count也时刻改变来记录，于是我们实现一个新的可以记录数量的set–Bag

本文地址：http://wuyudong.com/2016/11/06/2942.html ，转载请注明出处。

因为需要动态存储来表示sets和objects，必需初始化Set与Object描述符：

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()：

void delete (void * item)
{
    free(item);
}

add()必须或多或少信赖指针类型的参数，它增加了元素的引用数量与set中元素的数量：

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()依然是检查元素是否指向适当的set:

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()没有发生改变：

int contains (const void * _set, const void * _element)
{
    return find(_set, _element) != 0;
}

如果drop()发现元素在set中，它减少元素的引用数量与set的元素数量，当元素的引用数量减少到0的时候，说明该元素已经从set中移除：

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()函数来返回set中元素的数目：

unsigned count (const void * _set)
{   const struct Set * set = _set;

    assert(set);
    return set -> count;
}

当然，直接使用.count更加的简单，但是我们坚持不暴露set的具体实现，在函数调用上面的开销与应用程序的值被覆盖的危险相比是微不足道的。

Bag 的行为不同于 Set：一个元素可以被添加几次，当其通过drop的次数与add的次数相同的时候，它只能从set中移除，一旦它被添加了许多次，因为它被添加。

将一个object通过add操作两次到set中，进行一次drop操作后，使用contains依然可以找到它。