-1

I've been studying a bit on hash tables and how to create them with chaining in C++. In an example of code I found, the list and buckets are declared as follows:

int bucket;
std::list<int> *table;

Then, elsewhere in the program something like this is called:

table[bucket].push_back(1);

My question is, how come when declaring as *table I can use the bracket operator [] but if I declare it without the * then I can no longer use the bracket operator?

ex:

std::list<int> *table;
table[bucket].... OKAY

std::list<int> table;
table[bucket]... NOT OKAY

So when * is used, it's like there is a list at each bucket. so table[1] is a list, table[2] is another list. How are they achieving this by using *?

I've noticed I can do this with other types as well

ex:
int *test;
test[index]... OKAY

int test;
test[index]... NOT OKAY

this obviously has something to do with the pointer declaration but after countless reading and looking around, I can't seem to understand this. My thinking is that "std::list *table" creates a pointer to a list. But that doesn't clear anything up about how I am now able to use [].

Any clarification is greatly appreciated.

user11467841
  • 41
  • 1
  • 4
  • 1
    Oh this is so wrong. You have a pointer that does not point to anything. Then your `table[bucket]` is accessing an array of `std::list` that does not exist, going off into random memory somewhere. – Zan Lynx Oct 22 '19 at 03:08
  • 1
    https://stackoverflow.com/questions/26517164/why-am-i-being-told-that-an-array-is-a-pointer-what-is-the-relationship-between – Paul Rooney Oct 22 '19 at 03:08
  • I took the code from here: https://www.geeksforgeeks.org/c-program-hashing-chaining/ that might clarify a bit. – user11467841 Oct 22 '19 at 03:35

2 Answers2

2

"Pointer arithmetic" is the key concept to understand.

For std::list<int> table(†), table[1] is equivalent to *(table + 1). Conceptually, this is saying "look at the memory address pointed to by table. Look one sizeof(table) to the right, and give me the std::list<int> that's there.

(†) Or any type for that matter, but I've stuck with std::list<int> for consistency with your question.

So for an example, if we have the following:

const char* foo = "Hi!";

then the following are equivalent:

foo[2];
*(foo + 2);
*(2 + foo);
2[foo];
druckermanly
  • 2,694
  • 15
  • 27
  • thanks for the feedback. im trying to understand. so for something like table[5], is that saying "look at the memory address pointed to by table, with size of 5 tables to the right"? – user11467841 Oct 22 '19 at 03:36
  • Yes (and it returns the value that is the result of dereferencing the pointer at that address). As an aside, the site you linked in the "main" comment thread in your question... looks like a horrible place to learn, when measured in terms of quality-of-code. But that's just my highly subjective opinion. – druckermanly Oct 22 '19 at 03:46
1

A pointer can use the [] operator as if it were an array. That's why it compiles. However, your pointer is uninitialized, so accessing anything with it is undefined behavior. That's why it appears to work with a pointer.

The std::list class does not support random access and thus does not support the [] operator. That is why it doesn't compile when you don't define it as a pointer.

jkb
  • 2,376
  • 1
  • 9
  • 12
  • I wish I could give two people the credit. The first part of yours combined with the other response helped me understand this a lot more. I appreciate the help – user11467841 Oct 22 '19 at 03:53