473,327 Members | 1,967 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,327 software developers and data experts.

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 2584
"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 thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

2
by: Jason | last post by:
I have a number of arrays that are populated with database values. I need to determine which array has the highest ubound out of all the arrays. The array size will always change based on the...
8
by: Hal Vaughan | last post by:
Is there a maximum length for Javascript program lines? What about strings? Is there a limit on string length? I found some references that said the maximum string length was 256 characters,...
11
by: eggie2486 | last post by:
What is the maximum size of an array? I tried to edit an extremely large array for a magic square, for example, array, and when I ran the program, it would not display the array. I changed the...
10
by: Till Crueger | last post by:
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...
11
by: Walter Dnes (delete the 'z' to get my real address | last post by:
I've noticed a few threads (full of sound and fury, signifying nothing) here recently about allocation of large memory blocks. I'm about to start on a personal pet project where I'll be using...
5
by: Evangelista Sami | last post by:
hello is there a maximum size that can be allocated by a malloc call? is this defined by the standard? thanks Sami Evangelista
9
by: ashok.anbalan | last post by:
Hi, Can someone tell me if the language imposes any restrictions on the maximum number of arguments that can be passed via a function call? Thanks, Ashok
13
by: Shutey | last post by:
I have a strange issue with dropdowns. Using php4, mySQL5, Apache 2 on a fast XP pro PC, I have a form which requires 5 dropdowns populated with indentical values. I extract the values using SQL...
18
by: raylopez99 | last post by:
The maximum int for an array on my machine (a Pentium IV with 2 GB RAM) is < 330 Million...before you get an "out of memory" exception. I simply filled an array of this size with ints...I got as...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.