I need a linked list expert !!!!!!!

Started by
32 comments, last by Jouei 16 years, 10 months ago
Quote:Original post by Jouei
The following code here!

http://www.hexdollhosting.com/MapLoader.txt


0) HTML code for links works on this forum.

1) Don't link to code off-site unless it's *really* long (I'm talking thousands of lines) - and even then, you should try to create a smaller example for demonstration instead. Longish code snippets go in [source]
[/source] tags within your post, as shown below. Shorter snippets can go between [code][/code] tags.

(EDIT: Editing the post unescaped the tags, so I had to re-edit to re-escape them. Grr.)

2) You can hit 'edit post' on my post to see how this stuff works (it won't let you save any edits, of course). But you're supposed to have looked this stuff up in the FAQ anyway.

Quote:Was designed to load in a map for 3d purposes it seems to work fine execept for one large problem.


Strange turn of phrase there :)

Anyway, I can hardly make any sense of the rest of what you wrote, but I'd have to agree with what jpetrie said. The best "linked list expert" to help you is the one who wrote a linked list for you and shipped it with your compiler.

But while we're on the topic of things being outdated: There is no such thing as 'stdio.h' in C++ any more (it's called 'cstdio' now), and if you're going to include 'fstream', you might consider using it - FILE* is horrible, arcane C hackery that is actually coming from stdio.h (because your compiler is letting you use C headers); fstream provides things like the std::ifstream class instead.

Also, C++ doesn't make you assign structs member-by-member. You can just assign the struct instances directly, for simple structures. For more complicated ones, you can explain to the compiler how to do it (i.e., overload an assignment operator), and then continue as before. Although, with proper use of the standard library, it is unusual to make "more complicated ones". :)

(Oh, and the singular of 'vertices' is 'vertex'.)

#include <windows.h>// We won't need stdio.h - or cstdio - any more.// But we will need these:#include <list>#include <string>#include <sstream>#include <iostream>#include <fstream>using namespace std;bool DisplaySector(int ID);struct Vertex {	float x;	float y;	float z;	float Tx;	float Ty;	// In C++, structs and classes are interchangeable: it's just syntactic	// sugar ('struct' simply means a 'class' where 'public:' is assumed for	// base classes and members unless otherwise specified). Thus, they can,	// and often should, have constructors:	Vertex(float x, float y, float z, float Tx, float Ty) :	x(x), y(y), z(z), Tx(Tx), Ty(Ty) {}};struct Polygon {	int TexId;	Vertex v1;	Vertex v2;	Vertex v3;	// Note how complex objects are passed by const reference.	Polygon(int TexId, const Vertex& v1, const Vertex& v2, const Vertex& v3) :	TexId(TexId), v1(v1), v2(v2), v3(v3) {}	// Also note that this will automatically copy the passed-in Vertices into	// the Polygon being constructed: the originals still exist separately.};// Using the standard library container, the "structure of the list" is// separated out from the actual objects. This makes it easier to maintain the// code. Of course, not having to write the actual linked-list code helps a// lot, too. :)typedef std::list<Polygon> Polylist;class Sector {	public:	int ID; // Don't repeat the class name in member names; it doesn't add information.	Polylist polygons;	// The constructor and destructor will no longer need to do anything for	// this class, so we eliminate them all together. The std::list will get its	// own default constructor and destructor called automatically where	// appropriate.	// Don't return 'bool' from a function if it could only ever return the	// one value ('true', in the case of the original code). The return value	// is meaningless.	void AddPoly(int TexId, const Vertex& v1, const Vertex& v2, const Vertex& v3);	// Also, only make comments that are meaningful - in particular, don't write	// things that are immediately obvious from the corresponding code.	Sector(int ID) : ID(ID) {}};typedef std::list<Sector> Sectorlist;void Sector::AddPoly(int TexId, const Vertex& v1, const Vertex& v2, const Vertex& v3) {	// This becomes much easier. All we do is construct a Polygon, and tell the	// 'polygons' list to accept it at the end. We don't even need to make a	// temporary variable to hold that Polygon, because we won't refer to it	// again (just like how you don't need to make a temporary variable to hold	// a number when you pass it to a function).	// Also notice how, for consistency, I kept the parameters in the same order	// for all the relevant functions.	polygons.push_back(Polygon(TexId, v1, v2, v3));}class Map	{	public:	Sectorlist sectors;	bool AddSector(const string& SectorFile, int ID);};// Here's how we do file I/O and string manipulation in C++.// In the original code, BTW, the ID-reading process basically left behind the// "rest of a string" to be handled by the rest of the polygon-reading process.// This is sort of messy; I'm instead going to make a function that reads in// a whole polygon at once, assuming that all the vertex data is on the// same line as the texture ID. I'll have that function just handle that line,// and do the line-skipping in the main loop.Polygon readPolygon(istream& is) {	// This is actually not how we'd normally write these things in C++. Instead	// we would define operator overloads that would let us do things like	// 'Map mymap; thefile >> mymap;'.	// Initialize variables with their initial values, where possible. Also,	// declare things near first use, not all at the top of the function.	int id;	is >> id;	// One problem with the original code is that it tries to read a texture ID	// before every vertex, rather than just before each polygon. Notice how	// better-organized code neatly sidesteps those kinds of problems.	float x, y, z, Tx, Ty;	Vertex v[3];	for (int i = 0; i < 3; ++i) {		is >> x >> y >> z >> Tx >> Ty;		v = Vertex(x, y, z, Tx, Ty);	}	return Polygon(id, v[0], v[1], v[2]);}bool Map::AddSector(const string& SectorFile, int ID) {	// Here's how we get that file object in C++:	ifstream file(SectorFile.c_str(), ios::trunc);	// The 'trunc' flag translates to what the 't' did in the old "magic string".	// The 'r' is implied by the fact that we have an ifstream rather than an	// ofstream.	if (!file) { // we can still check it the same way.		MessageBox(NULL, "Sector could not load", "May be corrrupt", MB_OK);		return false;	}	// We don't need to pass around a buffer, because we can make a std::string	// locally (although even in the old code, it would have been better to make	// the buffer locally) and it will automatically be the right size. The C++	// standard library provides a real string object that is not simply some	// array of chars - it handles the memory management for you.	// Also, the same function will automatically work with the console input	// the same way as it does with files, in case you ever need that	// functionality. C++ stream objects (such as std::istream) are 'polymorphic';	// the decision about how to get bytes is made by the object itself, and not	// by the name of the function called. 	Sector s(ID);	string line;	// I'm also going to restructure your loop in a more sensible way:	while (getline(is, line)) {		// There's no need to check for special stuff at the beginning of the line,		// because all lines *not* starting with '#' are ignored *anyway*.		if (!line.empty() && line[0] == '#') {			// We can treat strings like streams, too:			s.polygons.push_back(readPolygon(stringstream(line)));		}	}	// Now that we finished making the sector, we can add it.	sectors.push_back(s);	// There's no need to "close" explicitly.	return true;}Map map;// This would normally be a member function of the Map instead...bool LoadMap(const string& fileName) {	// Oh, I see you're somewhat familiar with iostreams after all. Why not	// use them consistently? :)	// Anyway, we only read from the file, so don't also open it for writing.	int ID = 1;	ifstream ifs(fileName.c_str());	if (!ifs) {		MessageBox(NULL, "Map could not load", "May be corrrupt", MB_OK);		return false;	}	string sectorName;	while (ifs >> sectorName) {		map.AddSector(sectorName, ID);		ID++;	}	return true;}bool DisplaySector(int ID) {	Sectorlist& sectors = map.sectors; // make an alias to save typing.	// The original code does something similar with pointers.	// We don't need to handle an empty list specially, because it simply	// contains zero elements (so the loop executes zero times).		// Here's how we can look at each element of the list in turn:	for (Sectorlist::iterator sit = sectors.begin();	     sit != sectors.end(); ++sit) {		// Notice that the "iterator" can be used like a pointer:		if (sit->ID == ID) {			// The original looping logic made no sense: it said "do this at least			// once, until the pointer is not null", but then also included a check			// for a null pointer (because it could be null the first time). Clearly			// we didn't want to always do the loop at least once - a plain 'while'			// loop was more appropriate.			// But with the iterators, a for-loop is appropriate:			Polylist& polygons = sit->polygons;			for (Polylist::iterator pit = polygons.begin();			     pit != polygons.end(); ++pit) {				// There was another bug here: v1.x was printed instead of v3.x.				// The code really should use an array instead. But I'll let it pass				// for now... the *real* fix involves more complex stuff and I can only				// explain so much at a time.				cout << temp->v3.x;				cout << " " << temp->v3.y;				cout << " " << temp->v3.z;				cout << " " << temp->v3.Tx;				cout << " " << temp->v3.Ty;				cout << "\n";				cout << " " << temp->v2.x;				cout << " " << temp->v2.y;				cout << " " << temp->v2.z;				cout << " " << temp->v2.Tx;				cout << " " << temp->v2.Ty;				cout << "\n";				cout << " " << temp->v1.x;				cout << " " << temp->v1.y;				cout << " " << temp->v1.z;				cout << " " << temp->v1.Tx;				cout << " " << temp->v1.Ty;				cout << "\n";			}			return true;		}	}	return false;}int main() {	cout << "Trying to load map";	LoadMap("Map1.mp");	cout << "\nMap loaded!";	DisplaySector(1);	DisplaySector(2);	// Please don't pause your programs artificially at the end.}


Please note that the above code does NOT fix all the design problems with the code (and in fact I didn't even make sure it would compile), but should at least give you some good ideas.
Advertisement
Umm wow thanks ill read over that real good iv never used the std::list before or pritty much almost non of the std classes for that matter so thanks ill have a real good long look at it and see if i cant learn a bunch from it ^^
Quote:Original post by jpetrie
Why are you reinventing the wheel? If you need a linked list, use std::list. Although from looking at your code, you don't really need a linked list and could use std::vector instead.


stl...is pushed far too much under the idea of 'not reinventing the wheel'. This is undoubtably a good goal but I would really say that it depends what you are doing as to whether it is a good idea.

For most people here perhaps the development environment they are using supports it and supports it well, but then again if you are developing for consoles its a different matter entirely and may not even work with the compilers you are using.

Even using stlport on those systems would bring you to the point where you might want to modify the code due to it not meeting your needs. There are very specific cases of wanting better control over memory, inlining and un-inlining things...and so on.

In these cases, a roll your own directed specifically at your situation can be a much better solution.

I would say though, that even a roll your own should probably be inspired by these libraries.
Quote:Original post by freakchild
Quote:Original post by jpetrie
Why are you reinventing the wheel? If you need a linked list, use std::list. Although from looking at your code, you don't really need a linked list and could use std::vector instead.


stl...is pushed far too much under the idea of 'not reinventing the wheel'. This is undoubtably a good goal but I would really say that it depends what you are doing as to whether it is a good idea.


Er, sorry, but where did this "STL" bit come from? We're talking about the standard C++ library, which both includes things that STL does not (for example, all the *stream headers) and excludes things found in STL (such as the 'iota' and 'copy_n' algorithms).

And, you know, it's pretty hard to argue that the standard library of the language in use is in any way not "the wheel", or in need of "reinvention". To avoid using std::string in C++, for example, is sort of like (though at a higher level of abstraction) avoiding the library strcat(), strlen() etc. in C. Honestly, there really isn't room to improve on these things, except in really extraordinary circumstances - and even then, with C++'s standard library containers, you can normally do almost if not all the work by just writing an allocator (or better yet, using one of the ones provided by Boost).

Quote:if you are developing for consoles its a different matter entirely and may not even work with the compilers you are using.


Before pursuing that argument further, I'd invite you to note what forum this is, and therefore who is being helped, and what environments they are likely to be working in for the next few years.

And yes, I realize that - at least currently - some popular platforms don't really support - well, they don't really support C++. A shame, sort of. But heck - for all I know, by the time the current generation "graduates", we might be seeing Python used extensively on the PS4(TM) or XboxNaN(TM) or Nintendo Lolubernaem(TM).

But generally speaking, it does no good to allude vaguely to performance considerations if you can't even give a real-world example from your own experience. In isolation, it reeks of FUD.
Ok well im back and everything looks nice on the page :)

ok one last hitch and its problay a dumb one.

when i did up some code using the std::list

bool DisplaySector(MAP Map1,int ID){	SectorList& sectors = Map1.Sectors; 		for (SectorList::iterator sit = sectors.begin(); sit != sectors.end(); ++sit) 		{		// Notice that the "iterator" can be used like a pointer:			if (sit->ID == ID)			{				cout <<"\n Sectors Storded id: "<<sit->ID <<"\n";				PolygonList& Polygons = sit->Polygons;				for (PolygonList::iterator pit = Polygons.begin();pit != Polygons.end(); ++pit) 				{				cout << pit->v3.x;				cout << " " << pit->v3.y;				cout << " " << pit->v3.z;				cout << " " << pit->v3.Tx;				cout << " " << pit->v3.Ty;				cout << "\n";				cout << " " << pit->v2.x;				cout << " " << pit->v2.y;				cout << " " << pit->v2.z;				cout << " " << pit->v2.Tx;				cout << " " << pit->v2.Ty;				cout << "\n";				cout << " " << pit->v1.x;				cout << " " << pit->v1.y;				cout << " " << pit->v1.z;				cout << " " << pit->v1.Tx;				cout << " " << pit->v1.Ty;				cout << "\n";				}						return true;			}						}	return false;}


For some reason and it is yes elluding me -.^ this prints out signtifict notation where as non of the floating points are above 10.0f.

i think its printing out mabye a memorie location

but i passed in the object directly not as a pointer.

secondly

SectorList& sectors = Map1.Sectors; line of code gives me this compiler error

error C2440: 'initializing' : cannot convert from 'const SectorList' to 'SectorList &'

witch is rather quite stright forward however when i remove the & it prints out what looks like memorie location.

and as i have not done pritty much anything with std::list im not sure why this is

here is the rest of the code if needed

#include <windows.h>// We won't need stdio.h - or cstdio - any more.// But we will need these:#include <list>#include <iostream>#include <string>#include <sstream>#include <fstream>using namespace std;//Vertex structor struct VERTEX{public:float x;float y;float z;float Tx;float Ty;//ConstructorVERTEX(float x,float y,float z,float Tx,float Ty) : x(x), y(y), z(z), Tx(Tx), Ty(Ty){}};struct POLYGON{public:int TexId;VERTEX v1; VERTEX v2;VERTEX v3;//constructorPOLYGON(int TexId, const VERTEX &v1, const VERTEX &v2, const VERTEX &v3) : TexId(TexId), v1(v1), v2(v2), v3(v3) {}};//Make a List Type for the Polygonstypedef std::list<POLYGON> PolygonList;//Sector Class Used to hold information for each sector of the mapclass SECTOR{public:	int ID;			//Sectors Id tag used for refrence and indexing	PolygonList Polygons;	//A polgon List for the Sector	void AddPoly(int TexID, const VERTEX &v1, const VERTEX& v2, const VERTEX& v3);	//Class constructor	SECTOR(int ID) : ID(ID){}};void SECTOR::AddPoly(int TexID, const VERTEX &v1, const VERTEX &v2, const VERTEX &v3){	Polygons.push_back(POLYGON(TexID,v1,v2,v3));}//Make a list type for our sectorstypedef std::list<SECTOR> SectorList;class MAP{public:	SectorList Sectors;	bool LoadMap(string FileName);private:	bool AddSector(string SectorName,int ID);	int ReadString(ifstream File,string ToReturn);	VERTEX GetVertex(stringstream & is);	int GetTextureID(stringstream & is);};int MAP::ReadString(ifstream File,string ToReturn){return 0;}//Load the mapbool MAP::LoadMap(string FileName){	ifstream File(FileName.c_str(),ios::in);	if(!File)	{		cout <<"\nCould not open file: " <<FileName.c_str();	return false;	}	string SectorName;	int ID = 0;	while(!File.eof())	{		File >>SectorName;		if(!AddSector(SectorName,ID))		{		File.close();		return false;		}		ID++;	}	File.close();return true;}int MAP::GetTextureID(stringstream & is){int TexID = 0;is >>TexID;return TexID;}VERTEX MAP::GetVertex(stringstream & is){float x,y,z,Tx,Ty;is >>x >>y >>z >>Tx >>Ty;VERTEX v(x,y,z,Tx,Ty);return v;}bool MAP::AddSector(string SectorName,int ID){	ifstream File(SectorName.c_str(),ios::in);	if(!File)	{	cout <<"\n Could not load sector";	return false;	}		string ReadLine;	int TexID = 0;		VERTEX TempV1(0,0,0,0,0);	VERTEX TempV2(0,0,0,0,0);	VERTEX TempV3(0,0,0,0,0);	SECTOR Sec(ID);	int VertexCount = 0;		while(!File.eof())	{		File >>ReadLine;		if(ReadLine[0] == '#')		{			ReadLine[0] = NULL;		TexID =GetTextureID(stringstream(ReadLine));		}				if(!ReadLine.empty() && ReadLine[0] != '/')		{		if(VertexCount == 0){TempV1 = GetVertex(stringstream(ReadLine));}		if(VertexCount == 1){TempV2 = GetVertex(stringstream(ReadLine));}		if(VertexCount == 2){TempV3 = GetVertex(stringstream(ReadLine));}		VertexCount++;		}		if(VertexCount == 3)		{			Sec.Polygons.push_back(POLYGON(TexID,TempV1,TempV2,TempV3));			VertexCount = 0;		}	}	File.close();	Sectors.push_back(Sec);return true;}int main(){	MAP Map1;	if(!Map1.LoadMap("Map1.Mp"))	{	cout <<"\nMap load failed";	cin.get();	return 0;	}	cout <<"\n Displaying sector 1:\n";	DisplaySector(Map1,0);	cout <<"\n Displaying sector 2:\n";	DisplaySector(Map1,1);	cin.get();return 0;}


Thanks ahead of time for any input!
Quote:Original post by Zahlman
Honestly, there really isn't room to improve on these things, except in really extraordinary circumstances - and even then, with C++'s standard library containers, you can normally do almost if not all the work by just writing an allocator (or better yet, using one of the ones provided by Boost).

...

But generally speaking, it does no good to allude vaguely to performance considerations if you can't even give a real-world example from your own experience. In isolation, it reeks of FUD.


I don't want to take this post to an off topic conversation and I'm not trying to open this up for discussion as there has been a thread recently on this very subject. Though please refer to this document EA STL on this issue. It explains very well why using boost, or STL, or even providing an allocator is just not an option for professional game developers.

As for the original poster using the C++ standard library, I agree with everyone else here that using it is a great idea. Though, in my opinion, it wouldn't hurt the OP to learn how to write his own linked list before using the STL's linked list. It depends on his goals which I do not know.

If you'd like to discuss this further you can PM me or start a new thread and I can share some of my own real-world experiences.

-= Dave

EDIT: I re-read your post. I may have mis understood you. If you are speaking in only the context of beginner programmers then ignore my post and let me apologize, other wise please read the link it is very educational.
Graphics Programmer - Ready At Dawn Studios
Ummm as intresting as this converstation has become if someone could just find the time to read what i hade last writen as its driving me mildly INSAIN!

..ps thank you
Quote:Original post by Jouei
secondly

SectorList& sectors = Map1.Sectors; line of code gives me this compiler error

error C2440: 'initializing' : cannot convert from 'const SectorList' to 'SectorList &'

witch is rather quite stright forward however when i remove the & it prints out what looks like memorie location.


I compiled your program without any compiler errors. I'm not sure how you got that error, can you elaborate?

-= Dave

Graphics Programmer - Ready At Dawn Studios
OH geez right sry i fixed that one ok well the real problem is when it runs it gives me this output -1.07374e+008 instead of what the data that was read in

a small part of the file that it loads into the sector

//Floor

#1

0.0 0.0 0.0 1.0 0.0
1.0 0.0 0.0 0.0 0.0
1.0 0.0 1.0 0.0 1.0

1.0 0.0 1.0 0.0 1.0
0.0 0.0 1.0 1.0 1.0
0.0 0.0 0.0 1.0 0.0

the Map file its self Map1.mp just holds the file names of each sector

Quote:Original post by Jouei
O
For some reason and it is yes elluding me -.^ this prints out signtifict notation where as non of the floating points are above 10.0f.

i think its printing out mabye a memorie location


Also, I tested this out with test data and it is printing numbers past the first 10's place. Here is my output

Displaying sector 1:

Sectors Storded id: 3
4.4 1.3 3.4 45.04 5.345
4.4 1.3 3.4 45.04 5.345
4.4 1.3 3.4 45.04 5.345

Displaying sector 2:

Sectors Storded id: 3
4.4 1.3 3.4 45.04 5.345
4.4 1.3 3.4 45.04 5.345
4.4 1.3 3.4 45.04 5.345


Care to elaborate on this as well?

Graphics Programmer - Ready At Dawn Studios

This topic is closed to new replies.

Advertisement