Velocity Reviews > Array of structs instead of an array with pointers to structs?

# Array of structs instead of an array with pointers to structs?

Paminu
Guest
Posts: n/a

 10-11-2005
Why make an array of pointers to structs, when it is possible to just make
an array of structs?

I have this struct:

struct test {
int a;
int b;
};

I have then made an array:

struct test testarray[5];

I would then like to shift all the elements one index to the right and
afterwards insert a new pkt struct at index 0.

something like this:

I would like to insert 3 different test structs with "b": 10, 20, and 30.

When I iterate through the testarray and make a printout of testarray[i].b,
I should see something like this:

10, 0, 0, 0, 0
20, 10, 0, 0, 0
30, 20, 10, 0, 0

For this to work I have made this function:

void insertIntoBuffer(struct test tt)
{
int c;
for(c=3; c>=0; c--)
{
testarray[c+1] = testarray[c];
}

testarray[0] = tt;
int i;
for (i = 0; i < 5; i++ )
{
}
printf("\n");

}

It seems to work fine, so I can't seem to see any reason to mess around with
an array of pointers.

Are there anything that I cannot do with this simple solution that would be
possible with an array of pointers to structs?

Singamsetty
Guest
Posts: n/a

 10-11-2005

Paminu wrote:
> Why make an array of pointers to structs, when it is possible to just make
> an array of structs?
>
>
> void insertIntoBuffer(struct test tt)
> {
> int c;
> for(c=3; c>=0; c--)
> {
> testarray[c+1] = testarray[c];
> }
>
> testarray[0] = tt;
> int i;
> for (i = 0; i < 5; i++ )
> {
> }
> printf("\n");
>
> }
>
> It seems to work fine, so I can't seem to see any reason to mess around with
> an array of pointers.
>
> Are there anything that I cannot do with this simple solution that would be
> possible with an array of pointers to structs?

......Observe that everytime you insert a new element into the array you
are using a for loop to shift all elements....in general the complexity
of this function is O(n), which can be achieved in constant time O(1)
the list.

- Singamsetty

Paminu
Guest
Posts: n/a

 10-11-2005
Singamsetty wrote:

>
> Paminu wrote:
>> Why make an array of pointers to structs, when it is possible to just
>> make an array of structs?
>>
>>
>> void insertIntoBuffer(struct test tt)
>> {
>> int c;
>> for(c=3; c>=0; c--)
>> {
>> testarray[c+1] = testarray[c];
>> }
>>
>> testarray[0] = tt;
>> int i;
>> for (i = 0; i < 5; i++ )
>> {
>> }
>> printf("\n");
>>
>> }
>>
>> It seems to work fine, so I can't seem to see any reason to mess around
>> with an array of pointers.
>>
>> Are there anything that I cannot do with this simple solution that would
>> be possible with an array of pointers to structs?

>
>
> .....Observe that everytime you insert a new element into the array you
> are using a for loop to shift all elements....in general the complexity
> of this function is O(n), which can be achieved in constant time O(1)
> the list.
>
> - Singamsetty

Ok so the "only" difference between regular arrays and pointers are the
efficency?

Mike Wahler
Guest
Posts: n/a

 10-11-2005

"Paminu" <(E-Mail Removed)> wrote in message
news:dih1mq\$rbt\$(E-Mail Removed)-c.dk...
> Singamsetty wrote:
>
>>
>> Paminu wrote:
>>> Why make an array of pointers to structs, when it is possible to just
>>> make an array of structs?
>>>
>>>
>>> void insertIntoBuffer(struct test tt)
>>> {
>>> int c;
>>> for(c=3; c>=0; c--)
>>> {
>>> testarray[c+1] = testarray[c];
>>> }
>>>
>>> testarray[0] = tt;
>>> int i;
>>> for (i = 0; i < 5; i++ )
>>> {
>>> }
>>> printf("\n");
>>>
>>> }
>>>
>>> It seems to work fine, so I can't seem to see any reason to mess around
>>> with an array of pointers.
>>>
>>> Are there anything that I cannot do with this simple solution that would
>>> be possible with an array of pointers to structs?

>>
>>
>> .....Observe that everytime you insert a new element into the array you
>> are using a for loop to shift all elements....in general the complexity
>> of this function is O(n), which can be achieved in constant time O(1)
>> the list.
>>
>> - Singamsetty

>
>
> Ok so the "only" difference between regular arrays and pointers are the
> efficency?

No.

An array is a collection of one or more objects of the same type.
A pointer is a single object. Depending upon what you're doing,
one may be more useful than the other.

-Mike

Singamsetty
Guest
Posts: n/a

 10-11-2005

Paminu wrote:
> Singamsetty wrote:
>
> >
> > Paminu wrote:
> >> Why make an array of pointers to structs, when it is possible to just
> >> make an array of structs?
> >>
> >>
> >> void insertIntoBuffer(struct test tt)
> >> {
> >> int c;
> >> for(c=3; c>=0; c--)
> >> {
> >> testarray[c+1] = testarray[c];
> >> }
> >>
> >> testarray[0] = tt;
> >> int i;
> >> for (i = 0; i < 5; i++ )
> >> {
> >> printf("Added b %d\n", testarray[i].b);
> >> }
> >> printf("\n");
> >>
> >> }
> >>
> >> It seems to work fine, so I can't seem to see any reason to mess around
> >> with an array of pointers.
> >>
> >> Are there anything that I cannot do with this simple solution that would
> >> be possible with an array of pointers to structs?

> >
> >
> > .....Observe that everytime you insert a new element into the array you
> > are using a for loop to shift all elements....in general the complexity
> > of this function is O(n), which can be achieved in constant time O(1)
> > if you use pointers (linked list) and add a new element at the head of
> > the list.
> >
> > - Singamsetty

>
>
> Ok so the "only" difference between regular arrays and pointers are the
> efficency?

.........There are always trade-offs between pointers and arrays. It all
depends on what you are trying to do. Pointers are not as efficient as
arrays when it comes to storing a fixed amount of data, which requires
a non-sequential access.

- Singamsetty

Eric Sosman
Guest
Posts: n/a

 10-11-2005

Paminu wrote On 10/11/05 14:30,:
> Why make an array of pointers to structs, when it is possible to just make
> an array of structs?

More generally, "Why make an array of pointers to X, when it
is possible to just make an array of X?"

The principal reason is flexibility. The size of an array
is fixed when you create it and cannot be changed, but with
pointers you can start using malloc() and friends to let your
data structures automatically adjust to the "problem size."
Also, pointers let you build data structures that just don't
work with plain arrays -- for example, the array of pointers
might contain several pointers to the same struct instance.

In some settings an array of pointers can lead to speed
improvements. For example, suppose you've got ten thousand
very large struct objects and you want to use qsort() to put
them in order. Even if the structs themselves do happen to
reside in an array, you might do better to build an array of
pointers to them and use qsort() to rearrange the pointers:
instead of sloshing all those 792-byte structs back and forth
to reorganize the array, qsort() can just move small 4- or 8-
byte pointers around and may well run faster. You could use
several such "parallel" pointer arrays to sort the big array
of structs in different ways simultaneously: one pointer array
would be sorted by telephone number, another by postal code,
another by credit card balance, and so on. It probably uses
less memory to store one array of big structs and three arrays
of small pointers than to store three separate copies of all
those structs -- and if you're making changes to them, you'd
need to remember to change every copy ...

Pointer arrays are not The Magic Solution to every problem,
and it's silly to use them when you don't need them. But there
is certainly no reason to avoid them, and many circumstances
when they are the tool of choice.

--
http://www.velocityreviews.com/forums/(E-Mail Removed)