Document program from PPP2 Chapter 20 - can't compile

[DragonOsman]

User code:

#include <iostream>
#include <fstream>
#include <list>
#include <vector>
#include "Document.h"

void print(Document &d);
void erase_line(Document &d, int n);
template<typename Iter>
void advance(Iter &p, int n);

int main()
{
	std::string str{ "hello world" };
	Document doc;
	doc.line.back.push_back(str);
	Text_iterator it = doc.begin();
	auto matched = it.find_txt(it, doc.end(), "hello");
	if (matched != doc.end())
	{
		std::cout << "Found\n";
	}
}

void print(Document &d)
{
	for (auto p : d)
	{
		std::cout << p;
	}
}

void erase_line(Document &d, int n)
{
	if (n < 0 || n >= d.line.size() - 1)
	{
		return;
	}
	auto p = d.line.begin();
	advance(p, n);
	d.line.erase(p);
}

template<typename Iter>
void advance(Iter &p, int n)
{
	while (n > 0)
	{
		++p;
		--n;
	}
	if (n < 0)
	{
		while (n < 0)
		{
			--p;
			++n;
		}
	}
}

Library code:

#ifndef DOCUMENT_H
#define DOCUMENT_H

#include <list>
#include <iostream>
#include <vector>

using Line = std::vector<char>;

struct Document
{
	std::list<Line> line;
	Document() { line.push_back(Line{}); }
	Text_iterator begin() { return Text_iterator(line.begin(), (*line.begin()).begin()); }
	Text_iterator end()
	{
		auto last = line.end();
		--last;		// we know know that the document is not empty
		return Text_iterator(last, (*last).end());
	}
};

class Text_iterator
	// keep track of line and character position within a line
{
	std::list<Line>::iterator ln;
	Line::iterator pos;
public:
	// start iterator at line ll's character position pp
	Text_iterator(std::list<Line>::iterator ll, Line::iterator pp)
		: ln{ ll }, pos{ pp } {}
	char &operator*() { return *pos; }
	Text_iterator &operator++();
	bool operator==(const Text_iterator &other) { return ln == other.ln && pos == other.pos; }
	bool operator!=(const Text_iterator &other) { return !(*this == other); }
	Text_iterator find_txt(Text_iterator first, Text_iterator last, const std::string &s);
	bool match(Text_iterator first, Text_iterator last, const std::string &str);
};

std::istream &operator>>(std::istream &is, Document &d);

#endif 

#include <algorithm>
#include <iostream>
#include <vector>
#include <list>
#include "Document.h"

std::istream &operator>>(std::istream &is, Document &d)
{
	char ch = ' ';
	for ( ; is.get(ch);)
	{
		d.line.back().push_back(ch);	// add the character
	}
	if (ch == '\n')
	{
		d.line.push_back(Line{});		// add another line
	}
	if (d.line.back().size())
	{
		d.line.push_back(Line{});		// add final empty line
	}
	return is;
}

Text_iterator &Text_iterator::operator++()
{
	++pos;		// proceed to the next character
	if (pos == (*ln).end())
	{
		++ln;	// proceed to the next line
		pos = (*ln).begin();	// bad if ln == line.end(); so make sure it isn't
	}
	return *this;
}

Text_iterator Text_iterator::find_txt(Text_iterator first, Text_iterator last, const std::string &s)
{
	if (s.size() == 0)
	{
		return last;
	}

	char first_char = s[0];
	while (true)
	{
		auto p = std::find(first, last, first_char);
		if (p == last || match(p, last, s))
		{
			return p;
		}
		first = ++p;
	}
}

bool Text_iterator::match(Text_iterator first, Text_iterator last, const std::string &str)
{
	if (str.empty())
	{
		return false;
	}
	
	for (char i = 0, j = *first; i < str.length(), j != *last; ++i, ++j)
	{
		if (i != j)
		{
			return false;
		}
	}
	return true;
}

I have 22 compiler errors with this. The first one is:

1>c:\users\osman\programming\visual_studio_2017\projects\programming_principles_practice_using_c++\document\document\document.h(14): error C3646: 'begin': unknown override specifier

Anyway, could someone please help me out here? Thanks in advance.

[kbw]

*line.begin() is a char
(*line.begin()).begin() is a what? char doesn't have begin().

[DragonOsman]

This is the code from the book:

struct Document {
    list<Line> line;
    Text_iterator begin() // first character of first line
    { return Text_iterator(line.begin(), (*line.begin()).begin()); }
    Text_iterator end() // one beyond the last character of the last line
    {
        auto last = line.end();
        ––last; // we know that the document is not empty
        return Text_iterator(last, (*last).end());
    }
};

I just copied the code from the book. And I'm pretty sure that's a std::vector<char>::begin().

Here are all of the errors:

1>c:\users\osman\programming\visual_studio_2017\projects\programming_principles_practice_using_c++\document\document\document.h(14): error C3646: 'begin': unknown override specifier
1>c:\users\osman\programming\visual_studio_2017\projects\programming_principles_practice_using_c++\document\document\document.h(14): error C2059: syntax error: '('
1>c:\users\osman\programming\visual_studio_2017\projects\programming_principles_practice_using_c++\document\document\document.h(14): error C2334: unexpected token(s) preceding '{'; skipping apparent function body
1>c:\users\osman\programming\visual_studio_2017\projects\programming_principles_practice_using_c++\document\document\document.h(15): error C3646: 'end': unknown override specifier
1>c:\users\osman\programming\visual_studio_2017\projects\programming_principles_practice_using_c++\document\document\document.h(15): error C2059: syntax error: '('
1>c:\users\osman\programming\visual_studio_2017\projects\programming_principles_practice_using_c++\document\document\document.h(16): error C2334: unexpected token(s) preceding '{'; skipping apparent function body
1>c:\users\osman\programming\visual_studio_2017\projects\programming_principles_practice_using_c++\document\document\main.cpp(16): error C2228: left of '.push_back' must have class/struct/union
1>c:\users\osman\programming\visual_studio_2017\projects\programming_principles_practice_using_c++\document\document\main.cpp(17): error C2039: 'begin': is not a member of 'Document'
1>c:\users\osman\programming\visual_studio_2017\projects\programming_principles_practice_using_c++\document\document\document.h(11): note: see declaration of 'Document'
1>c:\users\osman\programming\visual_studio_2017\projects\programming_principles_practice_using_c++\document\document\main.cpp(17): error C2512: 'Text_iterator': no appropriate default constructor available
1>c:\users\osman\programming\visual_studio_2017\projects\programming_principles_practice_using_c++\document\document\document.h(25): note: see declaration of 'Text_iterator'
1>c:\users\osman\programming\visual_studio_2017\projects\programming_principles_practice_using_c++\document\document\main.cpp(18): error C2039: 'end': is not a member of 'Document'
1>c:\users\osman\programming\visual_studio_2017\projects\programming_principles_practice_using_c++\document\document\document.h(11): note: see declaration of 'Document'
1>c:\users\osman\programming\visual_studio_2017\projects\programming_principles_practice_using_c++\document\document\main.cpp(18): error C2660: 'Text_iterator::find_txt': function does not take 2 arguments
1>c:\users\osman\programming\visual_studio_2017\projects\programming_principles_practice_using_c++\document\document\main.cpp(19): error C3536: 'matched': cannot be used before it is initialized
1>c:\users\osman\programming\visual_studio_2017\projects\programming_principles_practice_using_c++\document\document\main.cpp(19): error C2039: 'end': is not a member of 'Document'
1>c:\users\osman\programming\visual_studio_2017\projects\programming_principles_practice_using_c++\document\document\document.h(11): note: see declaration of 'Document'
1>c:\users\osman\programming\visual_studio_2017\projects\programming_principles_practice_using_c++\document\document\main.cpp(28): error C3312: no callable 'begin' function found for type 'Document'
1>c:\users\osman\programming\visual_studio_2017\projects\programming_principles_practice_using_c++\document\document\main.cpp(28): error C3312: no callable 'end' function found for type 'Document'
1>c:\users\osman\programming\visual_studio_2017\projects\programming_principles_practice_using_c++\document\document\main.cpp(29): error C2065: 'p': undeclared identifier
1>c:\users\osman\programming\visual_studio_2017\projects\programming_principles_practice_using_c++\document\document\main.cpp(35): warning C4018: '>=': signed/unsigned mismatch
1>Document.cpp
1>c:\users\osman\programming\visual_studio_2017\projects\programming_principles_practice_using_c++\document\document\document.h(14): error C3646: 'begin': unknown override specifier
1>c:\users\osman\programming\visual_studio_2017\projects\programming_principles_practice_using_c++\document\document\document.h(14): error C2059: syntax error: '('
1>c:\users\osman\programming\visual_studio_2017\projects\programming_principles_practice_using_c++\document\document\document.h(14): error C2334: unexpected token(s) preceding '{'; skipping apparent function body
1>c:\users\osman\programming\visual_studio_2017\projects\programming_principles_practice_using_c++\document\document\document.h(15): error C3646: 'end': unknown override specifier
1>c:\users\osman\programming\visual_studio_2017\projects\programming_principles_practice_using_c++\document\document\document.h(15): error C2059: syntax error: '('
1>c:\users\osman\programming\visual_studio_2017\projects\programming_principles_practice_using_c++\document\document\document.h(16): error C2334: unexpected token(s) preceding '{'; skipping apparent function body

It's skipping the function body because it can't recognize what "begin" is and is saying that the open paren there is a syntax error. I need to fix this error before it stops ignoring the function body.

[coder777]

Move the definition of Text_iterator before Document use it otherwise Document can't use anything from Text_iterator including the constructor.

[DragonOsman]

More errors after doing that:

1>c:\users\osman\programming\visual_studio_2017\projects\programming_principles_practice_using_c++\document\document\main.cpp(16): error C2228: left of '.push_back' must have class/struct/union
1>c:\users\osman\programming\visual_studio_2017\projects\programming_principles_practice_using_c++\document\document\main.cpp(35): warning C4018: '>=': signed/unsigned mismatch
1>Document.cpp
1>c:\users\osman\programming\visual_studio_2017\projects\programming_principles_practice_using_c++\document\document\document.cpp(62): warning C4018: '<': signed/unsigned mismatch
1>c:\program files (x86)\microsoft visual studio\2017\community\vc\tools\msvc\14.11.25503\include\xutility(984): error C2794: 'iterator_category': is not a member of any direct or indirect base class of 'std::iterator_traits<_InIt>'
1> with
1> [
1> _InIt=Text_iterator
1> ]
1>c:\program files (x86)\microsoft visual studio\2017\community\vc\tools\msvc\14.11.25503\include\xutility(3133): note: see reference to function template instantiation 'void std::_Debug_range<_InIt>(_InIt,_InIt,std::_Dbfile_t,std::_Dbline_t)' being compiled
1> with
1> [
1> _InIt=Text_iterator
1> ]
1>c:\users\osman\programming\visual_studio_2017\projects\programming_principles_practice_using_c++\document\document\document.cpp(46): note: see reference to function template instantiation '_InIt std::find<Text_iterator,char>(_InIt,_InIt,const _Ty &)' being compiled
1> with
1> [
1> _InIt=Text_iterator,
1> _Ty=char
1> ]
1>c:\program files (x86)\microsoft visual studio\2017\community\vc\tools\msvc\14.11.25503\include\xutility(984): error C2938: '_Iter_cat_t<Text_iterator>' : Failed to specialize alias template
1>c:\program files (x86)\microsoft visual studio\2017\community\vc\tools\msvc\14.11.25503\include\xutility(984): error C2062: type 'unknown-type' unexpected

Also include some harmless warnings, but please ignore those.

[DragonOsman]

Okay, now I have a Segfault being trigged in the find_txt function because of the match function. I'm having trouble stepping through the code in GDB without triggering the Segfault, the and VS debugger can't download the needed symbols right now. So I'm kind of stuck.

Document.h:

#ifndef DOCUMENT_H
#define DOCUMENT_H

#include <list>
#include <iostream>
#include <vector>
#include <iterator>

using Line = std::vector<char>;

struct Document
{
	std::list<Line> line;
	class Text_iterator : public std::iterator<std::bidirectional_iterator_tag, Line, Line, Line*, Line&>
		// keep track of line and character position within a line
	{
		std::list<Line>::iterator ln;
		Line::iterator pos;
	public:
		// start iterator at line ll's character position pp
		Text_iterator(std::list<Line>::iterator ll, Line::iterator pp)
			: ln{ ll }, pos{ pp } {}
		char &operator*() { return *pos; }
		Text_iterator &operator++();
		Text_iterator operator++(int n);
		bool operator==(const Text_iterator &other) { return ln == other.ln && pos == other.pos; }
		bool operator!=(const Text_iterator &other) { return !(*this == other); }
		Text_iterator find_txt(Text_iterator first, Text_iterator last, const std::string &s);
		bool match(Text_iterator first, Text_iterator last, const std::string &str);
	};
	Document() { line.push_back(Line{}); }
	Text_iterator begin() { return Text_iterator(line.begin(), (*line.begin()).begin()); }
	Text_iterator end()
	{
		auto last = line.end();
		--last;		// we know know that the document is not empty
		return Text_iterator(last, (*last).end());
	}
};

std::istream &operator>>(std::istream &is, Document &d);

#endif 

Document.cpp:

#include <algorithm>
#include <iostream>
#include <vector>
#include <list>
#include "Document.h"

std::istream &operator>>(std::istream &is, Document &d)
{
	char ch = ' ';
	for ( ; is.get(ch);)
	{
		d.line.back().push_back(ch);	// add the character
	}
	if (ch == '\n')
	{
		d.line.push_back(Line{});		// add another line
	}
	if (d.line.back().size())
	{
		d.line.push_back(Line{});		// add final empty line
	}
	return is;
}

Document::Text_iterator &Document::Text_iterator::operator++()
{
	++pos;		// proceed to the next character
	if (pos == (*ln).end())
	{
		++ln;	// proceed to the next line
		pos = (*ln).begin();	// bad if ln == line.end(); so make sure it isn't
	}
	return *this;
}

Document::Text_iterator Document::Text_iterator::operator++(int n)
{
	auto ret = *this;
	pos += n;
	if (pos == (*ln).end())
	{
		++ln;
		pos = (*ln).begin();
	}
	ret = *this;
	return ret;
}

Document::Text_iterator Document::Text_iterator::find_txt(Document::Text_iterator first, Document::Text_iterator last, const std::string &s)
{
	if (s.size() == 0)
	{
		return last;
	}

	char first_char = s[0];
	while (true)
	{
		auto p = std::find(first, last, first_char);
		if (p == last || match(p, last, s))
		{
			return p;
		}
		first = ++p;
	}
}

bool Document::Text_iterator::match(Document::Text_iterator first, Document::Text_iterator last, const std::string &str)
{
	if (str.empty())
	{
		return false;
	}
	
	for (char i = 0, j = *first; i < str.length() && j != *last; ++i, ++j)
	{
		if (i && j)
		{
			if (i != j)
			{
				return false;
			}
		}
	}
	return true;
}

main.cpp:

#include <iostream>
#include <fstream>
#include <list>
#include <vector>
#include "Document.h"

void print(Document &d);
void erase_line(Document &d, int n);
template<typename Iter>
void advance(Iter &p, int n);

int main()
{
	std::string str{ "hello world" };
	Document doc;
	for (int i = 0; i < str.length(); ++i)
	{
		doc.line.back().push_back(str[i]);
	}
	Document::Text_iterator it = doc.begin();
	auto matched = it.find_txt(it, doc.end(), "hello");
	if (matched != doc.end())
	{
		std::cout << "Found\n";
	}
}

void print(Document &d)
{
	for (auto p : d)
	{
		std::cout << p;
	}
}

void erase_line(Document &d, int n)
{
	if (n < 0 || n >= d.line.size() - 1)
	{
		return;
	}
	auto p = d.line.begin();
	advance(p, n);
	d.line.erase(p);
}

template<typename Iter>
void advance(Iter &p, int n)
{
	while (n > 0)
	{
		++p;
		--n;
	}
	if (n < 0)
	{
		while (n < 0)
		{
			--p;
			++n;
		}
	}
}

[coder777]

The problem is on line 18 in main.cpp. The vector doc.line is empty. On line 18 you try to access a not existing element. Try this:

	Document doc;
	doc.line.emplace_back(); // Note
	for (int i = 0; i < str.length(); ++i)
	{
		doc.line.back().push_back(str[i]);
	}

[DragonOsman]

Shouldn't that for loop fill the vector up? And I'm pretty sure emplace_back expects at least one argument (which I think should be a char in this case).

Edit: Also, I changed Document::Text_iterator::match to this to get rid of the vector iterator "non-dereference-able" error:

bool Document::Text_iterator::match(Document::Text_iterator first, Document::Text_iterator last, const std::string &str)
{
	if (str.empty())
	{
		return false;
	}
	
	for (Document::Text_iterator doc_it = first; doc_it != last; ++doc_it)
	{
		for (std::string::const_iterator str_it = str.begin(); str_it != str.end(); ++str_it)
		{
			if (doc_it == last)
			{
				break;
			}
			if (str_it == str.end())
			{
				break;
			}

			if (*str_it != *doc_it)
			{
				return false;
			}
		}
	}
	return true;
}

But now I get a debug assertion failure with the message being that the list iterator isn't dereference-able. What do I do now?

[coder777]

Line 13 (std::list<Line> line;) deceives you. It is not a line. It is actually a list of lines:

	Document doc;
	doc.list_of_lines.emplace_back(); // Note
	for (int i = 0; i < str.length(); ++i)
	{
		doc.list_of_lines.back().push_back(str[i]);
	}

Shouldn't that for loop fill the vector up?

Yes, but without the emplace_back() no line exists in the list which could be filled.

And I'm pretty sure emplace_back expects at least one argument (which I think should be a char in this case).

No, the emplace_back() creates an empty vector (line) that can be filled within the loop.

But now I get a debug assertion failure with the message being that the list iterator isn't dereference-able. What do I do now?

Where does this error occur?

Your match() function doesn't make sense. Change it like so:

bool Document::Text_iterator::match(Document::Text_iterator first, Document::Text_iterator last, const std::string &str)
{
	if (str.empty())
	{
		return false;
	}

	std::string::size_type i = 0;	
	Text_iterator doc_it = first;
	for (; doc_it != last; ++doc_it)
	{
		if(i < str.size())
		{
		  if(str[i] != *doc_it)
		    break;
		}
		else
		  break;
	}
	return (i == str.size()) && (doc_it == last); //Note && (doc_it == last) means full match
	// if you want to allow partial match remove that part
}

[DragonOsman]

It's saying it about the list iterator again after I made that change in main. I'll make that suggested change in match first and try it again. Thanks.

Edit: Just tried it. Another debug assertion failure; "vector iterator not dereferenceable", in the <vector> header on line 73. Last item on the call stack from my own code on the call stack is the Text_iterator operator* called after find_txt called std::find. And in the debugger, the code breaks on line 17 in this code (stdthrow.cpp):

/ throw -- terminate on thrown exception REPLACEABLE
#ifndef _M_CEE_PURE
#define _HAS_EXCEPTIONS 0
#endif /* _M_CEE_PURE */
#include <cstdio>
#include <cstdlib>
#include <exception>
#include <crtdbg.h>

_STD_BEGIN

#ifdef _DEBUG
_CRTIMP2_PURE void __CLRCALL_PURE_OR_CDECL _Debug_message(const wchar_t *message, const wchar_t *file, unsigned int line)
	{	// report error and die
        if(::_CrtDbgReportW(_CRT_ASSERT, file, line, NULL, L"%ls", message)==1)
        {
            ::_CrtDbgBreak();
        }
	}
_CRTIMP2_PURE void __CLRCALL_PURE_OR_CDECL _Debug_message(const unsigned short *message, const unsigned short *file, unsigned int line)
	{	// report error and die
        _Debug_message((wchar_t *) message, (wchar_t *) file, line);
	}

#endif

_STD_END

/*
 * Copyright (c) by P.J. Plauger. All rights reserved.
 * Consult your license regarding permissions and restrictions.
V6.50:0009 */

Here's my code:

#ifndef DOCUMENT_H
#define DOCUMENT_H

#include <list>
#include <iostream>
#include <vector>
#include <iterator>

using Line = std::vector<char>;

struct Document
{
	std::list<Line> line;
	class Text_iterator : public std::iterator<std::bidirectional_iterator_tag, Line, Line, Line*, Line&>
		// keep track of line and character position within a line
	{
		std::list<Line>::iterator ln;
		Line::iterator pos;
	public:
		// start iterator at line ll's character position pp
		Text_iterator(std::list<Line>::iterator ll, Line::iterator pp)
			: ln{ ll }, pos{ pp } {}
		char &operator*() { return *pos; }
		Text_iterator &operator++();
		Text_iterator operator++(int n);
		bool operator==(const Text_iterator &other) { return ln == other.ln && pos == other.pos; }
		bool operator!=(const Text_iterator &other) { return !(*this == other); }
		Text_iterator find_txt(Text_iterator first, Text_iterator last, const std::string &s);
		bool match(Text_iterator first, Text_iterator last, const std::string &str);
	};
	Document() { line.push_back(Line{}); }
	Text_iterator begin() { return Text_iterator(line.begin(), (*line.begin()).begin()); }
	Text_iterator end()
	{
		auto last = line.end();
		--last;		// we know know that the document is not empty
		return Text_iterator(last, (*last).end());
	}
};

std::istream &operator>>(std::istream &is, Document &d);

#endif 

#include <algorithm>
#include <iostream>
#include <vector>
#include <list>
#include "Document.h"

std::istream &operator>>(std::istream &is, Document &d)
{
	char ch = ' ';
	for ( ; is.get(ch);)
	{
		d.line.back().push_back(ch);	// add the character
	}
	if (ch == '\n')
	{
		d.line.push_back(Line{});		// add another line
	}
	if (d.line.back().size())
	{
		d.line.push_back(Line{});		// add final empty line
	}
	return is;
}

Document::Text_iterator &Document::Text_iterator::operator++()
{
	++pos;		// proceed to the next character
	if (pos == (*ln).end())
	{
		++ln;	// proceed to the next line
		pos = (*ln).begin();	// bad if ln == line.end(); so make sure it isn't
	}
	return *this;
}

Document::Text_iterator Document::Text_iterator::operator++(int n)
{
	auto ret = *this;
	pos += n;
	if (pos == (*ln).end())
	{
		++ln;
		pos = (*ln).begin();
	}
	ret = *this;
	return ret;
}

Document::Text_iterator Document::Text_iterator::find_txt(Document::Text_iterator first, Document::Text_iterator last, const std::string &s)
{
	if (s.size() == 0)
	{
		return last;
	}

	char first_char = s[0];
	while (true)
	{
		auto p = std::find(first, last, first_char);
		if (p == last || match(p, last, s))
		{
			return p;
		}
		first = ++p;
	}
}

bool Document::Text_iterator::match(Document::Text_iterator first, Document::Text_iterator last, const std::string &str)
{
	if (str.empty())
	{
		return false;
	}
	
	std::string::size_type i = 0;
	Text_iterator doc_it = first;
	for (; doc_it != last; ++doc_it)
	{
		if (i < str.size())
		{
			if (str[i] != *doc_it)
			{
				break;
			}
		}
		else
		{
			break;
		}
	}
	return (i == str.size()) && (doc_it == last);
}

#include <iostream>
#include <fstream>
#include <list>
#include <vector>
#include "Document.h"

void print(Document &d);
void erase_line(Document &d, int n);
template<typename Iter>
void advance(Iter &p, int n);

int main()
{
	std::string str{ "hello world" };
	Document doc;
	doc.line.emplace_back();
	for (int i = 1; i < str.length(); ++i)
	{
		doc.line.back().push_back(str[i]);
	}
	Document::Text_iterator it = doc.begin();
	auto matched = it.find_txt(it, doc.end(), "hello");
	if (matched != doc.end())
	{
		std::cout << "Found\n";
	}
}

void print(Document &d)
{
	for (auto p : d)
	{
		std::cout << p;
	}
}

void erase_line(Document &d, int n)
{
	if (n < 0 || n >= d.line.size() - 1)
	{
		return;
	}
	auto p = d.line.begin();
	advance(p, n);
	d.line.erase(p);
}

template<typename Iter>
void advance(Iter &p, int n)
{
	while (n > 0)
	{
		++p;
		--n;
	}
	if (n < 0)
	{
		while (n < 0)
		{
			--p;
			++n;
		}
	}
}