Implement set for generate data type?

[PengYu.UT]

Hi,

I'm searching for an implementation of set. I want to insert or delete
elements. The set should have no redudant element. It seems linked list
is one way for implementing set.

But I don't have any experence how to handle the C++ concept "templete"
in C. That is how to make the implemetation adaptable to different data
types.

Would you please point me some references? I'll also be glad, if you
can show me any implemenations of set in C. Thanks!

Best wishes,
Peng

 

[Lew Pitcher]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Hi,

I'm searching for an implementation of set. I want to insert or delete
elements. The set should have no redudant element. It seems linked list
is one way for implementing set.

But I don't have any experence how to handle the C++ concept "templete"
in C. That is how to make the implemetation adaptable to different data
types.

Would you please point me some references? I'll also be glad, if you
can show me any implemenations of set in C. Thanks!

Here's some hints...

union AllElements {
char Character;
unsigned int UnsignedInt;
unsigned long UnsignedLong;
float FloatPoint;
double LongFloatPoint;
};


struct A_Set_Element {
{
struct A_Set_Element *Next;
int Type;
union AllElements Valu;
};

and

#include <stdio.h>
void SayElementType(struct A_Set_Element *Element)
{
switch (Element->Type)
{
case 0: /* Character */
printf("Set Element is Character - value is '%c'\n",
Element->Valu.Character);
break;

case 1: /* UnsignedInt */
printf("Set Element is UnsignedInt - value is '%u'\n",
Element->Valu.UnsignedInt);
break;

/* and so on */
}
}




- --
Lew Pitcher

Master Codewright & JOAT-in-training | GPG public key available on request
Registered Linux User #112576 (http://counter.li.org/)
Slackware - Because I know what I'm doing.
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.4 (GNU/Linux)

iD8DBQFCsh5LagVFX4UWr64RAg0JAJ45C4I9MwEh+r3Ns/+UovuhKJ/yTQCgvp59
cZwmsOL+1pT43S8PtFeFj3c=
=dpZp
-----END PGP SIGNATURE-----

 

[PengYu.UT]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1



Here's some hints...

union AllElements {
char Character;
unsigned int UnsignedInt;
unsigned long UnsignedLong;
float FloatPoint;
double LongFloatPoint;
};


struct A_Set_Element {
{
struct A_Set_Element *Next;
int Type;
union AllElements Valu;
};

and

#include <stdio.h>
void SayElementType(struct A_Set_Element *Element)
{
switch (Element->Type)
{
case 0: /* Character */
printf("Set Element is Character - value is '%c'\n",
Element->Valu.Character);
break;

case 1: /* UnsignedInt */
printf("Set Element is UnsignedInt - value is '%u'\n",
Element->Valu.UnsignedInt);
break;

/* and so on */
}
}

Is it possible to use void pointer to point to the data? I think it is
easier to use than define union structures. Thanks!

 

[Jean-Claude Arbaut]

Le 17/06/2005 02:50, dans [email protected], « Lew

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

It's more on-topic on comp.programming I think, but just a suggestion,
you should probably use hash tables, for faster access. But maybe another
data structure is best, it greatly depends on your data. Linked list are
not very good since they need O(N) to access, with N the list length (but
insertion is fast). Other structures likes hashes, trees or B-trees may
be more suited. There are great textbooks on data structures:
"Aho, Hopcroft, Ullmann", "Cormen, Leiserson, Rivest, Stein", and "Knuth"
Among others. Google knows the titles

 

[PengYu.UT]

Le 17/06/2005 02:50, dans [email protected], « Lew
Pitcher » <[email protected]> a écrit :

It's more on-topic on comp.programming I think, but just a suggestion,
you should probably use hash tables, for faster access. But maybe another
data structure is best, it greatly depends on your data. Linked list are
not very good since they need O(N) to access, with N the list length (but
insertion is fast). Other structures likes hashes, trees or B-trees may
be more suited. There are great textbooks on data structures:
"Aho, Hopcroft, Ullmann", "Cormen, Leiserson, Rivest, Stein", and "Knuth"
Among others. Google knows the titles

For my specific application, N is less than some small threshold. So
the efficiency of the implementation is not very important to me. The
problem for me is that there are several data type that I have to put
into several sets. My concern is how to implement a generic set data
stucture such that I can put any type of data in it.

 

[Malcolm]

Is it possible to use void pointer to point to the data? I think it is
easier to use than define union structures. Thanks!

That's the route to go down.
In reality you seldom want to store basic types in a set (I presume you mean
the C++ stl set, but the term doesn't have an agreed programming meaning).

Your choice is, store pointers and effectively require all elements to be
allocated with malloc(), or store elements of arbitrary size and pass the
size in to the structure, treating them internally as arrays of unsigned
chars.

Neither method is perfect, which is why C++ introduced templates. The
pointer method is inefficient for small structures, whilst the pass the size
method is inefficinet when the elements you wnat to store are pointers
anyway.