list class std::initializer_list constructor problem

[DragonOsman]

The two exercises I referenced are talking about a doubly-linked list. They're talking completing the list I have now and then doing something to it.

For your first question. I was asking about having an iterator to the end to see if I've reached the end when incrementing, and having an iterator to the beginning to check if I've reached the beginning when decrementing.

This is what I was thinking with the above code:

template<typename Elem>
auto list<Elem>::end() const
{
    if (last == nullptr)
    {
        throw std::out_of_range{"list iterator out of range"};
    }
    Link<Elem> *one_past_end = new Link<Elem>(last->succ);
    return const_iterator(one_past_end);
}

But if I should have it as a member of the class instead, then I guess that's better since it'd avoid having to have an extra new and delete.

I don't think it's a good idea. It would prohibit the use of end() on an empty list.

So what would you suggest, then?

And since the one-past-the-end node would never be used, would it be okay to leave some garbage value stored in there? Or should I at set the node's value to the default value for whatever type it is?

[Peter87]

The two exercises I referenced are talking about a doubly-linked list.

OK, I just assumed it was a singly-linked list because they said "the size of an empty list can be equal to the size of a single pointer". So it's a doubly-linked list with no quick access to the end? This would make operations such as push_back() and pop_back() much slower.

Interestingly it seems like they ignore the problem of being able to decrement the end() iterator. It's not necessarily wrong but it's different from how the standard library work and something that would have to be clearly stated in the documentation if this was a real library.

This is what I was thinking with the above code: ...

I don't think you want to create a new one-past-the-end node each time end() is called. Who would clean it up and how would you know what to check for if you have multiple different one-past-the-end nodes?

So what would you suggest, then?

Just return the one-past-the-end iterator.

since the one-past-the-end node would never be used, would it be okay to leave some garbage value stored in there?

I think it's OK to not initialize in this case. Not that it makes much difference.

[DragonOsman]

I have quick access to begin and end. I do have pointers to the head and tail, after all. Stroustrup probably just said that about the size of an empty list for simplicity's sake. Not sure.

So I just have a member of the class that represents the one-past-the-end node and return that in the end() function? What did you say about prohibiting the use of end() on an empty list, though, and how do I fix that?

Edit: Update Gist: https://gist.github.com/DragonOsman/87a1e9fba06d49cab9b5b556c7dd31eb

I have this error on line 68:

1>c:\users\osman\programming\visual_studio_2017\projects\programming_principles_practice_using_c++\real_linked_list\real_linked_list\list.h(68): error C2187: syntax error: '{' was unexpected here

I don't get why, though? I mean, I'm trying to use uniform initialization, and even have the compiler switch for C++14 turned on. What am I doing wrong there and how do I fix it?

And what else am I doing wrong aside from (assuming there's still something wrong, which there might be)?

[Peter87]

So I just have a member of the class that represents the one-past-the-end node and return that in the end() function?

Yes, you return an iterator that points to that node.

What did you say about prohibiting the use of end() on an empty list, though, and how do I fix that?

If you throw an exception in end() when last == nullptr (which is when the list is empty) you are not allowing iterators to be used on an empty list. I mean, wouldn't you expect std::sort(a.begin(), a.end()) to work even if a is empty? Of course a would be left unmodified in this case because an empty list is always sorted. Note that begin() should return the same as end() on an empty list for this to work. The easiest way to handle this is probably to initialize the first pointer to point to the one-past-the-end node when constructing an empty list.

I have this error on line 68

You should not mention the names of the members of the object that you're initializing. The compiler uses the order of the values to figure out which member should get which value. Using one_past_end{last, nullptr} should be enough. This should work if one_past_end is a Link object (why is it a pointer?).

And what else am I doing wrong aside from (assuming there's still something wrong, which there might be)?

Not wrong, but to avoid having to update the last pointer you could simply remove it and use one_past_end->prev instead. It's just a thought.

[DragonOsman]

I like having an actual pointer pointing to the last node. So I'll keep last. The one_past_end node is a pointer because the list class is using Link pointers as nodes. Why, is that not good?

I'll make the changes you mentioned for begin and end.

Edit: Actually, I already took out that check in end(). I had it in begin(), but should I keep that or take it out?

[DragonOsman]

Here's the updated Gist: https://gist.github.com/DragonOsman/87a1e9fba06d49cab9b5b556c7dd31eb

I have these build messages:

1>------ Build started: Project: real_linked_list, Configuration: Debug Win32 ------
1>main.cpp
1>c:\users\osman\programming\visual_studio_2017\projects\programming_principles_practice_using_c++\real_linked_list\real_linked_list\list.h(147): error C2327: 'list<int>::one_past_end': is not a type name, static, or enumerator
1>c:\users\osman\programming\visual_studio_2017\projects\programming_principles_practice_using_c++\real_linked_list\real_linked_list\list.h(146): note: see reference to function template instantiation 'auto &list<int>::iterator::operator ++(void)' being compiled
1>c:\users\osman\programming\visual_studio_2017\projects\programming_principles_practice_using_c++\real_linked_list\real_linked_list\main.cpp(50): note: see reference to function template instantiation 'Iter high<list<int>::iterator>(Iter,Iter)' being compiled
1> with
1> [
1> Iter=list<int>::iterator
1> ]
1>c:\users\osman\programming\visual_studio_2017\projects\programming_principles_practice_using_c++\real_linked_list\real_linked_list\main.cpp(42): note: see reference to class template instantiation 'list<int>' being compiled
1>c:\users\osman\programming\visual_studio_2017\projects\programming_principles_practice_using_c++\real_linked_list\real_linked_list\list.h(147): error C2065: 'one_past_end': undeclared identifier
1>Done building project "real_linked_list.vcxproj" -- FAILED.
========== Build: 0 succeeded, 1 failed, 0 up-to-date, 0 skipped ==========

Please help me fix this and then let me know if there's anything else that's sloppy or whatnot (is one_past_end being a pointer sloppy?).

Edit: How do I make sure that my ++ operators don't go past the last node? I can't use one_past_end in there because it's not a member of list::iterator.

[Peter87]

The one_past_end node is a pointer because the list class is using Link pointers as nodes. Why, is that not good?

No, the Link objects are the nodes. If one_past_end is a pointer you still have to create the node and make one_past_end point to it. It's much easier to simply make it a Link object because then it will be created and destroyed automatically together with the list. To get a pointer to it you can just use the & operator.

I'll make the changes you mentioned for begin and end. [...] I had it in begin(), but should I keep that or take it out?

Take it out. You want to allow begin() to be called on an empty list in which case it should return the same as end().

How do I make sure that my ++ operators don't go past the last node? I can't use one_past_end in there because it's not a member of list::iterator.

Now that you are using the one-past-the-end node you only need to check if curr->succ is null, nothing more.

[DragonOsman]

Does what you said about the one_past_end node still apply if I'm not using new to allocate memory for it? I mean, all of my other nodes are also pointers to Links.

For clarification and reference, here's what I have now: https://gist.github.com/DragonOsman/87a1e9fba06d49cab9b5b556c7dd31eb

[Peter87]

The pointers are not nodes. The nodes are the objects that the pointers point to.

You haven't gained anything by just creating a one-past-the-end pointer. You need an actual node (Link<T>) object so that you can traverse back to the previous node when the end() iterator is decremeted.

[DragonOsman]

So there are imaginary nodes that the pointers are pointing to? Because I only made pointers to them.

But as for traversing back to the previous node from one_past_end: I tried that and saw that I actually can do it. Look at my user code on the Gist. That does actually work.

[Peter87]

So there are imaginary nodes that the pointers are pointing to? Because I only made pointers to them.

Link<Elem> *new_node = new Link<Elem>;

The right hand side of the assignment operator creates a new Link<Elem> object and returns an address to it. The address is then assigned to the new_node pointer. The result is that new_node now points to the newly created Link<Elem> object.

But as for traversing back to the previous node from one_past_end: I tried that and saw that I actually can do it. Look at my user code on the Gist. That does actually work.

It's not guaranteed to work. It's what's called undefined behaviour. When I run your program with optimizations turned off it seems to work all right but with optimizations turned on it crashes immediately with a segfault.

[DragonOsman]

I made it a regular a node. But I don't get how to fix insert() now, in the case when it has to insert the new node after the last node. I had a memory leak, too, last I checked.

Here's the code for insert():

template<typename Elem>
auto list<Elem>::insert(iterator p, const Elem &v)
{
	Link<Elem> *new_node = new Link<Elem>;
	new_node->val = v;
	new_node->prev = nullptr;
	new_node->succ = nullptr;
	
	if (first == nullptr)
	{
		first = new_node;
		last = first;
		last->succ = &one_past_end;
		one_past_end.prev = last;
		num_nodes++;
		return iterator(new_node);
	}
	else if (p.current_link())
	{
		new_node->prev = p.current_link();
		new_node->succ = p.current_link()->succ;
		p.current_link()->succ = new_node;
		new_node->succ->prev = new_node;
		if (!p.current_link()->succ || p.current_link() == last)
		{
			last = new_node;
			last->succ = &one_past_end;
			one_past_end.prev = last;
		}
		num_nodes++;
		return iterator(new_node);
	}
	return p;
}

I'll change this to insert before and add an inserting function called add() to insert after the current node later, but for now I just want this working. So anyway, what condition should I use to check (on line 24 in the above code)? Is it fine the way it is now? It was leaking when the condition was if (!new_node->succ), but with the current conditional check there are no leaks at least. But is it fine aside from that as well or could there be other problems?

Also, as you read the code, do you think there are any operations missing here that I should add before the list class is truly complete? Aside from a move constructor and move assignment. I was thinking of adding sorting and searching functions later if I could figure how to do the sorting for a linked list. And I was also thinking of adding a reverse iterator and a const version of that, as well (though I don't know what the latter one should be called (the class name, I mean)). I just know that the begin and end functions should rbegin and rend for the reverse ones and crbegin and crend for the const reverse ones. But anything else missing? Note: I do want to add move semantics, too.

[Peter87]

When the list is empty both last and first should already be pointing to one_past_end (unless you want to make it more difficult than necessary) so you shouldn't need to handle the special case when the list is empty. What you should instead do is handle the special case when an element is inserted at the front in which case you need to update the first pointer. Similarly you also need to handle the case when an element is inserted at the end.

I think I might have mentioned this earlier but I do it again because I think you might have missed it. Since you are doing range checking for your iterators I think you should also do it in the dereference operator (operator*). I'm thinking of the case when the iterator is not dereferenceable because it points one-past-the-end.

[DragonOsman]

Don't I have to point first and last at one_past_end?

Right now it's still inserting after the current node, so I don't need to worry about a node being insert at the front.

Edit: Just made the changes (aside from the check for the iterator being dereferenceable; I'll do that later). https://gist.github.com/DragonOsman/87a1e9fba06d49cab9b5b556c7dd31eb

For now I need help with the constructor that has the signature list(size_type count); inside the class definition.

This is the output I have now:

Visual Leak Detector read settings from: C:\Program Files (x86)\Visual Leak Detector\vld.ini
Visual Leak Detector Version 2.5.1 installed.
100
200
300
400
500
|
Size of lst2 is 1
lst2:
0
lst in reverse:
100
200
300
400
500
The highest value was 500
Please enter a character to exit
l
No memory leaks detected.
Visual Leak Detector is now exiting.
Press any key to continue . . .

There's only one node in lst2. So how do I define that constructor so that it inserts count number of nodes with the default value?

[Peter87]

Don't I have to point first and last at one_past_end?

Yes, in the constructor.

Right now it's still inserting after the current node, so I don't need to worry about a node being insert at the front.

OK, that means you can't use the insert function to insert to an empty list or at the front of the list. What should the function do if someone pass in the end() iterator?

For now I need help with the constructor that has the signature list(size_type count); inside the class definition.

The easiest way would be to call one of your insert functions (e.g. push_back) in a loop count number of times.

[DragonOsman]

I'll try to test with an empty list and see what happens. But on that note, when I do want to change it to insert before the current node, how should I change this part?
new_node->succ->prev = new_node; Should it be changed to new_node->prev->succ = new_node;?

Edit: Okay, here's that constructor:

template<typename Elem>
list<Elem>::list(typename list<Elem>::size_type count)
	: first{ nullptr }, last{ nullptr }, one_past_end{ last, nullptr }, num_nodes{ 0 }
{
	first = &one_past_end;
        last = first;
        for (size_type i = 0; i < count; ++i)
	{
		Link<Elem> *new_node = new Link<Elem>;
		new_node->prev = nullptr;
		new_node->succ = nullptr;
		new_node->val = Elem{};
		push_back(new_node);
	}
}

And I changed the default constructor to this (but that's all I could think of for now):

list()
	: first{ nullptr }, last{ nullptr }, one_past_end{ last, nullptr }, num_nodes{ 0 }
{
	first = &one_past_end;
	last = first;
}

What other constructor needs it?

This is my insert() right now:

auto list<Elem>::insert(iterator p, const Elem &v)
{
	Link<Elem> *new_node = new Link<Elem>;
	new_node->val = v;
	new_node->prev = nullptr;
	new_node->succ = nullptr;
	
	if (first == &one_past_end && last == &one_past_end)
	{
		first = new_node;
		last = first;
		last->succ = &one_past_end;
		one_past_end.prev = last;
		num_nodes++;
		return iterator(new_node);
	}
	else if (p.current_link())
	{
		new_node->prev = p.current_link();
		new_node->succ = p.current_link()->succ;
		p.current_link()->succ = new_node;
		new_node->succ->prev = new_node;
		if (!p.current_link()->succ || p.current_link() == last)
		{
			last = new_node;
			last->succ = &one_past_end;
			one_past_end.prev = last;
		}
		num_nodes++;
		return iterator(new_node);
	}
	return p;
}

This should work for an empty list, too, right? If I can make sure that first == &one_past_end and last == first always hold true for an empty list (how?).

Edit: The list(size_type count) constructor isn't even being called. It calls the initializer_list constructor instead, and then crashes because last is nullptr (it crashes on the last->succ = new_node; line, and triggers a breakpoint with the message saying that **last** is nullptr). I fixed that by putting this code in push_back:

if (num_nodes == 0)
{
	first = &one_past_end;
	last = first;
}

but now it freezes after calling the destructor and a breakpoint is triggered in this code:

//
// delete_scalar.cpp
//
//      Copyright (c) Microsoft Corporation. All rights reserved.
//
// Defines the scalar operator delete.
//
#include <crtdbg.h>
#include <malloc.h>
#include <vcruntime_new.h>



void __CRTDECL operator delete(void* const block) noexcept
{
    #ifdef _DEBUG
    _free_dbg(block, _UNKNOWN_BLOCK);
    #else
    free(block);
    #endif
}

on line 17.

[DragonOsman]

I went back to having end() be nullptr. I was having trouble with the other way.

Now I'm trying to implement a reverse_iterator for the list class. Updated Gist: https://gist.github.com/DragonOsman/87a1e9fba06d49cab9b5b556c7dd31eb

The output is like this:

Visual Leak Detector read settings from: C:\Program Files (x86)\Visual Leak Detector\vld.ini
Visual Leak Detector Version 2.5.1 installed.
100
200
300
400
500
|
Size of lst2 is 1
lst2:
0
lst in reverse:
100
200
300
The highest value was 500
Please enter a character to exit
k
No memory leaks detected.
Visual Leak Detector is now exiting.
Press any key to continue . . .