i need help making an infinite two dimensional array in c++, in other words, i have no clue how to do it....
can anyone help?
Name:
Anonymous2006-02-25 3:17
No such thing as infinite in computers!
Name:
Anonymous2006-02-25 3:36
Well, if some of the language constructs are lazily evaluated, there is such a thing. Haskell, for example, allows such things.
I can't imagine how you'd do it in C++ though. Create your own ADT that behaves like an array but is a hash or tree internally? Probably implemented in the same way as a sparse array.
Name:
Anonymous2006-02-25 3:44
he probably wants a linked list, shitheads.
Name:
Anonymous2006-02-25 3:51
If you are allowed to use the STL then the vector template is your best friend.
Otherwise just make a linked list of linked lists.
Name:
Anonymous2006-02-25 4:47
>>4
A single linked list is a poor fit for a 2D sparse array.
>>5
I'm not certain a vector is a good choice.
a) It can't handle arbitrary-length integers
b) Sucks for sparse arrays.
In general, to have an infinite array, you'll need a class that provides you an integer of arbitrary lengh, and some means of mapping that integer to whatever it is you've made your array out of (char, int, blue cheese, etc). Since it's obviously a sparse array, you'll need a linked list, tree, or hash to store this mapping.
It's not a real infinite array, but it looks like one, so long as you don't stuff too much actual data in it.
Name:
cvtc prof2006-02-27 12:07
what i would do is...
create a loopback where you increment the value of the first dimension by one every time that part of the program runs, then set it up so that the second dimensional value is reset whenever the first value is incremented...
also, cvtc user, instead of posting here, why not just ask me? that is what college professors are for.
P.S. mention this entry on the exam and i'll give you ten extra credit points
Name:
Anonymous2006-02-27 12:12
wtf
Name:
Anonymous2006-02-27 13:21
PWNED!!!
Name:
Anonymous2006-02-27 13:39
... go ask your tutors. they get paid to answer stupid questions like this.
how do i shot segmentation fault?
Name:
Anonymous2006-02-27 13:53
lol, it sux when your prof surfs the same boards as you
Name:
Anonymous2006-02-27 14:07
how do i shot segmentation fault?
kill -s SIGSEGV 22
Name:
Anonymous2006-02-28 4:57
FUCKING AL-CAP-OWNED
Name:
Anonymous2006-02-28 5:34
just use a <vector> instead? problem solved, AND it's dynamic. ^__^
The problem isn't 1D versus 2D. The problem is that vectors suck at sparse arrays, which is what you'll be using if you're trying to make a fake infinite array.
Also, vectors use ints for their index. If you can't go beyond 2^32 or 2^64 elements, that's not infinite now, is it?
Neither is the amount of memory available to any computer, what is your point?
Name:
Anonymous2006-03-06 19:37
>>36
One is a physical limitation put in place by the machine. The other is because you were sleeping through your lectures.
Of course it's not a real infinite array, but if you're trying to fake it, might as well get as close as possible. Are you telling me you've never dealt with integers larger than what your machine's word size will give you?
Name:
etatoby2006-03-09 17:53
WTF, am I the only one who understood the OP?
Seriously, these forums are turning to deeper and deeper shit every day.
OP: get a single integer index (i) from the two indices you have in your algorithm (x,y) such that it is a bijection (ie., for every (x,y) there exists only one (i) and vice-versa.) The simplest formula that comes to my mind is:
i = (x+y)*(x+y+1)/2+y
It's based on the same idea as that famous proof that the rationals are coutable (http://fyad.org/bl4y) and yes, that division right there is integer safe (x+y and x+y+1 are adjacent naturals, so one of them is even :-)
Then use that single index (i) as a key in a hash table. Use a good hash table, one that grows as the dataset grows, and you'll be allright.
For bonus points you could use bignums (=integers only limited by the available RAM) instead of plain ints for all the indices and their math, then you'd have a really infinite matrix!
To the trolls who are reading this, 'infinite' in CS means 'only limited by the available RAM', instead of by arbitrary limits (as the ±2 billion limit for common ints.)
Name:
Anonymous2006-03-09 22:00
WTF, am I the only one who understood the OP?
No, but you are one of the people who can't read.
That was an interesting post though. Please post more often.
>>38
>'infinite' in CS means 'only limited by the available RAM'
You had me going until this part. Subtle, Anon.
Name:
Anonymous2012-02-08 15:03
>>37
a 32 bit integer and an N bit integer bounded by RAM/hdd/whatever are both infinitely far from infinity, you're not any closer with the latter option.
In fact, might as well just store a single base 2 number since that is just "as close" as 1 trillion 2M bit numbers.