list class std::initializer_list constructor problem

Pages: 12
DragonOsman (715)
I need help with a std::initializer_list constructor for my custom list class. I got a "Access violation location <memory address here>" error on it inside the library code:
1
2
3
4
5
6
7
8
9
 
template<class _InIt,
	class _OutIt> inline
	_OutIt _Copy_unchecked1(_InIt _First, _InIt _Last,
		_OutIt _Dest, _General_ptr_iterator_tag)
	{	// copy [_First, _Last) to [_Dest, ...), arbitrary iterators
	for (; _First != _Last; ++_Dest, (void)++_First)
		*_Dest = *_First;
	return (_Dest);
	}


On this line of code:
*_Dest = *_First;

My code is in here: https://gist.github.com/DragonOsman/87a1e9fba06d49cab9b5b556c7dd31eb

I added some range checking to my ++ and -- operators, but what else do I need to do make the list iterator range-checked? And is the range-checking in those ++ and -- operators fine or do I need to something there?
Peter87 (11237)
std::copy just copies values from one range to another with the assumption that the range that you copy to is at least as long as the range that you copy from. It does not automatically extend the length of the list. You either have to make sure the list is long enough before calling std::copy or you could use std::back_inserter which will automatically call push_back for each value that is copied.

 
 
std::copy(lst.begin(), lst.end(), std::back_inserter(*this));

http://en.cppreference.com/w/cpp/iterator/back_inserter
Last edited on
DragonOsman (715)
Updated code: https://gist.github.com/DragonOsman/87a1e9fba06d49cab9b5b556c7dd31eb

This is giving me these errors:

1>c:\users\osman\programming\visual_studio_2017\projects\programming_principles_practice_using_c++\real_linked_list\real_linked_list\list.h(127): error C2244: 'list<Elem>::iterator::operator ++': unable to match function definition to an existing declaration
1>c:\users\osman\programming\visual_studio_2017\projects\programming_principles_practice_using_c++\real_linked_list\real_linked_list\list.h(126): note: see declaration of 'list<Elem>::iterator::operator ++'
1>c:\users\osman\programming\visual_studio_2017\projects\programming_principles_practice_using_c++\real_linked_list\real_linked_list\list.h(127): note: definition
1>c:\users\osman\programming\visual_studio_2017\projects\programming_principles_practice_using_c++\real_linked_list\real_linked_list\list.h(127): note: 'auto list<Elem>::iterator::operator ++(void)'
1>c:\users\osman\programming\visual_studio_2017\projects\programming_principles_practice_using_c++\real_linked_list\real_linked_list\list.h(127): note: existing declarations
1>c:\users\osman\programming\visual_studio_2017\projects\programming_principles_practice_using_c++\real_linked_list\real_linked_list\list.h(127): note: 'auto list<Elem>::iterator::operator ++(int)'
1>c:\users\osman\programming\visual_studio_2017\projects\programming_principles_practice_using_c++\real_linked_list\real_linked_list\list.h(127): note: 'auto &list<Elem>::iterator::operator ++(void)'
1>c:\users\osman\programming\visual_studio_2017\projects\programming_principles_practice_using_c++\real_linked_list\real_linked_list\list.h(137): error C2244: 'list<Elem>::iterator::operator --': unable to match function definition to an existing declaration
1>c:\users\osman\programming\visual_studio_2017\projects\programming_principles_practice_using_c++\real_linked_list\real_linked_list\list.h(136): note: see declaration of 'list<Elem>::iterator::operator --'
1>c:\users\osman\programming\visual_studio_2017\projects\programming_principles_practice_using_c++\real_linked_list\real_linked_list\list.h(137): note: definition
1>c:\users\osman\programming\visual_studio_2017\projects\programming_principles_practice_using_c++\real_linked_list\real_linked_list\list.h(137): note: 'auto list<Elem>::iterator::operator --(void)'
1>c:\users\osman\programming\visual_studio_2017\projects\programming_principles_practice_using_c++\real_linked_list\real_linked_list\list.h(137): note: existing declarations
1>c:\users\osman\programming\visual_studio_2017\projects\programming_principles_practice_using_c++\real_linked_list\real_linked_list\list.h(137): note: 'auto list<Elem>::iterator::operator --(int)'
1>c:\users\osman\programming\visual_studio_2017\projects\programming_principles_practice_using_c++\real_linked_list\real_linked_list\list.h(137): note: 'auto &list<Elem>::iterator::operator --(void)'
1>c:\users\osman\programming\visual_studio_2017\projects\programming_principles_practice_using_c++\real_linked_list\real_linked_list\list.h(147): error C2244: 'list<Elem>::const_iterator::operator ++': unable to match function definition to an existing declaration
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 declaration of 'list<Elem>::const_iterator::operator ++'
1>c:\users\osman\programming\visual_studio_2017\projects\programming_principles_practice_using_c++\real_linked_list\real_linked_list\list.h(147): note: definition
1>c:\users\osman\programming\visual_studio_2017\projects\programming_principles_practice_using_c++\real_linked_list\real_linked_list\list.h(147): note: 'auto list<Elem>::const_iterator::operator ++(void)'
1>c:\users\osman\programming\visual_studio_2017\projects\programming_principles_practice_using_c++\real_linked_list\real_linked_list\list.h(147): note: existing declarations
1>c:\users\osman\programming\visual_studio_2017\projects\programming_principles_practice_using_c++\real_linked_list\real_linked_list\list.h(147): note: 'auto list<Elem>::const_iterator::operator ++(const int)'
1>c:\users\osman\programming\visual_studio_2017\projects\programming_principles_practice_using_c++\real_linked_list\real_linked_list\list.h(147): note: 'auto &list<Elem>::const_iterator::operator ++(void)'
1>c:\users\osman\programming\visual_studio_2017\projects\programming_principles_practice_using_c++\real_linked_list\real_linked_list\list.h(157): error C2244: 'list<Elem>::const_iterator::operator --': unable to match function definition to an existing declaration
1>c:\users\osman\programming\visual_studio_2017\projects\programming_principles_practice_using_c++\real_linked_list\real_linked_list\list.h(156): note: see declaration of 'list<Elem>::const_iterator::operator --'
1>c:\users\osman\programming\visual_studio_2017\projects\programming_principles_practice_using_c++\real_linked_list\real_linked_list\list.h(157): note: definition
1>c:\users\osman\programming\visual_studio_2017\projects\programming_principles_practice_using_c++\real_linked_list\real_linked_list\list.h(157): note: 'auto list<Elem>::const_iterator::operator --(void)'
1>c:\users\osman\programming\visual_studio_2017\projects\programming_principles_practice_using_c++\real_linked_list\real_linked_list\list.h(157): note: existing declarations
1>c:\users\osman\programming\visual_studio_2017\projects\programming_principles_practice_using_c++\real_linked_list\real_linked_list\list.h(157): note: 'auto list<Elem>::const_iterator::operator --(const int)'
1>c:\users\osman\programming\visual_studio_2017\projects\programming_principles_practice_using_c++\real_linked_list\real_linked_list\list.h(157): note: 'auto &list<Elem>::const_iterator::operator --(void)'
1>c:\users\osman\programming\visual_studio_2017\projects\programming_principles_practice_using_c++\real_linked_list\real_linked_list\main.cpp(51): error C3779: 'list<int>::iterator::operator ++': a function that returns 'auto' cannot be used before it is defined
1>c:\users\osman\programming\visual_studio_2017\projects\programming_principles_practice_using_c++\real_linked_list\real_linked_list\list.h(32): note: see declaration of 'list<int>::iterator::operator ++'
1>c:\users\osman\programming\visual_studio_2017\projects\programming_principles_practice_using_c++\real_linked_list\real_linked_list\main.cpp(51): error C2088: '++': illegal for class
1>c:\users\osman\programming\visual_studio_2017\projects\programming_principles_practice_using_c++\real_linked_list\real_linked_list\main.cpp(58): error C3779: 'list<int>::iterator::operator ++': a function that returns 'auto' cannot be used before it is defined
1>c:\users\osman\programming\visual_studio_2017\projects\programming_principles_practice_using_c++\real_linked_list\real_linked_list\list.h(32): note: see declaration of 'list<int>::iterator::operator ++'
1>c:\users\osman\programming\visual_studio_2017\projects\programming_principles_practice_using_c++\real_linked_list\real_linked_list\main.cpp(58): error C2088: '++': illegal for class
1>c:\users\osman\programming\visual_studio_2017\projects\programming_principles_practice_using_c++\real_linked_list\real_linked_list\main.cpp(65): error C3779: 'list<int>::iterator::operator ++': a function that returns 'auto' cannot be used before it is defined
1>c:\users\osman\programming\visual_studio_2017\projects\programming_principles_practice_using_c++\real_linked_list\real_linked_list\list.h(32): note: see declaration of 'list<int>::iterator::operator ++'
1>c:\users\osman\programming\visual_studio_2017\projects\programming_principles_practice_using_c++\real_linked_list\real_linked_list\main.cpp(65): error C2088: '++': illegal for class


So what should I do? Would it better to put the definitions of the functions declared as auto inside of the class definition and then define list(std::initializer_list<Elem> lst) after those functions inside the class definition? And is that constructor fine now?
Peter87 (11237)
I don't think you can use auto in place of the return type when defining the function elsewhere because there is no way the compiler could figure out what return type the function should have by just looking at the function declaration. I think you'll either have to define them inside the class definition or write the types explicitly.
Last edited on
DragonOsman (715)
I heard from someone on MSDN that it's supposed to work in C++14.

But anyway, for the parameters of the member functions, the typename is only needed because you are referring to it in a way which is dependent on the template parameters.

If you remember that the class name is always injected into a class, even a template class, and any unqualified lookup will do a non dependent lookup on the current class name, then simply using:

1
2
 
template<typename Elem>
typename list<Elem>::iterator list<Elem>::insert(iterator p, const Elem &v);

will work. The return type is different though. The compiler doesn't do any looking ahead, so while it is reading the function declaration, it doesn't know what class, if any, it is a member of, so the unqualified lookup that was used with the parameters doesn't work, so while it is to the left of the function name then it will always require typename.

There are two ways in which you can deal with this. One of these needs C++11 and the other needs C++14. The first is return type deduction, this is the C++14 feature:

1
2
 
template<typename Elem>
auto list<Elem>::insert(iterator p, const Elem &v);

The compiler will deduce the return type and so you won't need to give the type, meaning you won't have to use typename.

The second is the trailing return type, this is the C++11 feature:
1
2
 
template<typename Elem>
auto list<Elem>::insert(iterator p, const Elem &v) -> iterator;

Because the return type is specified after the function name in this case, the compiler knows what class it can use to lookup unqualified names and so you don't need to use a template type name dependent way of looking up the name, this means you don't need to use typename.

So basically, if you are referring to members of your class, then you can avoid typename if you use the fact that unqualified names will look in the class associated with the member function.


I was trying to use that C++14 feature that person mentioned. Could you help me out with this if possible?
Last edited on
Thomas1965 (4571)
I think it has nothing to do with Visual Studio.
GCC 7.2 with C++17 enabled doesn't compile it either.
DragonOsman (715)
Eh, but it was a guy on MSDN Forums that said all that. Shouldn't that mean MSVC compiler should be able to compile that? I'll ask.
Peter87 (11237)
Ok, so it seems like it's possible after all. The error in your code has to do with inconsistent use of auto and auto& as return type.
DragonOsman (715)
Yeah, that's what it was. Thanks.

Now do you think you could help me out with range-checking in the list iterator?
Peter87 (11237)
So what do you want to happen when an iterators goes out of range? Throw an exception? Abruptly terminate the program with an error message?
DragonOsman (715)
Throw an exception.
Peter87 (11237)
You're already doing range-checking inside the ++ and -- operators so now you need to change it so that instead of doing nothing when the iterator is about to go out of range you instead throw an exception. std::out_of_range seems like an appropriate exception to throw.

1
2
3
4
5
6
7
8
9
10
 
template<typename Elem>
auto& list<Elem>::iterator::operator++()
{ 
	if (curr == nullptr)
	{
		throw std::out_of_range("list iterator incremented past the end of range");
	}
	curr = curr->succ;
	return *this; 
}


You might also want to do some range checking in operator* to make sure that the user is not trying to dereference the end() iterator.

I can see some minor mistakes here and there so make sure you test your code thoroughly.
DragonOsman (715)
Mistakes where? I've tested the insertion and deletion operations and the new constructor that takes an std::initializer_list (as well as the other constructors and the destructor) and seen that they work as intended, but could it be that they still have some problems? Or are you talking about other functions?

Here's the code from the ++ and -- operators after the changes:
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
 
template<typename Elem>
auto &list<Elem>::iterator::operator++()
{ 
	if (curr == nullptr)
	{
		throw std::out_of_range{ "list iterator out of range" };
	}
	curr = curr->succ;
	return *this; 
}

template<typename Elem>
auto &list<Elem>::iterator::operator--()
{ 
	if (curr == first && curr == nullptr)
	{
		throw std::out_of_range{ "list iterator out of range" };
	}
	curr = curr->prev;
	return *this; 
}

template<typename Elem>
auto &list<Elem>::const_iterator::operator++()
{
	if (curr == nullptr)
	{
		throw std::out_of_range{ "list iterator out of range" };
	}
	curr = curr->succ;
	return *this;
}

template<typename Elem>
auto &list<Elem>::const_iterator::operator--()
{
	if (curr == first && curr == nullptr)
	{
		throw std::out_of_range{ "list iterator out of range" };
	}
	curr = curr->prev;
	return *this;
}

template<typename Elem>
auto list<Elem>::iterator::operator++(int)
{ 
	auto ret = *this; 
	if (curr == nullptr)
	{
		throw std::out_of_range{ "list iterator out of range" };
	}
	curr = curr->succ;
	return ret; 
}

template<typename Elem>
auto list<Elem>::iterator::operator--(int)
{ 
	auto ret = *this; 
	if (curr == first && curr == nullptr)
	{
		throw std::out_of_range{ "list iterator out of range" };
	}
	curr = curr->prev;
	return ret; 
}

template<typename Elem>
auto list<Elem>::const_iterator::operator++(const int)
{ 
	auto ret = *this; 
	if (curr == nullptr)
	{
		throw std::out_of_range{ "list iterator out of range" };
	}
	curr = curr->succ;
	return ret; 
}

template<typename Elem>
auto list<Elem>::const_iterator::operator--(const int)
{ 
	auto ret = *this; 
	if (curr == first && curr == nullptr)
	{
		throw std::out_of_range{ "list iterator out of range" };
	}
	curr = curr->prev;
	return ret; 
}


Is it okay now? If so, what else can I do with the iterator to make it range-checked?

By the way, do you see problems in my const_iterator class and its functions? If so, what should I do there?

Also, do I need to check for curr->succ being nullptr in the ++ operator functions?
Last edited on
Peter87 (11237)
end() returns last->succ but that won't work if last == nullptr. An easy fix is to simply return nullptr directly (last->succ is always null anyway). Note that this implementation will not allow you to decrement the end iterator which is something that std::list and all the other standard containers allow you to do (except for std::forward_list).

If you call the decrement operator on an iterator you will get a compilation error because first is not accessible inside the iterator class. I think you should rethink the whole bounds checking condition for the decrement operators. You don't actually need to use the first pointer.

Your insert function has quite a few problems. It inserts the new element after the element that the iterator points to which makes it impossible to insert at the front of the list. Inserting at the end of the list also doesn't work.
Last edited on
DragonOsman (715)
The example in the book said to make it insert after the node pointed to by the passed in iterator. It's Programming: Principles and Practice Using C++ 2nd Edition, by Bjarne Stroustrup. I'm thinking of changing it to how it is in the standard library implementation of a linked list, though.

But yeah, I'll look into inserting at the end.

As for end(); I could just check if last is nullptr, right? But how do I allow it to be able to decrement from the end iterator? The standard library list's end() returns an iterator to "one-past-the-end", doesn't it?
DragonOsman (715)
Updated operator ++ and -- code:
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
 
template<typename Elem>
auto &list<Elem>::iterator::operator++()
{ 
	if (curr == nullptr)
	{
		throw std::out_of_range{ "list iterator out of range" };
	}
	curr = curr->succ;
	return *this; 
}

template<typename Elem>
auto &list<Elem>::iterator::operator--()
{ 
	if (curr == nullptr)
	{
		throw std::out_of_range{ "list iterator out of range" };
	}
	curr = curr->prev;
	return *this; 
}

template<typename Elem>
auto &list<Elem>::const_iterator::operator++()
{
	if (curr == nullptr)
	{
		throw std::out_of_range{ "list iterator out of range" };
	}
	curr = curr->succ;
	return *this;
}

template<typename Elem>
auto &list<Elem>::const_iterator::operator--()
{
	if (curr == nullptr)
	{
		throw std::out_of_range{ "list iterator out of range" };
	}
	curr = curr->prev;
	return *this;
}

template<typename Elem>
auto list<Elem>::iterator::operator++(int)
{ 
	auto ret = *this; 
	if (curr == nullptr)
	{
		throw std::out_of_range{ "list iterator out of range" };
	}
	curr = curr->succ;
	return ret; 
}

template<typename Elem>
auto list<Elem>::iterator::operator--(int)
{ 
	auto ret = *this; 
	if (curr == nullptr)
	{
		throw std::out_of_range{ "list iterator out of range" };
	}
	curr = curr->prev;
	return ret; 
}

template<typename Elem>
auto list<Elem>::const_iterator::operator++(const int)
{ 
	auto ret = *this; 
	if (curr == nullptr)
	{
		throw std::out_of_range{ "list iterator out of range" };
	}
	curr = curr->succ;
	return ret; 
}

template<typename Elem>
auto list<Elem>::const_iterator::operator--(const int)
{ 
	auto ret = *this; 
	if (curr == nullptr)
	{
		throw std::out_of_range{ "list iterator out of range" };
	}
	curr = curr->prev;
	return ret; 
}


If I can't access first in the iterator class, though, how come the compiler doesn't give an error when I use begin()?
Peter87 (11237)
The example in the book said to make it insert after the node pointed to by the passed in iterator. It's Programming: Principles and Practice Using C++ 2nd Edition, by Bjarne Stroustrup.

I don't have access to the book so I can't say much about it. I just think it's a weird design decision if you can't insert new elements at the beginning of the list using the insert function.

As for end(); I could just check if last is nullptr, right?

And if it is, what do you do then?

But how do I allow it to be able to decrement from the end iterator? The standard library list's end() returns an iterator to "one-past-the-end", doesn't it?

Yes, conceptually, that's how we can think about it. Exactly how it is done is up to the implementation.

GCC solves this problem by having an extra node that the end iterator points to. This extra node is stored as a member of the list class (it is not dynamically allocated) and they use some clever trick to avoid having any data attached to it (it's just two pointers). The extra node is not only connected to the last element's node but also to the first node in the list so it becomes a circular data structure. This means they can quickly access both ends of the list just using this extra node so they don't need any additional pointers to keep track of the beginning and end of the list. This not only solves the problem with decrementing the end iterator but it also makes it easier to implement reverse iterators and it requires less special handling when inserting and erasing at the beginning or end of the list.

I don't say you should necessarily do it this way, but if you do you might find it harder to do range checking because there is no easy way to check that you have reached the end of the list. You might be forced to store additional information inside the iterator.
Last edited on
Peter87 (11237)
Updated operator ++ and -- code:

You don't catch the situation when the decrement operator is used on an iterator that points to the first element.

If I can't access first in the iterator class, though, how come the compiler doesn't give an error when I use begin()?

The begin() function is part of the list so accessing first is not a problem.
Last edited on
DragonOsman (715)
In the ++ and -- operators, would it be better to get an iterator to begin() and end() (once I've fixed end())? That way I could check against begin() in the -- operator to know if I'm at the head of the list or not.

I don't want to do the GCC way given the complication of determining when I've reached of the list. So tell me an alternative.

As for what I said about last in relation to end():
1
2
3
4
5
6
7
8
9
 
template<typename Elem>
auto list<Elem>::end() const
{
    if (last == nullptr)
    {
        throw std::out_of_range{"list iterator out of range"};
    }
    return const_iterator(last->succ);
}


Like that?

I could allocate a node to represent the one-past-the-end node and assign 0 to it. Like it says in the book in these two exercises:
12. Complete the definition of list from §20.4.1–2 and get the high() example
to run. Allocate a Link to represent one past the end.
13. We don’t really need a “real” one-past-the-end Link for a list . Modify your
solution to the previous exercise to use 0 to represent a pointer to the
(nonexistent) one-past-the-end Link ( list<Elem>::end() ); that way, the size
of an empty list can be equal to the size of a single pointer.


If I do allocate a Link to represent the one-past-the-end node, what should I initialize it as (if I don't set it to 0)? Would new Link<Elem>(last->succ) be fine, or does that not make sense?
Last edited on
Peter87 (11237)
In the ++ and -- operators, would it be better to get an iterator to begin() and end() (once I've fixed end())?

Do you mean each iterator should contain two additional pointers? The way things are at the moment I don't think you need anything more to keep track of the beginning of the list. You already know that prev is nullptr for the first node. If the end() iterator points to a dummy node that is never used for anything other than being "one-past-the-end" you could store a pointer to it in each iterator, it should be safe as long as the nodes can't move between lists, but it might be unnecessary because if you have a one-past-the-end node you can always check the succ pointer to find out if the end has been reached.

As for what I said about last in relation to end():

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

I could allocate a node to represent the one-past-the-end node and assign 0 to it. Like it says in the book in these two exercises:

You could do as suggested in #12 and have a one-past-the-end node. #13 is how you have already done it. When they write 0 they mean a nullptr. Note that they are using singly-linked list so they don't have the problem of decrementing the end() iterator because you can only move forward in a singly-linked list, not backwards.

If I do allocate a Link to represent the one-past-the-end node, what should I initialize it as (if I don't set it to 0)?

The value doesn't matter. It should never be used.

Would new Link<Elem>(last->succ) be fine, or does that not make sense?

It makes sense. Another option would be to store it as a member of the class. That way you don't need to use new and delete.
Last edited on
Pages: 12