469,926 Members | 1,656 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 469,926 developers. It's quick & easy.

Maximum for Arrays in C/C++

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
--
Please add "Salt and Peper" to the subject line to bypass my spam filter
Jul 22 '05 #1
9 2404
"Till Crueger" <Ti****@gmx.net> wrote in message
news:c7**********@f1node01.rhrz.uni-bonn.de...
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.
</OT for clc>
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
Jul 22 '05 #2

"Till Crueger" <Ti****@gmx.net> wrote in message
news:c7**********@f1node01.rhrz.uni-bonn.de...
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
Jul 22 '05 #3
On Wed, 05 May 2004 20:21:27 +0100, John Harrison wrote:
P.S. In the end what was the problem with your 'miraculously incorrect
calculations', I'm curious to know.


Well, it wasn't actually in the code I posted, but it took me a long time
to figure that out. It helped to break the code down to small pieces still
containing the bug. Somewhere along I called the method normalize of the
Vector. I took it for granted this method was implemented as const, but it
wasn't. Hence the wrong results. Since I would have never guessed this
method might wreak havoc on my object I didn't include it. Guess I do much
better when I post code the next time *gg*.
Till

--
Please add "Salt and Peper" to the subject line to bypass my spam filter

Jul 22 '05 #4
On Wed, 05 May 2004 19:52:14 +0200 in comp.lang.c++, "Till Crueger"
<Ti****@gmx.net> wrote,
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.

Jul 22 '05 #5
On Wed, 5 May 2004, Till Crueger wrote:
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.
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
--
Please add "Salt and Peper" to the subject line to bypass my spam filter


--
Send e-mail to: darrell at cs dot toronto dot edu
Don't send e-mail to vi************@whitehouse.gov
Jul 22 '05 #6

"John Harrison" <jo*************@hotmail.com> wrote in message

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.
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.

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.
Jul 22 '05 #7
"John Harrison" <jo*************@hotmail.com> writes:
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
--
,--. Martin Dickopp, Dresden, Germany ,= ,-_-. =.
/ ,- ) http://www.zero-based.org/ ((_/)o o(\_))
\ `-' `-'(. .)`-'
`-. Debian, a variant of the GNU operating system. \_/
Jul 22 '05 #8
Mike Wahler wrote:
"Till Crueger" <Ti****@gmx.net> wrote in message
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.

--
fix (vb.): 1. to paper over, obscure, hide from public view; 2.
to work around, in a way that produces unintended consequences
that are worse than the original problem. Usage: "Windows ME
fixes many of the shortcomings of Windows 98 SE". - Hutchison
Jul 22 '05 #9
> > > 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.

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.


C++ standard requires that the elements of a vector are stored contiguously.
To me that means that the standard requires implementations to use an array.

john
Jul 22 '05 #10

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

8 posts views Thread by Hal Vaughan | last post: by
11 posts views Thread by eggie2486 | last post: by
10 posts views Thread by Till Crueger | last post: by
11 posts views Thread by Walter Dnes (delete the 'z' to get my real address | last post: by
5 posts views Thread by Evangelista Sami | last post: by
9 posts views Thread by ashok.anbalan | last post: by
13 posts views Thread by Shutey | last post: by
18 posts views Thread by raylopez99 | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.