Like Tree2Likes

trouble with hash function implementing

This is a discussion on trouble with hash function implementing within the C++ Programming forums, part of the General Programming Boards category; Originally Posted by whiteflags That is and always has been a horrible idea, as it forces the size of the ...

  1. #16
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,587
    Quote Originally Posted by whiteflags View Post
    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.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  2. #17
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,689
    std::copy(arr, arr + SIZE(arr), bar);
    You do know that this arr is not an array reference anymore?

    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.

    You're going against convention to prevent questionable errors.

  3. #18
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,587
    Quote Originally Posted by whiteflags View Post
    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.
    Last edited by Elysia; 07-22-2012 at 08:14 AM.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  4. #19
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,689
    Quote Originally Posted by Elysia
    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?
    When I answer this, I hope you link to it, or something, so that other people can read it when you talk about it again. Also if you put it in your signature, I imagine it will be hard for you to forget about the huge downsides in the future.

    It causes code bloat. After fixing warnings, it compiles and comes up with an executable that is ~920 KB in size. Let's exacerbate the problem!

    Code:
    #include <string>
    #include <iostream>
    #include <algorithm>
    
    #define SIZE(x) sizeof(x) / sizeof(x[0])
    template <typename T, size_t N>
    void foo(T (&arr)[N])
    {
        int bar[N];
        std::copy(arr, arr + N, bar);
        for (size_t i = 0; i < N; i++)
            std::cout << "bar[" << i << "]: " << bar[i] << std::endl;
    }
    
    int main()
    {
        int _foo[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
        int _bar[20] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31};
        double _quz[4] = {1.1412, 3.1415, 1.618, 1.01234567801};
    
        for (size_t i = 0; i < SIZE(_foo); i++)
            std::cout << "_foo[" << i << "]: " << _foo[i] << std::endl;
        foo(_foo);
        for (size_t i = 0; i < SIZE(_bar); i++)
            std::cout << "_bar[" << i << "]: " << _bar[i] << std::endl;
        foo(_bar);
        for (size_t i = 0; i < SIZE(_quz); i++)
            std::cout << "_bar[" << i << "]: " << _quz[i] << std::endl;
        foo(_quz);
        return 0;
    }
    925 KB

    Code:
    #include <string>
    #include <iostream>
    #include <algorithm>
    
    #define SIZE(x) sizeof(x) / sizeof(x[0])
    template <typename T, size_t N>
    void foo(T (&arr)[N])
    {
        int bar[N];
        std::copy(arr, arr + N, bar);
        for (size_t i = 0; i < N; i++)
            std::cout << "bar[" << i << "]: " << bar[i] << std::endl;
    }
    
    int main()
    {
        int _foo[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
        int _bar[20] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31};
        double _quz[4] = {1.1412, 3.1415, 1.618, 1.01234567801};
        float _quuz[4] = {1.1412, 3.1415, 1.618};
        for (size_t i = 0; i < SIZE(_foo); i++)
            std::cout << "_foo[" << i << "]: " << _foo[i] << std::endl;
        foo(_foo);
        for (size_t i = 0; i < SIZE(_bar); i++)
            std::cout << "_bar[" << i << "]: " << _bar[i] << std::endl;
        foo(_bar);
        for (size_t i = 0; i < SIZE(_quz); i++)
            std::cout << "_bar[" << i << "]: " << _quz[i] << std::endl;
        foo(_quz);
        for (size_t i = 0; i < SIZE(_quz); i++)
            std::cout << "_bar[" << i << "]: " << _quz[i] << std::endl;
        foo(_quuz);
        return 0;
    }
    929 KB

    Now, I'm not sure, but eventually you can call this ridiculous. What sort of design has to get bigger for each wrinkle in the code? Every array type, and size means that you have to make a whole new function JUST to accommodate the reference type. The only way I changed the code in your original post was to reap the benefits of templates in making that less arduous. I think this ruins the usefulness of the idea though. Every other method of deducing N is less expensive in terms of space.

    You can use this technique at least a little smarter than what you're actually teaching people to do. If generating the size is really a concern, use this code to do that and nothing else -- follow convention for passing in sequences. Use two iterators or one iterator and a size parameter. Designing a whole program as lazily as this example is going to mean a huge exe in the end.

    The bad thing is that you will always pay the file size penalty. Maybe you just don't care but it's nothing to sneeze at. Mind you, the whole code bloat thing applies to templates just as much, but this is a particularly dumb use of code in the name of security. I wish I could wave the security wand and make all my poorly thought out designs OK.

  5. #20
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,587
    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).
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  6. #21
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    4,246
    O_o

    And, exactly as last time, the approach using iterators with the potential of convenience functions still wins by a wide margin.

    Soma

    Code:
    #include <algorithm>
    #include <iterator>
    #include <iostream>
    #include <vector>
    
    void Test
    (
        const int * fElement
      , const int * fTerminus
    )
    {
        using namespace std;
        vector<int> sData(fElement, fTerminus);
        copy(sData.begin(), sData.end(), ostream_iterator<int>(cout, "\n"));
    }
    
    template
    <
        typename FType
      , size_t FSize
    >
    void Test
    (
        const FType (&sData)[FSize]
    )
    {
        Test(sData, sData + FSize);
    }
    
    int main()
    {
        int sData[] =
        {
            0
          , 1
          , 2
          , 3
          , 4
          , 5
          , 6
          , 7
          , 8
          , 9
        };
        Test(sData);
        return(0);
    }
    iMalc likes this.

  7. #22
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,304
    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).
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  8. #23
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    4,246
    FTFY!
    O_o

    FTFM! (Fixed That For Me)

    There, I fixed that for you. ^_^

    In case you didn't notice, everything else is formatted in exactly the same way.

    Putting the operator first for statements breaching multiple lines has mechanical advantages. Consistency has greater value to me than convention. Styling one bit of code so differently from another that parses the same is repellent in my eyes. Beyond that, there is simply no need to do it differently unless I'm following the style others set for their convenience.

    Soma

  9. #24
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,304
    Doh, I didn't notice that the rest was like that also.
    It's really weird looking.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  10. #25
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,689
    Quote Originally Posted by phantomotap View Post
    Putting the operator first for statements breaching multiple lines has mechanical advantages.
    It does?

  11. #26
    Registered User
    Join Date
    Jul 2012
    Posts
    87
    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?
    Attached Images Attached Images  
    Last edited by monkey_c_monkey; 07-23-2012 at 03:00 PM.

  12. #27
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    4,246
    Doh, I didn't notice that the rest was like that also.
    Almost every example I've posted in the last 18 months have been written against this new style.

    It's really weird looking.
    I don't disagree.

    I also, for example, find prefixing variables with tags to be useless yet that is a large part of the new style.

    I used the old style in almost all code I wrote for public consumption for about six years. In that time I've listen to a lot of complaints about literally every common style in use just because some other style is "to be preferred". Because I could not possibly care less (I only care if style is meaningful, consistent, and imparts semantic value. If a style manages that the details aren't all that interesting.) I started playing with a new style that incorporates a lot of common strategies and a lot of complaints specifically so that all persons reading the code would find something to like about and something to complain about.

    Call it a hobby.

    It does?
    Code:
        condition1 &&
        (condition2 || condition3)
    Code:
        condition1
     && (condition2 || condition3)
    This is one situation where breaking before an operator imparts semantic meaning which reduces the time spent reasoning about existing code. Beyond situations like these the style is held to consistency. As I've said, I find inconsistency within the same source repellant.

    Soma

  13. #28
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,689
    Quote 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.
    Last edited by whiteflags; 07-23-2012 at 06:09 PM.

  14. #29
    Registered User
    Join Date
    Jul 2012
    Posts
    87
    Pointers to pointers are therefore a necessity, because the type of thing you dereference is part of the pointer type.
    Isn't is when you pass by address, a COPY of the address is created which means a new pointer that points to address of first item as the original bucket (see below code). So I'd think that doing: list[i] would would if the function below had been: void print_list_1_wrong(hockey_player* list, size_t size); b/c I thought as long as we are pointing to the correct first index, a newly created pointer to address of first index of bucket (array) would be able to have no trouble accessing the elems (which happens to pointers in this case). That's the part I'm stuck with.

    I thought we only pass by ptr to ptr whenever we need to actually change the address of some variable, ptr or not like with linked lists like insert new node at front, and so we MUST pass by ptr to ptr (I think there's an equivalent using references) in order to make the head ptr declared in main to point to new node. Otherwise if just ACCESSING items like in an array, passing by ptr (so passing by address (of first *elem* ) was sufficient which explains why the string list array below can just pass by ptr. I hope I'm making sense. If I get this, it'll make my day.

    Code:
    void print_list_1(hockey_player** list, size_t size)
    { 
      for ( size_t i = 0; i < size; ++i )
        cout << list[i] <<" , ";
      cout << endl;
    }
    
    int main()
    {
      hockey_player* head_1 = NULL;
      hockey_player* head_2 = NULL;
      hockey_player* head_3 = NULL;
      hockey_player* bucket[10] = {head_1, head_2, head_3};
      print_list_1(&bucket[0], 3);
      return 0;
    }
    (VS)

    Code:
    void print_list_2(string* list, size_t size)
    {
      for ( size_t i = 0; i < size; ++i )
        cout << list[i] << ", ";
      cout << endl;
    }
    
    int main()
    {
      string a,b,c;
      a = "first"; b = "second"; c = "third";
      string list[10] = {a,b,c};
      print_list_2(&list[0], 3);
      return 0;
    }

  15. #30
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,689
    Quote 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:
    Quote 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.
    Last edited by whiteflags; 07-24-2012 at 12:07 AM.

Page 2 of 3 FirstFirst 123 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Hash function to hash key into geographic coordinate
    By dominic_tran201 in forum C++ Programming
    Replies: 2
    Last Post: 02-11-2011, 09:03 AM
  2. trying to make a hash table......trouble w/ memory?
    By cuizy in forum C Programming
    Replies: 3
    Last Post: 05-11-2009, 04:47 PM
  3. A little trouble implementing a blur filter
    By omishompi in forum C++ Programming
    Replies: 2
    Last Post: 04-16-2006, 08:57 AM
  4. Having trouble implementing enumeration.
    By RP319 in forum C++ Programming
    Replies: 8
    Last Post: 03-02-2005, 06:03 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21