Maximum for Arrays in C/C++

[Till Crueger]

Hi,
I have to implement some simple sorting algorithm. I am NOT asking for you
to do my homework, but my question is rather on how to store the integers.

I recall reading once in here that there is a maximum value the operator
[] has to accept. Since the programm should accept almost any number of
integers, I am not sure if this limit will be enough.

Also I would like to know the same about the STL-Vector class, since I
haven't decided wether to use c or c++. How about the speed of Vectors?
Could they be implemented as linked lists, which would make storing new
values much slower?
Thanks
Till

 

[Mike Wahler]

Hi,
I have to implement some simple sorting algorithm. I am NOT asking for you
to do my homework, but my question is rather on how to store the integers.

I recall reading once in here that there is a maximum value the operator
[] has to accept. Since the programm should accept almost any number of
integers, I am not sure if this limit will be enough.

The theoretical limit is the maximum value representable
by the standard type 'size_t' (an implementation-defined
unsigned integer type, declared by <stdlib.h> among other
headers), but the actual maximum will be also limited to
available memory (for dynamically allocated arrays), or
by compiler limits for file scope or local arrays. For
many compilers these limits a configurable. Check your
documentation for that.

Also I would like to know the same about the STL-Vector class,

<OT for clc>
The value returned by std::vector<>::max_size() will tell
you the maximum number of elements the vector can store (this
actual value will depend upon your implementation.) This again
will also be limited by available memory.

since I
haven't decided wether to use c or c++. How about the speed of Vectors?

The only way to know is to try both an array and a vector, and
measure the difference. This will also depend upon your implementation.
Neither the C nor C++ language makes an requirements about 'speed',
only behavior. But do research the 'complexity requirements' of the C++
standard containers.

Could they be implemented as linked lists, which would make storing new
values much slower?

<OT for clc>
A linked list (e.g. std::list<>) could be used, yes. But the performance of
storing values has dependencies. For a vector, adding elements at the end
will typically be faster than inserting elements elsewhere. Inserting
at an arbitrary location will typically be faster with a list than with a
vector. </OT for clc>

-Mike

 

[John Harrison]

Hi,
I have to implement some simple sorting algorithm. I am NOT asking for you
to do my homework, but my question is rather on how to store the integers.

I recall reading once in here that there is a maximum value the operator
[] has to accept. Since the programm should accept almost any number of
integers, I am not sure if this limit will be enough.

I don't know what the standard says but I would be very surprised if the
size of an array was limited by anything other than the amount of available
memory.

Also I would like to know the same about the STL-Vector class, since I
haven't decided wether to use c or c++. How about the speed of Vectors?

They're fast, might not be as quite fast as ordinary arrays, but they are a
damn site more convenient. Try both and time them, its the only way to find
out.

Could they be implemented as linked lists, which would make storing new
values much slower?

No they cannot be implemented as linked lists. They are implemented using
arrays.

P.S. In the end what was the problem with your 'miraculously incorrect
calculations', I'm curious to know.

john

 

[Darrell Grainger]

Hi,
I have to implement some simple sorting algorithm. I am NOT asking for you
to do my homework, but my question is rather on how to store the integers.

I recall reading once in here that there is a maximum value the operator
[] has to accept. Since the programm should accept almost any number of
integers, I am not sure if this limit will be enough.

If you need to accept any valid integer value then you will probably run
out of memory even if the compiler lets you create a large enough array.

Regardless, the limit for array size would be dependent on the compiler. I
have seen some implementations that limited the size of an array 32767 or
65535. Check the documentation for your compiler to determine the actual
limits of it unless you want to write something that will work for any
compiler that properly supports an ANSI C standard.

For the C standard I believe an object must hold at least 65535 bytes. So
if you use an int array and sizeof(int) == 4 the array must be able to
hold at least 16383 integers.

 

[David Harmon]

On Wed, 05 May 2004 19:52:14 +0200 in comp.lang.c++, "Till Crueger"

Also I would like to know the same about the STL-Vector class, since I
haven't decided wether to use c or c++.

Decide, then post to the ONE newsgroup that's appropriate.

 

[Malcolm]

I don't know what the standard says but I would be very surprised > if the

size of an array was limited by anything other than the amount

of available memory.

The size of an object (including an array) can also be limited by pointer
characteristics. This is to handle architectures without a flat address
space.

No they cannot be implemented as linked lists. They are
implemented using arrays.

Though the idea of STL is that the underlying representation in memory isn't
known the the programmer, so if there are a few links in there it won't
matter. However you'd be crazy to implement a vector as anything other than
a flat array.

 

[Martin Dickopp]

I don't know what the standard says but I would be very surprised if
the size of an array was limited by anything other than the amount of
available memory.

Please prepare to be very surprised.

The C standard says the following:

| 5.2.4.1 Translation limits
|
| 1 The implementation shall be able to translate and execute at least
| one program that contains at least one instance of every one of the
| following limits:
|
| [...]
| -- 65535 bytes in an object (in a hosted environment only)
| [...]

(This is obviously the C answer. Followup-To: comp.lang.c set.)

Martin

 

[CBFalconer]

I have to implement some simple sorting algorithm. I am NOT
asking for you to do my homework, but my question is rather
on how to store the integers.

I recall reading once in here that there is a maximum value
the operator [] has to accept. Since the programm should accept
almost any number of integers, I am not sure if this limit will
be enough.

The theoretical limit is the maximum value representable
by the standard type 'size_t' (an implementation-defined
unsigned integer type, declared by <stdlib.h> among other
headers), but the actual maximum will be also limited to
available memory (for dynamically allocated arrays), or
by compiler limits for file scope or local arrays. For
many compilers these limits a configurable. Check your
documentation for that.
.... snip OT C++ stuff ...

Could they be implemented as linked lists, which would make
storing new values much slower?

<OT for clc>
A linked list (e.g. std::list<>) could be used, yes. But the performance of
storing values has dependencies. For a vector, adding elements at the end
will typically be faster than inserting elements elsewhere. Inserting
at an arbitrary location will typically be faster with a list than with a
vector. </OT for clc>

While std::list is OT, singly linked lists (at least their
implementation in C) are not. They are very useful in that you do
not need advance knowledge of the list size, and can easily detect
the exhaustion of resources. They can also be efficiently sorted
with mergesort. The sort of system limits mentioned above are
likely to be less onerous under C than under C++, because the
system just uses fewer resources.

What you can't do quickly and easily is insert a new value in
order in a presorted list. This also applies to an array. This
sort of algorithmic choice is better suited to comp.programming.

If you want to remove duplicates on entry, an array is better.
Another method is a hash table, followed by forming a list and
sorting. An example of this is available in my hashlib package,
at:

<http://cbfalconer.home.att.net/download/>

Cross-posting between c.l.c and c.l.c++ is virtually never good,
so FUPs set.

 

[John Harrison]

I don't know what the standard says but I would be very surprised if
the size of an array was limited by anything other than the amount of
available memory.

Please prepare to be very surprised.

The C standard says the following:

| 5.2.4.1 Translation limits
|
| 1 The implementation shall be able to translate and execute at least
| one program that contains at least one instance of every one of the
| following limits:
|
| [...]
| -- 65535 bytes in an object (in a hosted environment only)
| [...]

(This is obviously the C answer. Followup-To: comp.lang.c set.)

Martin

That's not a limit, its a minimum requirement.

john

 

[Ben Pfaff]

I don't know what the standard says but I would be very surprised if
the size of an array was limited by anything other than the amount of
available memory.

The C standard says the following:

[...]

That's not a limit, its a minimum requirement.

A minimum requirement is the smallest possible limit, which is
all that you can depend on portably.

 

[Martin Dickopp]

I don't know what the standard says but I would be very surprised if
the size of an array was limited by anything other than the amount of
available memory.

Please prepare to be very surprised.

The C standard says the following:

| 5.2.4.1 Translation limits
|
| 1 The implementation shall be able to translate and execute at least
| one program that contains at least one instance of every one of the
| following limits:
|
| [...]
| -- 65535 bytes in an object (in a hosted environment only)
| [...]

That's not a limit, its a minimum requirement.

I actually omitted a footnote which says "Implementations should avoid
imposing fixed translation limits whenever possible." But footnotes are
not normative, so this is a quality-of-implementation issue.

To describe the situation in a more precise way: An implementation which
didn't support objects larger than 65535 bytes, even on systems with
tons of available memory, would still be a conforming implementation of
the C language according to the standard.

Martin