list class std::initializer_list constructor problem

Pages: 12
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:
1
2
3
4
5
6
7
8
9
10
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?
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.
Last edited on
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: http://www.pickinpatchfarm.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)?
Last edited on
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.
Last edited on
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?
Last edited on
Here's the updated Gist: http://www.pickinpatchfarm.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.
Last edited on
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.
Last edited on
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: http://www.pickinpatchfarm.com/DragonOsman/87a1e9fba06d49cab9b5b556c7dd31eb

Last edited on
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.
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.
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.
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():
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
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.
Last edited on
Registered users can post here. Sign in or register to post.
Pages: 12
<rt id="pwjBlLZ"><small id="pwjBlLZ"></small></rt>
<acronym id="pwjBlLZ"></acronym><rt id="pwjBlLZ"></rt>
<tr id="pwjBlLZ"><optgroup id="pwjBlLZ"></optgroup></tr><tr id="pwjBlLZ"><optgroup id="pwjBlLZ"></optgroup></tr><acronym id="pwjBlLZ"><small id="pwjBlLZ"></small></acronym>
<acronym id="pwjBlLZ"><optgroup id="pwjBlLZ"></optgroup></acronym>
<option id="pwjBlLZ"></option>
<tr id="pwjBlLZ"><optgroup id="pwjBlLZ"></optgroup></tr>
<acronym id="pwjBlLZ"><small id="pwjBlLZ"></small></acronym><acronym id="pwjBlLZ"></acronym>
<acronym id="pwjBlLZ"><small id="pwjBlLZ"></small></acronym>
  • 6512882421 2018-04-19
  • 4659652420 2018-04-19
  • 2967832419 2018-04-19
  • 8339042418 2018-04-19
  • 8147112417 2018-04-19
  • 2774752416 2018-04-19
  • 4316132415 2018-04-19
  • 6265742414 2018-04-19
  • 1875142413 2018-04-19
  • 4146552412 2018-04-19
  • 8205662411 2018-04-19
  • 959982410 2018-04-19
  • 7153742409 2018-04-19
  • 9349932408 2018-04-18
  • 6024052407 2018-04-18
  • 2113432406 2018-04-18
  • 7629172405 2018-04-18
  • 163882404 2018-04-18
  • 3515922403 2018-04-18
  • 5047802402 2018-04-18