Array List?

[Michael B. Allen]

Coming from C and Java on *nix I'm a little out of my element messing around
with CList and MSVC++ but I think my issues are largely syntactic.

I have an ADT that I use called a 'varray' that can return a pointer to an
arbirary sized element in an array given an index and it will allocate the
memory to back it if necessary:

struct varray *tests = varray_new(size of(struct test));
struct test *t = (struct test *)varray_get(te sts, 50));

The point being I don't have to allocate the memory for *t. Each element in
the backing array is sizeof(struct test).

Is there an equivalent ADT in C++ that I should use?

Thanks,
Mike

ref: http://www.ioplex.com/~miallen/libmba/dl/src/varray.c

[Michael B. Allen]

Re: Array List?

"Alf P. Steinbach" <alfps@start.no > wrote in message
news:3f5c369a.3 60393171@News.C IS.DFN.DE...[color=blue][color=green]
> >I have an ADT that I use called a 'varray' that can return a pointer to[/color][/color]
an[color=blue][color=green]
> >arbirary sized element in an array given an index and it will allocate[/color][/color]
the[color=blue][color=green]
> >memory to back it if necessary:
> >
> > struct varray *tests = varray_new(size of(struct test));
> > struct test *t = (struct test *)varray_get(te sts, 50));
> >
> >The point being I don't have to allocate the memory for *t. Each element[/color][/color]
in[color=blue][color=green]
> >the backing array is sizeof(struct test).
> >
> >Is there an equivalent ADT in C++ that I should use?[/color]
>
> Check out the standard containers, std::vector, std::list and so on.[/color]

You mean like this? Is this legit?

#include <iostream>
#include <list>
using namespace std;

struct foo {
int i;
short s;
};

main()
{
list<struct foo> L;
struct foo f;

f.i = 10;
f.s = 5;
L.push_back(f);
f.i = 30;
f.s = 15;
L.push_front(f) ;
f.i = 100;
f.s = 50;
L.insert(++L.be gin(),f);
f.i = 101;
f.s = 51;
L.push_back(f);
f.i = 102;
f.s = 52;
L.push_back(f);

list<struct foo>::iterator i;

for(i=L.begin() ; i != L.end(); ++i) cout << "i=" << i->i << ",s=" << i->s
<< " ";
cout << endl;
return 0;
}

c:\miallen\p>li st
i=30,s=15 i=100,s=50 i=10,s=5 i=101,s=51 i=102,s=52

[Alf P. Steinbach]

Re: Array List?

On Mon, 8 Sep 2003 14:10:16 -0700, "Michael B. Allen" <mba2000@ioplex .com> wrote:
[color=blue]
>"Alf P. Steinbach" <alfps@start.no > wrote in message
>news:3f5c369a. 360393171@News. CIS.DFN.DE...[color=green][color=darkred]
>> >I have an ADT that I use called a 'varray' that can return a pointer to[/color][/color]
>an[color=green][color=darkred]
>> >arbirary sized element in an array given an index and it will allocate[/color][/color]
>the[color=green][color=darkred]
>> >memory to back it if necessary:
>> >
>> > struct varray *tests = varray_new(size of(struct test));
>> > struct test *t = (struct test *)varray_get(te sts, 50));
>> >
>> >The point being I don't have to allocate the memory for *t. Each element[/color][/color]
>in[color=green][color=darkred]
>> >the backing array is sizeof(struct test).
>> >
>> >Is there an equivalent ADT in C++ that I should use?[/color]
>>
>> Check out the standard containers, std::vector, std::list and so on.[/color]
>
>You mean like this?[/color]

Good. I'll comment only on opportunities for improvement.

[color=blue]
> Is this legit?[/color]

Yep.


[color=blue]
>#include <iostream>
>#include <list>
>using namespace std;[/color]

Prevents you from using names like 'list' for your own purposes.


[color=blue]
>struct foo {
> int i;
> short s;
>};[/color]

A constructor can ease things considerably, avoiding e.g. dummy
variables like 'f' below, as well as the assignments.

[color=blue]
>main()[/color]

'main' must have return type 'int'.

See [http://www.research.att.com/~bs/bs_faq2.html#void-main].


[color=blue]
>{
> list<struct foo> L;[/color]

No need to repeat the word 'struct' (in contrast to C, in C++ a
'struct' is a type like any others).

Avoiding all uppercase names can help avoid name conflicts with
macros.

[color=blue]
> struct foo f;
>
> f.i = 10;
> f.s = 5;
> L.push_back(f);
> f.i = 30;
> f.s = 15;
> L.push_front(f) ;
> f.i = 100;
> f.s = 50;
> L.insert(++L.be gin(),f);
> f.i = 101;
> f.s = 51;
> L.push_back(f);
> f.i = 102;
> f.s = 52;
> L.push_back(f);
>
> list<struct foo>::iterator i;
>
> for(i=L.begin() ; i != L.end(); ++i) cout << "i=" << i->i << ",s=" << i->s
><< " ";
> cout << endl;
> return 0;
>}[/color]


Consider


#include <iostream>
#include <list>

struct Foo
{
int i;
short s;

Foo( int iValue, short sValue ): i( iValue ), s( sValue ) {}
};

int main()
{
std::list<Foo> list;

list.push_back( Foo( 10, 5 ) );
list.push_front ( Foo( 30, 15 ) );
list.insert( ++list.begin(), Foo( 100, 50 ) );
list.push_back( Foo( 101, 51 ) );
list.push_back( Foo( 102, 52 ) );

std::list<Foo>: :iterator i;

for( i = list.begin(); i != list.end(); ++i )
{
std::cout << "i=" << i->i << ",s=" << i->s << " " << std::endl;
}
}

[color=blue]
>c:\miallen\p>l ist
>i=30,s=15 i=100,s=50 i=10,s=5 i=101,s=51 i=102,s=52[/color]

[Michael B. Allen]

Re: Array List?


"Alf P. Steinbach" <alfps@start.no > wrote in message
news:3f5cca5d.3 98220265@News.C IS.DFN.DE...[color=blue]
> #include <iostream>
> #include <list>
>
> struct Foo
> {
> int i;
> short s;
>
> Foo( int iValue, short sValue ): i( iValue ), s( sValue ) {}
> };
>
> int main()
> {
> std::list<Foo> list;
>
> list.push_back( Foo( 10, 5 ) );[/color]
"
Interesting. Is that a constructor? Is there a relationship between this and
the constructor of a class? Does this degenerate into a class or is this
just some extra notation specific to structures?

In practice do folks just end up using classes over structs entirely? Or is
there an advantage to using a struct like this? One of the things that
bothered me about C++ that you cannot not be certain what was in memory
(e.g. you cannot serialize, inspect, or partially copy the memory occupied
by a class for fear of breaking it). Explicit memory manipluation is what
makes C great (yes, and dangerous).

Thanks,
Mike

[llewelly]

Re: Array List?

"Michael B. Allen" <mba2000@ioplex .com> writes:
[color=blue]
> "Alf P. Steinbach" <alfps@start.no > wrote in message
> news:3f5cca5d.3 98220265@News.C IS.DFN.DE...[color=green]
>> #include <iostream>
>> #include <list>
>>
>> struct Foo[/color][/color]

A struct is a class whose members and bases are public by default (as
opposed to private). There is no other difference between struct and
class. structs may have constructors, destructors, copy-assignment
operators, virtual functions, base classes, virtual base classes,
etc, all with the same semantics as classes do.
[color=blue][color=green]
>> {
>> int i;
>> short s;
>>
>> Foo( int iValue, short sValue ): i( iValue ), s( sValue )
>> {}[/color][/color]

This is a constructor.
[color=blue][color=green]
>> };
>>
>> int main()
>> {
>> std::list<Foo> list;
>>
>> list.push_back( Foo( 10, 5 ) );[/color]
> "
> Interesting. Is that a constructor?[/color]

Yes.
[color=blue]
> Is there a relationship between this and
> the constructor of a class?[/color]

It fills the same role. The standard refers to both structs and
classes as 'class types'

[snip][color=blue]
> In practice do folks just end up using classes over structs entirely? Or is
> there an advantage to using a struct like this?[/color]

Yes. It is common to place public interface before private
members. Since struct access is public default, it suits this
style naturally.
[color=blue]
> One of the things that
> bothered me about C++ that you cannot not be certain what was in memory
> (e.g. you cannot serialize, inspect, or partially copy the memory occupied
> by a class for fear of breaking it). Explicit memory manipluation is what
> makes C great (yes, and dangerous).[/color]
[snip]

This is not true. C and C++ offer essentially the same guarantees in
this area.

[Alf P. Steinbach]

Re: Array List?

On Mon, 8 Sep 2003 14:58:01 -0700, "Michael B. Allen" <mba2000@ioplex .com> wrote:
[color=blue]
>
>"Alf P. Steinbach" <alfps@start.no > wrote in message
>news:3f5cca5d. 398220265@News. CIS.DFN.DE...[color=green]
>> #include <iostream>
>> #include <list>
>>
>> struct Foo
>> {
>> int i;
>> short s;
>>
>> Foo( int iValue, short sValue ): i( iValue ), s( sValue ) {}
>> };
>>
>> int main()
>> {
>> std::list<Foo> list;
>>
>> list.push_back( Foo( 10, 5 ) );[/color]
>"
>Interesting. Is that a constructor? Is there a relationship between this and
>the constructor of a class? Does this degenerate into a class or is this
>just some extra notation specific to structures?[/color]

Here I'll just redirect you to the FAQ, your textbook, etc., but yes, yes, yes,
and no, and


[color=blue]
>In practice do folks just end up using classes over structs entirely? Or is
>there an advantage to using a struct like this?[/color]

yes, and depends.

[color=blue]
>One of the things that
>bothered me about C++ that you cannot not be certain what was in memory
>(e.g. you cannot serialize, inspect, or partially copy the memory occupied
>by a class for fear of breaking it).[/color]

You can do whatever you do in C, but C++ provides additional features where
you can't do whatever you do in C. Scribble on yellow note: intelligent
constraints yield power. Put note on computer monitor.

[Michael B. Allen]

Re: Array List?


"llewelly" <llewelly.at@xm ission.dot.com> wrote in message
news:8665k3ume6 .fsf@Zorthluthi k.local.bar...[color=blue][color=green]
> > One of the things that
> > bothered me about C++ that you cannot not be certain what was in memory
> > (e.g. you cannot serialize, inspect, or partially copy the memory[/color][/color]
occupied[color=blue][color=green]
> > by a class for fear of breaking it). Explicit memory manipluation is[/color][/color]
what[color=blue][color=green]
> > makes C great (yes, and dangerous).[/color]
> [snip]
>
> This is not true. C and C++ offer essentially the same guarantees in
> this area.[/color]

Actually I just realized something that might illustrate my point. In my
original C example I basically had:

struct Foo *f = varray_get(foos , index);
f->i = 10;
f->s = 5;

The C++ alternative is:

list.push_back( Foo( 10, 5 ) );

The benifit of the C version was that one memory allocation might accomodate
many structs and nothing is copied. You are given a pointer to _the_ memory.
In the C++ version I don't think this is the case. Is push_back copying an
entire Foo? Also, is Foo( 10, 5 ) makeing another function call?

I don't mean to nit-pik (yet). I'm just trying to understand what's
happening under the hood.

Mike

[Alf P. Steinbach]

Re: Array List?

On Mon, 8 Sep 2003 15:27:01 -0700, "Michael B. Allen" <mba2000@ioplex .com> wrote:
[color=blue]
>
>"llewelly" <llewelly.at@xm ission.dot.com> wrote in message
>news:8665k3ume 6.fsf@Zorthluth ik.local.bar...[color=green][color=darkred]
>> > One of the things that
>> > bothered me about C++ that you cannot not be certain what was in memory
>> > (e.g. you cannot serialize, inspect, or partially copy the memory[/color][/color]
>occupied[color=green][color=darkred]
>> > by a class for fear of breaking it). Explicit memory manipluation is[/color][/color]
>what[color=green][color=darkred]
>> > makes C great (yes, and dangerous).[/color]
>> [snip]
>>
>> This is not true. C and C++ offer essentially the same guarantees in
>> this area.[/color]
>
>Actually I just realized something that might illustrate my point. In my
>original C example I basically had:
>
> struct Foo *f = varray_get(foos , index);
> f->i = 10;
> f->s = 5;
>
>The C++ alternative is:[/color]


Two errors in that sentence. (1) You can do the same in C++, and at
different levels of abstraction, including the raw C level. (2) There
are more than one way to obtain the high-level functionality, including
but not limited to per-structure allocation.


[color=blue]
> list.push_back( Foo( 10, 5 ) );
>
>The benifit of the C version was that one memory allocation might accomodate
>many structs and nothing is copied. You are given a pointer to _the_ memory.[/color]

Consider


std::vector<Foo > foos( cacheSize );
Foo& f = foos[index];

f.i = 10;
f.s = 5;


[color=blue]
>In the C++ version I don't think this is the case. Is push_back copying an
>entire Foo? Also, is Foo( 10, 5 ) makeing another function call?[/color]

It can be, yes in this example, quality of implementation.

[Michael B. Allen]

Explicit Memory Management of Strings


"Alf P. Steinbach" <alfps@start.no > wrote in message
news:3f5cdb67.4 02581531@News.C IS.DFN.DE...
[color=blue][color=green]
> >The benifit of the C version was that one memory allocation might[/color][/color]
accomodate[color=blue][color=green]
> >many structs and nothing is copied. You are given a pointer to _the_[/color][/color]
memory.[color=blue]
>
> Consider
>
>
> std::vector<Foo > foos( cacheSize );
> Foo& f = foos[index];
>
> f.i = 10;
> f.s = 5;[/color]

So the [] operator is overloaded to allocate memory backing the memory at
that index? Or is the entire Foo still being copied?

Here's a similar problem I'm having (not really a problem but coming from
pure C I'd like to know how to do this sort of thing); I have a
csv_row_parse function that parses a Comma Separated Values (CSV) file and
populates a char *row[] array with pointers to each element in a CSV record.
Now I know that the pointers in this array all point to one continuous chunk
of memory and that the order of elements in that memory is preserved in the
array.

Here's the problem; I need a class with a CString *args[10] member that
corresponds to row elements 4 to 13 in the row. Because I know the pointers
of interest all appear together in memory I can just copy them by finding
the last valid element, finding the end of it, and then substracting a
pointer to the first element to get the chunk of memory that needs to be
copied:

struct test *t = varray_get(test s, index);

memset(t->args, 0, 10 * sizeof *str);
for(i = 4; i < 14 && row[i]; i++) { /* find the last args element */
str = row[i];
}
if (i > 4) {
/* calc the very end of the last args element */
size_t siz = ((str + str_length(str, rlim) + 1) - row[4]) * sizeof *str;
if ((str = (char *)malloc(siz)) == NULL) {
return -1;
}
/* allocate and copy */
memcpy(str, row[4], siz);
for(i = 4; i < 14 && row[i]; i++) {
/* recalculate pointers relative to the
* beginning of the new mem chunk */
t->args[i - 4] = str + (row[i] - row[4]);
}
}

Now all the args are in one string. Can I do this with CString?

Thanks,
Mike

ref: http://www.ioplex.com/~miallen/libmba/dl/src/csv.c

[Karl Heinz Buchegger]

Re: Explicit Memory Management of Strings



"Michael B. Allen" wrote:[color=blue]
>
> "Alf P. Steinbach" <alfps@start.no > wrote in message
> news:3f5cdb67.4 02581531@News.C IS.DFN.DE...
>[color=green][color=darkred]
> > >The benifit of the C version was that one memory allocation might[/color][/color]
> accomodate[color=green][color=darkred]
> > >many structs and nothing is copied. You are given a pointer to _the_[/color][/color]
> memory.[color=green]
> >
> > Consider
> >
> >
> > std::vector<Foo > foos( cacheSize );
> > Foo& f = foos[index];
> >
> > f.i = 10;
> > f.s = 5;[/color]
>
> So the [] operator is overloaded to allocate memory backing the memory at
> that index? Or is the entire Foo still being copied?[/color]

No. The element at that index has to exist already. Since the
vector is initialized with cacheSize elements, that many elements
are created by the constructor of the vector:

In the above, nothing gets copied in
Foo& f = foos[index];

f is a *reference* to the element in the vector. A reference
is another name for an already existing object.

Alf could have written as well:

std::vector<Foo > foos( cacheSize );
foos[index] = Foo( 10, 5 );

Why don't you do yourself a favour and buy a book about C++?
You will need it. You can't learn a language like C++ by studying
some examples out of context. C++ is much to powerfull for this,
even if you have C-knowledge.
[color=blue]
>
> Here's a similar problem I'm having (not really a problem but coming from
> pure C I'd like to know how to do this sort of thing); I have a
> csv_row_parse function that parses a Comma Separated Values (CSV) file and
> populates a char *row[] array with pointers to each element in a CSV record.
> Now I know that the pointers in this array all point to one continuous chunk
> of memory and that the order of elements in that memory is preserved in the
> array.
>
> Here's the problem; I need a class with a CString *args[10] member that
> corresponds to row elements 4 to 13 in the row. Because I know the pointers
> of interest all appear together in memory I can just copy them by finding
> the last valid element, finding the end of it, and then substracting a
> pointer to the first element to get the chunk of memory that needs to be
> copied:
>
> struct test *t = varray_get(test s, index);
>
> memset(t->args, 0, 10 * sizeof *str);
> for(i = 4; i < 14 && row[i]; i++) { /* find the last args element */
> str = row[i];
> }
> if (i > 4) {
> /* calc the very end of the last args element */
> size_t siz = ((str + str_length(str, rlim) + 1) - row[4]) * sizeof *str;
> if ((str = (char *)malloc(siz)) == NULL) {
> return -1;
> }
> /* allocate and copy */
> memcpy(str, row[4], siz);
> for(i = 4; i < 14 && row[i]; i++) {
> /* recalculate pointers relative to the
> * beginning of the new mem chunk */
> t->args[i - 4] = str + (row[i] - row[4]);
> }
> }
>
> Now all the args are in one string. Can I do this with CString?[/color]

The first thing you need to get rid of:
Drop your use of pointers. In C++ you do much less with them then you did in C.
Drop your way of thinking in memory locations and how you can use clever tricks
with pointer arithmetic to get at the information you want.

In C++ one would create

std::vector< std::string > Args

and fill in entire objects, instead of fidelling around with pointers and memory
allocation stuff. Stop your thinking of raw memory and how to squeeze out every
last nanosecond from the code. Work with objects: objects are resonsible for themselfs.
Objects *know* how to deal with the low level stuff. If you need a string, then
you have one: std::string or CString (if you are working with MFC). And that
std::string deals with the low level things, you just say:

mystring = "abcdef";

and the string class does the memory allocation under the hood.

You need an array of strings. Easy ...

std::vector< std::string > MyStrings;

.... is one. It does everything for you:

MyStrings.push_ back( "hello world" );
MyStrings.push_ back( "this is a" );
MyStrings.push_ back( "example" );

MyStrings[1] = "this is not an";

The string class handles all the details need for handling
one string and the vector class handles all the details needed
to have an array of strings which can grow dynamically.

I know it's hard. But the change from C to C++ is not just
only different syntax. If you want to go OO, then you also
need a different way of thinking.

--
Karl Heinz Buchegger
kbuchegg@gascad .at

[tom_usenet]

Re: Explicit Memory Management of Strings

On Mon, 8 Sep 2003 16:22:48 -0700, "Michael B. Allen"
<mba2000@ioplex .com> wrote:
[color=blue]
>
>"Alf P. Steinbach" <alfps@start.no > wrote in message
>news:3f5cdb67. 402581531@News. CIS.DFN.DE...
>[color=green][color=darkred]
>> >The benifit of the C version was that one memory allocation might[/color][/color]
>accomodate[color=green][color=darkred]
>> >many structs and nothing is copied. You are given a pointer to _the_[/color][/color]
>memory.[color=green]
>>
>> Consider
>>
>>
>> std::vector<Foo > foos( cacheSize );
>> Foo& f = foos[index];
>>
>> f.i = 10;
>> f.s = 5;[/color]
>
>So the [] operator is overloaded to allocate memory backing the memory at
>that index? Or is the entire Foo still being copied?[/color]

operator[] is overloaded to return a reference (like a pointer) to a
member of the vector. No copying occurs - f above is just an alias for
the index'th member of foos.
[color=blue]
>Here's a similar problem I'm having (not really a problem but coming from
>pure C I'd like to know how to do this sort of thing); I have a
>csv_row_pars e function that parses a Comma Separated Values (CSV) file and
>populates a char *row[] array with pointers to each element in a CSV record.
>Now I know that the pointers in this array all point to one continuous chunk
>of memory and that the order of elements in that memory is preserved in the
>array.
>
>Here's the problem; I need a class with a CString *args[10] member that
>corresponds to row elements 4 to 13 in the row. Because I know the pointers
>of interest all appear together in memory I can just copy them by finding
>the last valid element, finding the end of it, and then substracting a
>pointer to the first element to get the chunk of memory that needs to be
>copied:
>
>struct test *t = varray_get(test s, index);
>
>memset(t->args, 0, 10 * sizeof *str);
>for(i = 4; i < 14 && row[i]; i++) { /* find the last args element */
> str = row[i];
>}
>if (i > 4) {
> /* calc the very end of the last args element */
> size_t siz = ((str + str_length(str, rlim) + 1) - row[4]) * sizeof *str;
> if ((str = (char *)malloc(siz)) == NULL) {
> return -1;
> }
> /* allocate and copy */
> memcpy(str, row[4], siz);
> for(i = 4; i < 14 && row[i]; i++) {
> /* recalculate pointers relative to the
> * beginning of the new mem chunk */
> t->args[i - 4] = str + (row[i] - row[4]);
> }
>}
>
>Now all the args are in one string. Can I do this with CString?[/color]

In this case you'd make str a std::string or vector<char> (to avoid
the memory management), but you'd stick with args being char*'s.
std::string (and CString) controls its own memory - there is no way to
get a CString to reference part of another string (although such a
class might be useful).

If this code isn't called in an inner loop, then having a separate
std::string for each arg would be the way to go. This will be fast
enough unless dealing with very large CSV files.

This may be of interest:

http://www.sgi.com/tech/stl/string_discussion.html

Tom

[Christian Brechbühler]

Re: Explicit Memory Management of Strings

Stroustrup (section 20.3.13) presents template Basic_substring which
does roughly that.

tom_usenet wrote:[color=blue]
> std::string (and CString) controls its own memory - there is no way to
> get a CString to reference part of another string (although such a
> class might be useful).[/color]