Thread: trouble with hash function implementing

Originally Posted by whiteflags

That is and always has been a horrible idea, as it forces the size of the array to be fixed...

Oh, but I mean, come on. Somethimes you use static arrays and sometimes dynamic arrays. Use whichever is best suited for the situation. If you are using static arrays, then most of the reason to dismiss the use of passing by reference goes away. It can most likely also catch bugs in your code where you incorrectly assume the size of the array.
If you are using dynamic arrays, then don't pass by reference. It's that simple. But use proper tools where appropriate.

and any code that uses such array references is forever incompatible with the STL, and several threads have been spent telling you such things.

I beg to differ. It works just as it should:

Code:

#include <string>
#include <iostream>
#include <algorithm>

#define SIZE(x) sizeof(x) / sizeof(x[0])

void foo(int (&arr)[10])
{
	int bar[SIZE(arr)];
	std::copy(arr, arr + SIZE(arr), bar);
	for (int i = 0; i < SIZE(bar); i++)
		std::cout << "bar[" << i << "]: " << bar[i] << std::endl;
}

int main()
{
	int _foo[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
	for (int i = 0; i < SIZE(_foo); i++)
		std::cout << "_foo[" << i << "]: " << _foo[i] << std::endl;
	foo(_foo);
}

Go on. Run it. It works as it should.

Originally Posted by whiteflags

You do know that this arr is not an array reference anymore?

Yes, I do. But the point is that I had a reference to an array and I was able to pass it to an STL algorithm without problems.
This debunks the whole "you can't use STL stuff if you have a reference to an array."

The worst thing about this suggestion is that it makes every thread about it into an argument. The only reason you advocate this is because you don't like to make size parameters, and this relieves you of the responsibility, but you cave in your own example, because even the STL forces it on you. You wouldn't be able to generate iterators without pointers and the size of the array.

No, I do not particularly like references to arrays. I much prefer using STL containers such as std::array and std::vector instead.
Last time, I mentioned it was a solution, not necessarily the best one.
This time, I am merely throwing out the fact that it's possible. I'd argue that the current code is broken, so it won't help either way. But it's still a fact that you can use references to pointers (instead of pointers to pointers) and references to arrays, too.

You're going against convention to prevent questionable errors.

Better safe than sorry. Every little possible mistake you can eliminate makes your code safer from mistakes.
It is not as if this takes 100x longer to implement. It takes very little time and prevents against mistakes, so what is the harm?


Btw, this suggestion will probably not improve your original code is any way due to how it is structured. But it might be worth experimenting with in future projects.

Both examples compile to an 10.5 KB executable for me.
Unless size is really hurting, I'd say this method is fine. Yes, if you are over-abusing it, it may turn into a disadvantage, but in most small projects that we see on this forum, I'd say it's good enough.
I do not deny there are other ways of doing this safely, though, but passing a size parameter is error prone unless you take measures against fixing that (say, take a custom size type that is only generated from a function call).

Like.
I must say though that I definitely don't like the way you've formatted that comma-separated list.

Code:

     int sData[] =
     {
       0,
       1,
       2,
       3,
       4,
       5,
       6,
       7,
       8,
       9,
     };

FTFY! (assuming we're not going to one-line it here).

Doh, I didn't notice that the rest was like that also.
It's really weird looking.

I thought I completely understood why we need to pass pointers to pointers, but then I remembered the name of an array is the constant pointer to the first index (NOT ptr to first elem). So that's why I thought if I pass by address (address of first index), that in order to access each item, I would dereference it. B/c the logic is with let's say a string array that holds either strings directly or string variables. When I just pass by address, it creates a new pointer that points to what the actual bucket (declared in main), so the address of first index. So that's why I don't see why it should be passing by ptr to ptr.

For the attached diagram I made, you can see the array name: bucket points to the first index, NOT the first item (which in this case is a pointer). So how does passing by ptr to ptr make it work is what I am unsure about. As is shown in the diagram attached, bucket_copy (if I had passed by address, so &bucket[0] or bucket), then it also points to address of first index. So why doesn't it work?

I thought we only pass by ptr to ptr is to actually modify the ptr (declared in main), so I wrote this print table program, so if I am just wish to access the elems in the array, which in this case, the elems happen to be pointers, why do I need to pass by ptr to ptr. I'm not modifying anything.

Please take a look at the attached diagram from my understanding of pointers and arrays. Why does the sc_print_table function have to be passed by ptr to ptr since the array name POINTS TO FIRST INDEX, NOT POINTS TO FIRST ITEM (which is a head pointer for that given bucket's doubly linked list). I also included a string list array, but for the print_list function, why can I just pass by address?

Code:

void print_list(string* list, size_t size )
{
    for ( size_t i = 0; i < size; ++i )
        cout << "Cur item: " << list[i] << ", ";
    cout << endl;
}

void sc_print_table(hockey_player* bucket, size_t size)
{
    cout << "PRINTING ENTIRE HASH TABLE..." << endl;
    
    for ( size_t i = 0; i < size; ++i )//for each index (aka: bucket in hash table jargon)
        for ( hockey_player* cur = bucket[i]; cur != NULL; cur = cur->next )//for each list for a given bucket
        {
            cout << "Cur player's bucket [" << i << "]" << endl;
            cout << "Cur player's num(key):[" << cur->num << "]" << endl;
            cout << "Cur player's name:[" << cur->name << "]" << endl;
            cout << "Cur player's team:[" << cur->team << "]" << endl;
            cout << endl;
        }
}

int main()
{
    hockey_player* p_1_front = NULL;//ptr to the itms in each bucket(ie. the address in each arr indx to a list)
    hockey_player* p_2_front = NULL;
    hockey_player* p_3_front = NULL;
    hockey_player* p_4_front = NULL;
    hockey_player* p_5_front = NULL;
    hockey_player* p_6_front = NULL;
    hockey_player* p_7_front = NULL;
    hockey_player* p_8_front = NULL;
    hockey_player* p_9_front = NULL;
    hockey_player* p_10_front = NULL;

    hockey_player* bucket[10] = {p_1_front, p_2_front, p_3_front, p_4_front, p_5_front, p_6_front, p_7_front, 
        p_8_front, p_9_front};

   sc_print_table(hockey_player* bucket, size_t size);//doesn't compile if not passed by ptr to ptr

   /**Another e.g.*/
   string a,b,c;
   a = "first";
   b = "second";
   c = "third";
   
   string list[5] = {a,b,c};

   size_t str_size = 3;

   print_list(list, str_size );
  
  return 0;
}

Or should I look at it as: for the string list array, we can pass by pointer (so array name w/ constant ptr to first item automatically) b/c I am dereferencing to actual content, whereas with the previous hockey_player* bucket array, if I just pass by address (by pointer so array's name), and I want to dereference, I should be accessing the indices content, but since the items in the bucket array are actually pointers, only a pointer to a pointer can access the pointer items?

Originally Posted by monkey_c_monkey

...

Boy, are you ever confused.

Arrays decay to a pointer to the first element. The reason to do this is because if you then do arithmetic on said pointer, you will compute addresses that correspond to where the next elements are. Creating a pointer to the first index doesn't really make sense. An index is just a number that means how many objects you had to skip over to get to some element.

Where your diagram is wrong: A correct depiction of bucket is a picture of an array of memory addresses. Those addresses point to all of the heads. The heads, which you painstakingly depicted as an array, aren't actually the array in question. There is no guarantee that the heads are stored one after the next like an array. The array is stored somewhere, and that is what you want to the pointee to be, so that when you dereference, you get the array element (a pointer), and so you can calculate the location of the next element. Pointers to pointers are therefore a necessity, because the type of thing you dereference is part of the pointer type.

B/c the logic is with let's say a string array that holds either strings directly or string variables.

An array element is an object as much as variables are. So if you create an array out of other pre-existing variables, you are actually copying those variables. You usually end up with two of the same thing.

Originally Posted by monkey_c_monkey

I thought we only pass by ptr to ptr whenever we need to actually change the address of some variable,

No, you are wrong.

You seem to keep forgetting that you have made an array of pointers. Every array type is different. Dude, you can do this:

Code:

void print_list_1(hockey_player* list[], size_t size)

The bracket syntax will allow you to correctly use an array of any type in a function. All you have to do is match your declaration. (It really doesn't matter - "hockey_player* list[]" in this context means "hockey_player** list" so you don't even really need to think.)

Finally this is what the C++ standard has to say on the topic:

Originally Posted by conv.array

An lvalue or rvalue of type “array of N T” or “array of unknown bound of T” can be converted to a [pure rvalue]
of type “pointer to T”. The result is a pointer to the first element of the array.

It says it right there. In this case, T is hockey_player*. Your compiler will back me up on this one, trust me. I don't know what a pointer to an index is, but that idea is clearly not helping you at all.