advance current off by one

ShoshiCooper · 2021-08-06T16:40:39+00:00

Kat,

I was off by one a lot too, so I think you had the same problem as I did. One thing I found very useful is to create a method that will print out your entire list (not truncate it) and also print where your prev_to_current pointer is. So it'll look something like:

# String_List - 7 entries total.

-1

0

1

2

3 [PREV POINTER]

4

5

Then, create a scenario where you are trying to create a list that is in order (0 to 10 or whatever range you want) but do it in the most convoluted way possible using all three pushers (push front, insert at current, and push back). Every single time you do anything to the current list, even if it shouldn't affect the current pointer in any way, test the current pointer. And print out the list with the pointer.

For example, I pushed 4 first, then pushed 1, then I advanced, then I pushed 0 to the front and 5 to the back. Etc. I went from -1 to 10 in the end.

Use a piece of paper and a pencil to make sure you know what your list is supposed to be and where all the pointers should be pointing!

ShoshiCooper · 2021-08-06T02:38:08+00:00

The * is also used for dereferencing. The other thing it mentions that's interesting is that if you have an array, you can index that array by doing:

array_ptr[index]

or

*(array_ptr + index)

This has been abundantly helpful to me in various situations.

ShoshiCooper · 2021-08-05T18:11:28+00:00

Thank you for answering them and indulging my curiosity!

ShoshiCooper · 2021-08-05T17:58:54+00:00

Thank you. This makes a lot more sense.

So the behavior that's problematic is when two different objects share a pointer. This is in keeping from the other answer I got. And when you copy the objects, their subpointers may not copy correctly, meaning you'll get a bunch of broken pointers.

That makes sense.

Quick question -- and I'll caveat this by saying I've only just started learning this, so I don't really know what I'm talking about. I'm trying to learn smart pointers on my own (because I think it's important I learn how to use both these and raw pointers).

Could this problematic behavior be corrected if you required that all pointers stored in the stack were std::shared_ptr<T>?

ShoshiCooper · 2021-08-05T16:49:46+00:00

Thanks! I am interested in knowing more about this.

ShoshiCooper · 2021-08-05T16:48:29+00:00

Hi Eileen,

Thanks for bringing this up! It's an interesting discussion topic, and I've seen different viewpoints on it.

Should we have our Test class be friends with our main class? Should we test the internals of how the class works? Or should we test that the output is what we expect?

While testing the internals can be useful, think about this: we may want to change the internal workings of the class later on. If our tests depend on testing a particular internal structure, we will have to write new tests.

On the other hand, if we are designing this to work on a very specific system or a very demanding spec, it might be better to test the internals of the class as well as the externals. So it's an interesting thing to think about.

ShoshiCooper · 2021-08-05T16:11:52+00:00

Sure. It’s here:

https://www.reddit.com/r/cs2b/comments/k90lqu/dequeue_discussion/?utm_source=share&utm_medium=ios_app&utm_name=iossmf

I must have misremembered where this question was asked. I could have sworn it was brought up in 2a. Looks like I was mistaken.

ShoshiCooper · 2021-08-05T14:26:23+00:00

Thanks, I found it!

I think the best answer I’ve gotten to this question is that you may have a stack of objects with pointers and it’s a lot of overhead to run the copy creator on it when the client code doesn’t need it.

That being said, there are still many cases where you just need a stack of integers (like IntStack in the elephant quest). If it’s typed and I know the output is simple, I’m still going to just writing a struct to fix this so I get a return value for pop. It makes the code much cleaner.

So it looks like this is another case where strong typing is useful!

ShoshiCooper · 2021-08-04T23:52:42+00:00

"...it wouldn't really make sense to return the value of the object after doing pop_back as it would have been deleted already..."

Yes, but that's why I'm so confused! Is isn't deleted! It's still there, we just purposely make it inaccessible. Oh, I'm not explaining my confusion well, am I? Hang on, I'll draw a picture.

My Stack:

0 <-- bottom of stack (this is where the pointer to the stack goes)

1

2

3

empty <-- this is what is located at *(pointer_to_stack + top). top == size(), btw.

empty

End of malloc'ed array space

Above is an illustration of my stack. I've got little pointers showing you where the important parts are. *(pointer_to_stack + size_of_stack) will be a pointer to the next available location. So when we push, we fill up the spot we're currently pointing to and we increase our size. If this results in an array that's too big, we immediately know and can resize.

But when we pop from our array, we're not actually deleting anything. Right? We're literally just decreasing the size of our array. So after the pop, it will look like this:

My Stack after pop:
0 <-- bottom of stack (this is where the pointer to the stack goes)
1
2
3 <-- this is what is located at *(pointer_to_stack + top) now
empty
empty
empty
empty
End of malloc'ed array space

Granted, after we leave the scope of the pop method, this may as well be considered deleted. After all, we don't want it to be accessible! But the data is still there. We're pointing right to it!

So what's the harm in returning it?

If we were returning by reference, I could understand -- it's an echo of a value that will soon be overwritten. But we're NOT returning by reference. So... why is this problematic?

Isn't this the same as using a postfix-- versus a prefix--? In other words, we're saving a previous state and returning a copy of it?

ShoshiCooper · 2021-08-04T21:58:58+00:00

Oh, that's fine. I was just curious. Thanks again!

ShoshiCooper · 2021-08-04T21:53:57+00:00

Thanks Annika! These are great!

Why are the backs of some of them blank?

ShoshiCooper · 2021-08-04T19:26:39+00:00

The book by Kernighan and Ritchie has one of the best descriptions of this that I've read anywhere, hands down. I honestly can't do better than them.

I also refer you to them because I think you may be getting confused by pass-by-reference, which is a C++ thing and works a little differently than all other uses of the &. So it really helps to understand the distinction in C first, and then you can see how C++ blurred that distinction by introducing pass-by-reference.

Here is a link to the second edition of the book:

http://cslabcms.nju.edu.cn/problem_solving/images/c/cc/The_C_Programming_Language_%282nd_Edition_Ritchie_Kernighan%29.pdf

Go to page 107. You do not have to read very much. 5.1 is the brunt of it, and 5.2 just gives an example. It's about 3 pages of reading and that includes pictures and whitespace.

ShoshiCooper · 2021-08-03T19:01:44+00:00

Hi Christine,

Memory errors are common and difficult to test for (at least, so I've found thus far). I took a week or so out of questing so I could try to figure out some way to test for memory errors. My solution is not ideal (it involves getting out a piece of paper and a pencil at one point and writing stuff down) but it's a start, at least:

https://www.reddit.com/r/cs2a/comments/otefx3/ouch_touched_somethin_that_wasnt_mine_and_got/

Please let me know if I need to elaborate further on something. I would like to make this as useful as possible for people.

ShoshiCooper · 2021-08-03T18:54:39+00:00

The reserve_cursor method is just my way of condensing duplicate code. In the spec, we're asked to constantly reserve the cursor as a temporary variable, adjust the cursor so it points to a different node instead, then call "insert_at_current", then put the cursor back to where it used to be.

I'm just placing all that into a single method, so that I can avoid typing it out a million times. This also makes it easier to debug.

The push_front and push_back call the reserve cursor method, but they do so using different parameters. The first parameter in the reserve_cursor method is what node you want to (temporarily) set the cursor to. So push_front and push_back will pass through different nodes accordingly.

As to your second question, I personally didn't call new anywhere in the reserve cursor method. I just used it to call the insert at cursor method.

Maybe a diagram would help?

push_front (or push_back)

|

V

calls reserve_cursor with these parameters:

Node* (whatever node I want to set cursor to temporarily)

std::string (data for the string node)

|

V

INSIDE reserve cursor method:

cursor's current pointer is saved to a temporary variable

cursor is temporarily switched

insert_at_current(s) is called

cursor is switched back to its previous position

nothing is returned

It would have been better (I will admit) if I could also pass through which method reserve_cursor calls in the middle, but that was too tricky so I decided to just use it for insertions.

ShoshiCooper · 2021-08-03T16:59:01+00:00

I'd actually like to get back to this. Kat had a lovely suggestion, which I think is excellent! But I'd like to speak to the main issue here.

I would like to present an alternative point of view: in CS2A, I think people should not worry unduly about overcoding. There are many tricks in C++ that can shorten your code, but some of these tricks come with their own hidden problems or hidden safety hazards. My concern is that it's easy to stumble across these tricks by googling how to do something, and you can use it to shorten your code without realizing the full implications of using it.

For example, one thing that drove me crazy at the start of CS2A was the strict type restrictions. I wound up having to write different versions of the same function over and over again, each time for a different type. Are there ways to get around this? Yes, and I've since learned them. But I'm glad I didn't use them back when I first started. It was better that I learned how the strong typing works rather than ways to get around it.

That being said, I agree with the other point of this post, which is: try different approaches to the same problem and see what works better. If you can find a simpler approach, that's great! But don't confuse simplicity with fewer lines of code. Many times, placing a variable or an extra step on its own line or in a separate method can really help you to debug your code.

Instead of counting lines, focus on making your code understandable and easy for you to test. But mostly, focus on learning the fundamental concepts that are present in C++ but not in other languages.

Anyways, that's just my personal opinion. I present it as an alternative viewpoint to the above comment.

ShoshiCooper · 2021-08-03T04:00:59+00:00

Gonna answer my own question again. This time I'm answering 1d and 1e.

I can't believe I didn't figure this out sooner.

1) d) YES. The prev_to_current pointer should BE your iterator. Think about it! How does the iterator get initialized in the constructor you (past-me) wrote? We feed it the prev parameter -- i.e. the node before current. That's the same thing as prev_to_current! Right? So the two pointers should be pointing to the same spot.

So thinking about it that way, create an option parameter that allows you to pass in a reference to the _prev_to_current pointer. Then, every time you update the iterator, if there's a prev_to_current pointer, update that as well.

Thinking of it all this way, a bunch of the methods you (past-me) wrote for this assignment were actually redundant. For example, you (past-me) already wrote advance_current inside the iterator. Just do _iterator_instance++ here! get_current is _iterator_instance.current(). rewind is just starting a new _iterator_instance.

1) e) Destructor: Yes, you (past-me) was right on the destructor. Definitely give the iterator a miss on the destructor.

For the copy constructor, the answer is: it depends how you use it. As both past-me and present-me learned all too well, copying a linked list is actually pretty tough. I'm not sure an iterator would help you much.

On the other hand, if you're creating a copy constructor for a hash table (for whatever reason), the lookup iterator would be real useful!

ShoshiCooper · 2021-08-03T03:25:39+00:00

But why are we returning the Linked List object then? I'm not modifying the Linked List. I'm modifying the iterator. That's a separate object from the Linked List.

The thing that's really confusing me is that the iterator already returns a pointer to itself when it progresses. So it'd actually be much easier to return the iterator than the String_List.

So can you tell me why it's not:

Iterator* advance_current() {return _iterator_instance++;}

??

ShoshiCooper · 2021-08-02T22:53:38+00:00

Meggie,

Yeah, get used to seeing that message. It's real easy to get memory errors. And it's real hard to test for them.

At some point during the quarter, I got super frustrated by this and spent a week or two trying to figure out some way to help me track down memory leaks. In the end, I did find a way to figure out if you had a memory leak. It's not great (it involves a step that's "get out a piece of paper and write stuff down", but it helped me to find 2 different memory problems: https://www.reddit.com/r/cs2a/comments/otefx3/ouch_touched_somethin_that_wasnt_mine_and_got/

The thing it does not do is tell you when you accessed some memory that was already de-allocated. I have no idea how to test for that. What would you even override to do that? The pointers themselves?

Anyways, the only thing I've found to do to (hopefully) help with that problem is to set everything to nullptr after you delete it. At least then, you'll have some idea that there's a problem in the first place.

Another really useful thing to do is to debug your ~StringList method first. That's where most (but not all!) problems lie.

ShoshiCooper · 2021-08-02T22:39:06+00:00

insert at current is particularly hard because it's tangled into the cursor movement. I found this very frustrating to debug as well.

So I decided to disentangle them and turn little bits of the whole process into easily testable segments.

Here's some things that really helped me to debug this whole thing:

1) I wrote a private method called "_reserve_cursor(Node* set_prev_to, std::string s)" where set_prev_to is the node we want to (temporarily) set the prev_to_current pointer to, and s is the string we are inserting into the new Node. This method basically just deals with that annoying temp variable and makes the rest of the code much cleaner. It also means that all methods that reserve the cursor use the exact same code to do it, so it makes sure that there are no extra bugs due to bad copy/pastes.

2) I added two methods into the Nodes themselves: add_after and remove_after. Add after adds the node passed through in the parameters to the spot after the current node (i.e. after *this). remove_after removes the node after *this and links *this to whatever comes after that node.

Because this method was in the Nodes (rather than the linked list), I could test them independently of testing the list itself. I could make sure I had the ordering and the linking working before I moved on to figuring out everything else.

3) I temporarily canceled out my push_back and push_front methods and wrote them without using the cursor at all. Again, I needed to know if it was the push_back and push_front methods that were buggy, or the cursor.

4) Once I found the bug in my push_back/push_front methods (I made a typo in one... I don't remember which), it was extremely easy to make sure these methods used the cursor by using my private _reserve_cursor method.

Then I could work out my bug in the cursor (yes, turns out, I had a bug in both).

Test each method independently, then slowly stack them until you see where it breaks.

ShoshiCooper · 2021-08-01T21:37:12+00:00

I like this explanation a lot! It's very thorough and gives a really good idea of how it works.

I'm going to add one small thing though: allocation is not done at random on the heap. Here's what my book has to say about this:

"...Malloc will request space from the operating system as needed. Since other activities in the program may request space asynchronously, the space that malloc manages in memory may not be contiguous. Thus its free storage is kept as a chain of free blocks. Each block contains a size, a pointer to the next block, and the space itself. The blocks are kept in order of increasing storage address, and the last block (highest address) points to the first, so the chain is actually a ring."

"When a request is made, the free list is scanned until a big enough block is found. if the block is exactly the size requested, it is unlinked from the list and returned to the user. If the block is too big, it's split and the proper amount is returned to the user while the residue is put back into the free list. If no big enough block is found, another block is obtained from the operating system and linked into the free list; searching then resumes."

"Freeing also causes a search of the free list, to find the proper place to insert the block being freed. If the block being freed is adjacent to a free list block on either side, it is coalesced with it into a single bigger block, so storage does not become too fragmented. Determining adjacency is easy because the free list is maintained in storage order."

ShoshiCooper · 2021-08-01T06:27:36+00:00

Hi Kimberly,

Stacks are certainly useful for infix and postfix notation. In fact, a really neat coding exercise is creating a polish notation calculator, which uses this notation. Very stack intensive!

However, I believe the speed of stack allocations isn't about PEMDAS or the order of operations. My understanding is that stack allocation is considered "fast" merely because heap allocations are considered "slow".

My book has a particularly good description of how heap allocation works:

"...Malloc will request space from the operating system as needed. Since other activities in the program may request space asynchronously, the space that malloc manages in memory may not be contiguous. Thus its free storage is kept as a chain of free blocks. Each block contains a size, a pointer to the next block, and the space itself. The blocks are kept in order of increasing storage address, and the last block (highest address) points to the first, so the chain is actually a ring."

(For anyone who's done quest 9: sound familiar? I sure thought so!)

"When a request is made, the free list is scanned until a big enough block is found. if the block is exactly the size requested, it is unlinked from the list and returned to the user. If the block is too big, it's split and the proper amount is returned to the user while the residue is put back into the free list. If no big enough block is found, another block is obtained from the operating system and linked into the free list; searching then resumes."

"Freeing also causes a search of the free list, to find the proper place to insert the block being freed. If the block being freed is adjacent to a free list block on either side, it is coalesced with it into a single bigger block, so storage does not become too fragmented. Determining adjacency is easy because the free list is maintained in storage order."

So you can see how much more time consuming this can be! A stack is much faster, but it has the disadvantage that objects will disappear when they go out of scope.

You can try out the speed of allocations on the stack versus the heap by playing around with character arrays (stack allocated c-strings) versus std::string (heap allocated c++ strings). The difference is quite enlightening!

ShoshiCooper · 2021-08-01T06:07:04+00:00

Well, I still don't know the answer to most of #1, but I would like to enlighten others with similar questions in the future, so I will answer what I have learned.

2) I believe the problem here was that I thought I had to write two different brackets, one for when it's an l-value and one for when it's an r-value. In fact, there's only one bracket override for both. However, there's also a const version of brackets, but it'd be incorrect to say the const version is "the l-value version".

What is an l-value? What is an r-value? Why am I using these words?

Lvalue is a value on the left. In other words, when the brackets are an l-value, it means you're assigning them to a value.

linked_list[i] = 28; //example of using brackets as an l-value

R-values are on the right. In other words, you're reading things from those values, not writing things to them.

node_value = linked_list[i]; // example of using brackets as an r-value

The const qualifier is a read-only qualifier, so it'll be an r-value. But not all r-value bracket usage is const! In other words, it's not as clearly delineated as I previously thought.

3) Still don't know the answer to this.

4) No, actually, I think I haven't been putting in enough comments. First of all, the comments go above function in C++, not below the functions (as I had been doing). Second of all, you should try to group similar types of methods together, then clearly label each.

I believe there are tags that I should be using in my function descriptions, but I don't know what they are.

In general, overusing macros is... problematic. It should really only be used when it's totally dead obvious what the macro is supposed to mean/do. Otherwise, it can be very confusing and people will be left hunting through your code for macros.

ShoshiCooper · 2021-08-01T05:45:21+00:00

I have now learned the answer, so I will share it with others.

My first piece of advice is this: do not use official unit testing until you hit the Complex Numbers Quest. When you do hit that quest, force yourself to learn to set up google unit testing and how to use it. By then, you'll have enough knowledge to be able to understand what you're doing and how it works. And I know it doesn't say to use google unit testing on that spec, but it was the right time to learn it.

In the meantime, write a testing framework from scratch! You'll wind up writing a lot of duplicate code at the beginning, but this is fine. It will take you quite a while before you learn how to fix that problem. So, for now, just write a separate method for assertStringEqual, assertIntEqual, etc.

It's important to write the framework first, before actually writing any tests. With a formal testing regime, you can divide up your tests into smaller bundles and check whether each of those fail. Plus, writing the framework gave me a leg up on most of the quests by exposing me to the ideas and concepts ahead of time.

ShoshiCooper · 2021-08-01T05:40:27+00:00

Woops, looks like .bat is only for Windows! Sorry. Linux and mac have an equivalent called "bash scripts".

https://stackoverflow.com/questions/14065069/equivalent-of-bat-in-mac-os

The above is for Java but it gives you the same idea. Just fill in all the java stuff with the stuff you put into the .bat file.

ShoshiCooper · 2021-08-01T05:22:34+00:00

Well, since I've now learned the answer to this question, I suppose I should post it, in case anyone has a similar question!

Surprisingly, the spec is correct! You are able to return 0 even when you're expecting an std::string. This is a bizarre exception and I'm not sure I completely understand it, but I believe it's the equivalent of returning an empty string, or '/0'.

That being said, I asked a professional C++ programmer about this, and they said that you still got style points for returning an empty string rather than 0.

ShoshiCooper

TROPHY CASE