SFML community forums
General => General discussions => Topic started by: Joshua Flynn on September 05, 2011, 09:31:04 pm
-
I am just in the design phase of an improved template dynamic list for use in combination with SFML classes, and I want people's opinion of what they imagine or expect (I want to make it instinctive and more user-friendly):
//What do you imagine these do, and what do you imagine they return?
TemplateList++;
TemplateList--;
--TemplateList;
++TemplateList;
TemplateList = Item;
//What do you imagine this should return?
(!TemplateList)
I have my own ideas of what the functions should do, but I want to see what others think.
Thank you for any feedback.
-
//What do you imagine these do, and what do you imagine they return?
TemplateList++;
TemplateList--;
--TemplateList;
++TemplateList;
- I could only see this as iterating the list, increasing and decreasing an internal iterator!
TemplateList = Item;
Makes no effective logic to set a list as one item, but if you make it a += its a perfectly acceptable "Append"
//What do you imagine this should return?
(!TemplateList) - makes no sense to me, if its a template, the any object won't have a common logic evaluation. Therefore, what the hell wold be a negation of a list of any kind of object? Cant think of anything
Hope it helps
-
None of those operators make any sense.
How can you increment a list? How can you assign an entire list to one item?
The closest thing I can imagine would be that !TemplateList would check to see if the list is empty, but even that is "blech".
EDIT:
Don't get cute with operator overloading. The reason it exists is to make code more natural, not to avoid typing function names. If you have to ask the question "what should this operator do or return", then you shouldn't be making that operator. It defeats the point and makes your code more confusing.
/EDIT
Any reason why you don't want to just use std::list?
EDIT 2:
if you make it a += its a perfectly acceptable "Append"
I disagree that that's perfectly acceptable =P
-
TemplateList++;
TemplateList--;
--TemplateList;
++TemplateList;
TemplateList = Item;
(!TemplateList)
- push back a default-constructed item
- pop back
- pop front
- push front a default-constructed item
- no idea
- test if the list is empty
?
In my opinion, it's confusing at best. Follow the rules of the language and its standard library. Don't try to over-simplify, longer but more explicit names will always be more intuitive than operators. Use operators only when they make perfect sense. And... use standard classes, don't reinvent the wheel ;)
-
- I could only see this as iterating the list, increasing and decreasing an internal iterator!
Makes no effective logic to set a list as one item, but if you make it a += its a perfectly acceptable "Append"
makes no sense to me, if its a template, the any object won't have a common logic evaluation. Therefore, what the hell wold be a negation of a list of any kind of object? Cant think of anything
Hope it helps
Yes it does, thank you for your feedback.
If you have to ask the question "what should this operator do or return", then you shouldn't be making that operator. It defeats the point and makes your code more confusing.
I have in mind precisely what it would do, but generally in programming, bugs occur when the assumptions of the user (IE other than me) are different from the assumptions of the program. In this case I want to see if other people instinctively have the same concepts I do before I make it part of the design.
Any reason why you don't want to just use std::list?
Std::list requires log(n) time to get the size of the list, when it's perfectly possible to get a log(1) return, including iterator numeric position. Given how I have no idea how it operates under the covers (if it does log(n) for size returns, what else does it do inefficiently?), it makes it difficult for me to optimise it to other classes - which are supposed to automate, simplify and make safe tasks.
The size issue might not seem like a gripe at first but running log(n)*n for how many times size is required seems very poor (especially given this will be for dynamic char lists of sizes 89000+ or more from files). Custom-lists also gain the advantage of improving over iteration (IE design and improvement), fewer functions, more capability/stability.
TemplateList++;
TemplateList--;
--TemplateList;
++TemplateList;
TemplateList = Item;
(!TemplateList)
- push back a default-constructed item
- pop back
- pop front
- push front a default-constructed item
- no idea
- test if the list is empty
These are generally the ideas I had for the list. Iteration across the list was the other alternative, but it would make either pre or post-fix redundant (duplication of tasks).
In my opinion, it's confusing at best. Follow the rules of the language and its standard library. Don't try to over-simplify, longer but more explicit names will always be more intuitive than operators. Use operators only when they make perfect sense. And... use standard classes, don't reinvent the wheel ;)
The operators would be front-ends for suitably named functions, with the named functions themselves still accessible. As for std library functions, they tend not to be my preference, generally because of how they work.
But it's good, thank you for the feedback. I will consider it when writing the classes. Any additional feedback is appreciated.
-
Std::list requires log(n) time to get the size of the list,
How do you figure that? All it has to do is store the size of the list internally (which I'm reasonably sure it does) and it gets O(1).
I don't even see how it could get O(log(n))
Custom-lists also gain the advantage of improving over iteration(IE design and improvement)
I don't follow. How can you improve upon linked list iteration?
fewer functions
So you basically want to make a list that does less.
Call me crazy, but that's a shortcoming, not an advantage.
more capability
What is std::list incapable of?
stability.
So you plan to write a linked list that's more stable than the one that's been around for several years and has been extensively used and tested by virtually every C++ programmer in the world.
I don't mean to sound negative. It's just that this seems like a fool's errand to me. Unless it's purely for academic/educational reasons, there's really no good reason to reinvent the wheel like this. It just seems like a massive waste of time, and will confuse/annoy any people who use your code in the future.
EDIT:
These are generally the ideas I had for the list. Iteration across the list was the other alternative
Again, the mere fact that there are multiple possibilities of what the operators could be doing is a pretty clear indication to me that they should not be overloaded.
-
Standard containers have a robust design and implementation which is the result of years and years of experts working on it. std::list::size is O(1). Basically, there are enough containers so that you can always find one that can be perfect for your needs (don't use a std::list to store thousands of characters!).
People (often beginners -- don't know about you) always tend to rewrite standard classes, I don't know why; maybe they don't have enough experience with the language and find it simpler to write their own classes rather than adapt their code to the language and its SL. A lot of people have to start like this, experiment and write their own low-level stuff, until they feel comfortable enough with the language.
It's not bad to reinvent the wheel from a learning point of view, but for "real" code just forget about that, and use what the language provides.
-
Sometimes if you need the best performance and not much functionality, you can rewrite it... I did that once, replacing std::list with a dynamic array implementation which was much faster. But that was a specific case, I was number crunching some genetic algorithms and needed the speed. ;) But for general cases it's usually good enough.
-
//What do you imagine these do, and what do you imagine they return?
TemplateList++;
TemplateList--;
--TemplateList;
++TemplateList;
TemplateList = Item;
//What do you imagine this should return?
(!TemplateList)
I have my own ideas of what the functions should do, but I want to see what others think.
Thank you for any feedback.
TemplateList++; - Add new item with default constructor(push_back(Item()))
TemplateList--; - Remove last item(pop_back())
--TemplateList/++TemplateList - Iterations
TemplateList = Item doesnt make sense, but maybe add that item? For that you should have += instead.
!TemplateList should return if its empty.
-
TemplateList++; - Add new item with default constructor(push_back(Item()))
TemplateList--; - Remove last item(pop_back())
--TemplateList/++TemplateList - Iterations
It would be very confusing because you won't be able to do *tl++ = smth.
As said previously, Use operators only when they make perfect sense.
I would say even more : Use operators only when they make perfect sense.
-
TemplateList++; - Add new item with default constructor(push_back(Item()))
TemplateList--; - Remove last item(pop_back())
--TemplateList/++TemplateList - Iterations
It would be very confusing because you won't be able to do *tl++ = smth.
As said previously, Use operators only when they make perfect sense.
I would say even more : Use operators only when they make perfect sense.
Hehe you are right sir :D Im not really that interested in a new container, since there are so many standards that do a good job already, just wanted to give my thoughts on an alternative tho :)
-
All it has to do is store the size of the list internally (which I'm reasonably sure it does) and it gets O(1).
std::list::size is O(1).
Not necessarily, in libstdc++ it's O(n). Legal in "old" C++, IIRC not legal anymore in C++0x.
-
Even if that's the case, you can just store the size of the list separately. To redo the entire class from scratch for such a minor detail is excessive.
-
I have in mind precisely what it would do, but generally in programming, bugs occur when the assumptions of the user (IE other than me) are different from the assumptions of the program. In this case I want to see if other people instinctively have the same concepts I do before I make it part of the design.
I hope you realized that there are many different opinions and so I recommend you not to implement those operators.
Std::list requires log(n) time to get the size of the list, when it's perfectly possible to get a log(1) return, including iterator numeric position. Given how I have no idea how it operates under the covers (if it does log(n) for size returns, what else does it do inefficiently?)
I don't think that implementing size in O(n) is just for fun. Mostly it is by the way implemented in O(1). If it is not, it is mostly O(n) because of other performance issues. For example would std::list::splice be in O(n), if size is in O(1), because the new size of the list has to be computated. If size is O(n), splice would be O(1).
I'd prefer size in O(1) and splice in O(n), but there are obviously different opinions about this topic.
But there are many other different STL container.
std::deque for example can be used similar to std::list, provieds size in O(1) and individual element access in O(1).
Just have a look at all STL containers and think about using them.
http://www.cplusplus.com/reference/stl/
I think the STL containers are rather performant and I don't think that you would easily create a new one which is better than the others ;).
-
That's interesting. I hadn't even thought about splice.
I would think the best way to handle that would be to invalidate the size after a splice, and only recalculate it if needed. That way you can get O(1) for both, except the first time you call size() after a splice operation, which is the only time it would take O(n):
class list
{
//...
private:
mutable size_t listsize;
mutable bool sizevalid;
//...
void splice(...)
{
//...
sizevalid = false;
}
//...
size_t size() const
{
if(!sizevalid)
{
recalcsize();
sizevalid = true;
}
return listsize;
}
//...
};
I wonder if any implementations do it like that.
-
Std::list requires log(n) time to get the size of the list,
How do you figure that? All it has to do is store the size of the list internally (which I'm reasonably sure it does) and it gets O(1).
I don't even see how it could get O(log(n))
Sorry I meant O(n) and O(n*n). I didn't mean log. Confusion of terms.
But, in response to why it's not O(1):
http://www.cprogramming.com/tutorial/stl/stllist.html
" There is one caveat to be aware of: the size function may take O(n) time, so if you want to do something simple such as test for an empty list, use the empty function instead of checking for a size of zero."
Given the above classes I will be stacking on top of it will make many calls to size (dynamic arrays will resize to match dynamic lists, etc), it should be optimal. As said, only way to know for sure is my own code.
I don't follow. How can you improve upon linked list iteration?
Not linked list iteration. Iteration of the design - for example, the first iteration of code will always be the buggiest, with the following iterations being improvements to the former.
For example, some time back I had a linked list that took probably about 2000 - 3000 lines of code riddled with memory allocation crashes and various pitfalls.
The present one (iteration 4) takes roughly 800 lines of code (scratched out in one day) - this includes both node and list, doesn't crash (bar user abuse - iteration 3 can't be crashed but is less efficienct), it will explicitly report traceable errors, and compared to previous iterations, already has more advanced functions (it's not finished yet).
My hope is to achieve a coding efficiency such that a fully functional template list is achievable in 400 lines or less (of readable code that's width is roughly the size of the screen) - that is better than it's predecessor.
fewer functions
So you basically want to make a list that does less.
Call me crazy, but that's a shortcoming, not an advantage.
Fewer functions don't mean less functionality. Nor does more functions mean more functionality. Consider you have an int *Ptr (with a dynamically allocated int), you might write:
int GetInt (){return *Ptr;}
void SetInt(const int A){*Ptr = A;}
Which is bad, consider:
int &Int(){return *Ptr;} //Does both of the above functions whilst not permitting the user to alter the pointer itself
And:
File = "Test.txt";
File = 'w';
File = "Write this to file.";
Which to the user is the 'same' function. More functionality, less functions.
more capability
What is std::list incapable of?
Non O(1) size returns. Which is pretty bad for something 'extensively' tested. Why does a novice coder like myself need to supply that?
And, I don't know how it works on the lowest level. It could do something scary like std::vector (which is to recopy everything everytime it runs out of space... which defeats the point of being dynamic).
Std::vector could easily be combined with a list to make it so it doesn't recopy anything until the array itself is called (then it keeps a hard copy until the list is modified).
And you can actually do something even more clever. AN array of pointers that point to the individual list items so modification to the array == modification to the list.
And I'm a novice coder.
So you plan to write a linked list that's more stable than the one that's been around for several years and has been extensively used and tested by virtually every C++ programmer in the world.
Given it's expanded functionality, yes. The std library is that many years out of date (see vector complaints above). It's fairly easy to be stable when you don't do much to rock the boat.
The most troubling phrase I've heard?
http://www.cplusplus.com/reference/stl/deque/
" deques perform worse and have less consistent iterators and references than lists."
How exactly can an iterator be 'less consistent'? The term sounds like it might inconsistently access memory, which is a huge issue, and part of the reason why I don't touch STD with a barge pole.
The usage of random access iterators isn't my idea of fun:
http://www.cplusplus.com/reference/std/iterator/
Given that doubly linked nodes can be allocated anywhere, chances are Iterator + 3 might run outside of scope and find itself a nice segfault.
To demonstrate (http://www.google.com/search?hl=en&biw=1280&bih=685&q=problem+with+std+iterator&oq=problem+with+std+iterator&aq=f&aqi=&aql=1&gs_sm=e&gs_upl=2932l6606l0l6724l25l19l0l0l0l0l190l2240l8.10l18l0).
People can use std by all means, but it isn't perfect. I gain bonus points by building my own lists because I can optimise them on all ends of the scope and learn as I go along.
Again, the mere fact that there are multiple possibilities of what the operators could be doing is a pretty clear indication to me that they should not be overloaded.
Ambiguity of operation never stopped a function implimentation before.
Consider <<. Bitwise shift or piping data?
A<<B;
std::cout<<A;
...Hmm.
-
People (often beginners -- don't know about you) always tend to rewrite standard classes, I don't know why; maybe they don't have enough experience with the language and find it simpler to write their own classes rather than adapt their code to the language and its SL. A lot of people have to start like this, experiment and write their own low-level stuff, until they feel comfortable enough with the language.
It's not bad to reinvent the wheel from a learning point of view, but for "real" code just forget about that, and use what the language provides.
From aspect, I find laying good groundwork helps later on. Iteration 3, for example, was stable and did the job, but I am now looking at inserting lines in any place in a file and insert images in any order/place, so iteration 4 is presently in development to enable that.
The other problem with using std is it's impossible to know it's pitfalls without either excessive research (compare; I can write a template list in one day, I would need to do a lot of reading to get up to scratch maybe over many times) until you are approximately 60-70% into development, where a key feature (EG iterator, as other programmers complained about) breaks or doesn't do what is anticipated.
I get the reinventing the wheel dig, which is why template list is a base class to advanced sub-classes classes, and the other classes so-on and so fourth.
I had the last iteration code up to the point where, barring some optimisation, this would have been valid:
File = HTMLData = "http://iono.jpl.nasa.gov/latest_rti_global.html";
And yes, it does precisely what you think it does. Merging File and HTMLFileProc would have probably resulted in:
File = "http://iono.jpl.nasa.gov/latest_rti_global.html";
What I eventually want to achieve is:
Renderer = ImageQueue = File = "www.fakewebsite.com/loadimages.html";
And yes. It is precisely what you think it does.
-
Even if that's the case, you can just store the size of the list separately. To redo the entire class from scratch for such a minor detail is excessive.
But since that's the case, your assertion about std::list::size() being O(1) isn't necessarily correct. I just wanted to wipe out the misconception.
I would think the best way to handle that would be to invalidate the size after a splice, and only recalculate it if needed. That way you can get O(1) for both, except the first time you call size() after a splice operation, which is the only time it would take O(n):
[...]
I wonder if any implementations do it like that.
I'm positive I've seen a std::list wrapper that was doing that, but I have absolutely no clue where I've seen it and how it was called. Anyone?
Fewer functions don't mean less functionality. Nor does more functions mean more functionality. Consider you have an int *Ptr (with a dynamically allocated int), you might write:
int GetInt (){return *Ptr;}
void SetInt(const int A){*Ptr = A;}
Which is bad, consider:
int &Int(){return *Ptr;} //Does both of the above functions whilst not permitting the user to alter the pointer itself
And:
File = "Test.txt";
File = 'w';
File = "Write this to file.";
Which to the user is the 'same' function. More functionality, less functions.
I wouldn't want to maintain the code that you've written.
-
Which is bad, consider:
int &Int(){return *Ptr;} //Does both of the above functions whilst not permitting the user to alter the pointer itself
Well that restricts your implementation, which is why it's not typically done that way. With the 'return a reference' approach you have to have a int that can be get/set without supervision in your implementation, which might not always be optimal.
Non O(1) size returns. Which is pretty bad for something 'extensively' tested. Why does a novice coder like myself need to supply that?
Again... have you profiled this? Or are you just making assumptions?
All the documentation I've seen says it's implementation dependent, and I would be quite surprised if such a commonly used function wasn't well optimized.
Your issue might be moot. I'd really recommend you at least test it before you do all this work to solve a problem that might not even exist in the first place.
And, I don't know how it works on the lowest level.
You don't need to, that's kind of the point. ;P
It could do something scary like std::vector (which is to recopy everything everytime it runs out of space... which defeats the point of being dynamic).
It's a linked list. So it doesn't do that (no linked list implementation would). You're right, that would defeat the entire point.
Again -- instead of just assuming list will give you a performance bottleneck, you should use it and see if it really does. If it does, you can swap in your own class later without having to rewrite anything in your code (except a single typedef).
Std::vector could easily be combined with a list to make it so it doesn't recopy anything until the array itself is called (then it keeps a hard copy until the list is modified).
That wouldn't be easy. That would drastically change the overall structure of the class and turn it into a mess. vector is already complicated enough without being a weird hybrid mash.
And you can actually do something even more clever. AN array of pointers that point to the individual list items so modification to the array == modification to the list.
If this is what you are after, then writing your own class would be a reasonable thing to do, since it is not offered in any of the standard classes. I was under the impression you just wanted a linked list.
But of course there are performance tradeoffs with this as well. Inserting elements in a list is no longer O(1), there's a higher memory footprint, etc, etc.
The std library is that many years out of date (see vector complaints above)
I didn't see any vector complaints? (EDIT: other than the "combine it with a list" thing, but I think that's crazy /EDIT)
It's fairly easy to be stable when you don't do much to rock the boat.
You just discovered the golden rule of programming. KISS: Keep it simple, stupid.
Overcomplication is a bane of many programmers and programs. You'll find that out in time. ;P
How exactly can an iterator be 'less consistent'?
When you insert an elements in a std::list, existing iterators remain valid.
When you insert an element in a std::deque or std::vector, they don't (since memory may have needed to be shifted around)
That's all it means. Don't freak out =P
Given that doubly linked nodes can be allocated anywhere, chances are Iterator + 3 might run outside of scope and find itself a nice segfault.
To demonstrate.
All of those posts on google are people misusing the class. Of course if you don't know what you're doing you will run into problems.
You can make the effort to write a fool-proof container class that guards against every possible invalid access, but its performance will suck. std figures performance is more important for practical applications.
I gain bonus points by building my own lists because I can optimise them on all ends of the scope and learn as I go along.
Well in the end if you do decide to reinvent the wheel, I hope you at least run some tests to compare its performance with std container classes. You might be surprised at the result -- std performs quite well.
Consider <<. Bitwise shift or piping data?
I agree that the << and >> overloads of iostream were a big mistake. Ambiguity aside, they also cause thread safety issues.
But just because std made that mistake doesn't mean it's OK to repeat it.
Remember that operator overloads are not there to reduce typing, they're there to make the code more clear. If what you want them to do isn't intuitive, it shouldn't be there (and judging by the multiple responses you got in this thread, I would say it's not intuitive).
-
Sometimes if you need the best performance and not much functionality, you can rewrite it... I did that once, replacing std::list with a dynamic array implementation which was much faster. But that was a specific case, I was number crunching some genetic algorithms and needed the speed. ;) But for general cases it's usually good enough.
Given template list is a base class to FileProc, StringTokeniser, HTMLFileProc etc, having it optimised is worth it in the long run.
/*
I apologise, the post has gone awry. There should be a quote from laurent here.
*/
That's an idea. Maybe have ++ return the newly created node (or node item?). The only issue I see is crash issue if the newly created node does not get created. So:
(TemplateList++) = Item; //Assigned via node's assign rather than item assign.
And -- returns the node it's moved back to. Again, only issue is if there is no nodes left. But this would be down to the user.
They sound potentially very useable but the issue is potential bugginess.
Even if that's the case, you can just store the size of the list separately. To redo the entire class from scratch for such a minor detail is excessive.
It would take more than merely implementing a int called size to get the highest efficiency in updating the size. Otherwise you would have to keep updating Size... by still using the O(n) algorithim (because there is no way to tell the list hasn't been modified).
So either you'd have to build function overloads to intercept at every modification to the list (what's so different to building own said list?), or you still have to keep updating the int of Size with the O(n) call.
Try it. You'd have to intercept every function. And given you overload it, you have to write the entire function for it anyway. So yes, minor details matter.
Additionally, consider:
O(a+(b*c)) Walk Distance of mainlist, plus walk distance of charlist times by access calls.
If I want to copy from a dynamic list to a dynamic array, I need the size of the main list (a) and the size of the specifc sub-list (b) however many times I access it (c):
10 chars in 10 lists, would become 10+(10*10) = 110;
WIth O(1) function, it becomes O(1+(1*c)) int access, int access times by number of access calls. Which is 10... so 1+10 = 11.
Vast saving. This is with just a small list. Imagine 89000+.
I don't think that implementing size in O(n) is just for fun. Mostly it is by the way implemented in O(1). If it is not, it is mostly O(n) because of other performance issues. For example would std::list::splice be in O(n), if size is in O(1), because the new size of the list has to be computated. If size is O(n), splice would be O(1).
I'd prefer size in O(1) and splice in O(n), but there are obviously different opinions about this topic.
But there are many other different STL container.
std::deque for example can be used similar to std::list, provieds size in O(1) and individual element access in O(1).
Just have a look at all STL containers and think about using them.
http://www.cplusplus.com/reference/stl/
I think the STL containers are rather performant and I don't think that you would easily create a new one which is better than the others ;).
My post to Disch earlier has appropos comments. Splice I have not heard of and would be even less sure of to use. Deque has it's (given above post) problems. It's theoretically possible to combine the traits of vector, list and deque (assuming I understand operation correctly) into a single class that does not have the pitfalls of all three.
I will offer the finished class for assessment.
-
Given template list is a base class to FileProc, StringTokeniser, HTMLFileProc etc, having it optimised is worth it in the long run.
You're spending time optimizing something without profiling it first. Optimization is a very hard topic. Guessing is not a good idea.
I'm not saying that you should not write your own list. But it should be only for a learning purpose.
If in an application you need a container, most of the time STL containers are better than custom class (and almost always vector is the best choice).
-
I wouldn't want to maintain the code that you've written.
I am not sure what there is to maintain? It's straight forward enough to use - assignment operators mostly. If (and if is key) it crashes you get an error telling you the exact chain of function calls you'd need to look at (all searchable in code::blocks) and the nature of the error. I could tack in the line __LINE__ var to also reproduce the line but I think that's a bit unnecessary.
If your issue is with the passing the filename and access mode via assignment, that's merely FileProcModular, a front-end to FileProc. Modular is designed specifically for straight-forward assignment operations.
I am sure you could write out every function call manually within both FileProc(Modular?), StringTokeniser and HTMLFileProc to make it somewhat more readable at the expense of wasting time.
A front-end is a user interface. If you're coding for stability, you use FileProc, if you're coding for speed, you call it's front-end, Modular for assignment operators.
If I had the following:
RendererProc Renderer;
ImageQueue Queue;
FileImage ImageLoader;
Queue = ImageLoader = "image1.jpg";
Queue = ImageLoader = "image2.jpg";
Queue = ImageLoader = "image3.jpg";
Renderer = Queue;
You probably can easily figure out precisely what it will do. And you'd have no difficulty modifying that code (even as a novice). Compared to:
sf::RenderWindow App(sf::VideoMode(800,600,32), "SFML Graphics");
sf::Image Image[3];
sf::Sprite Sprite[3];
//This is without the error statements
//Can't loop this unless images have a complicated string setup
Image[0].LoadFromFile("image1.jpg");
Image[1].LoadFromFile("image2.jpg");
Image[2].LoadFromFile("image3.jpg");
//May alternatively be a loop
Sprite[0].SetImage(Image[0]);
Sprite[1].SetImage(Image[1]);
Sprite[2].SetImage(Image[2]);
App.Clear();
//May alternately be a loop
App.Draw(ImageArr[0]);
App.Draw(ImageArr[1]);
App.Draw(ImageArr[2]);
App.Display();
You might argue the latter will grant you more control (granted, writing from scratch will do that for you), but it won't make it more manageable, so maintainability is more difficult.
-
You might argue the latter will grant you more control (granted, writing from scratch will do that for you), but it won't make it more manageable, so maintainability is more difficult.
Actually, I'd argue that the latter is much more readable, because it actually says what it is doing.
To understand your code on the other hand, I'll have to learn your strange overloads, which I've never seen elsewhere.
As everybody else here, I'd say: Use the STL containers and roll your own if, and only if, they are really your bottleneck.
Just my 2 cents...
-
Well that restricts your implementation, which is why it's not typically done that way. With the 'return a reference' approach you have to have a int that can be get/set without supervision in your implementation, which might not always be optimal.
I don't see how that restricts the implementation, given you were arguing fewer functions produce less functionality. If we had Get and Set, as separate, it would still crash if int wasn't there (you can't get or set a NULL), but this is purely red herring - point was, two functions can be merged.
If you're going down the dynamic allocation issue, consider:
//Two functions
const ClassItem &GetItem(){return Item;}
void SetItem(const ClassItem &Copy){Item = Copy;}
//One function
ClassItem &GetItem(){ return Item; }
Same functionality.
Non O(1) size returns. Which is pretty bad for something 'extensively' tested. Why does a novice coder like myself need to supply that?
Again... have you profiled this? Or are you just making assumptions?
All the documentation I've seen says it's implementation dependent, and I would be quite surprised if such a commonly used function wasn't well optimized.
The bolded parts says it all. If it's implementation dependent then testing it is redundant - it varies from implementation to implementation there is no consistency (ironic from a library called 'standard', no?) and thus no point using it as an optimisation here is an inefficiency there. O(n) is worst-case and O(1) is best case, compared to my own class which is O(1) worst-case and O(1) best case.
To address the next points:
Your issue might be moot. I'd really recommend you at least test it before you do all this work to solve a problem that might not even exist in the first place.
And, I don't know how it works on the lowest level.
You don't need to, that's kind of the point. ;P
Which is, of course, a contradiction. If I want to know if something is optimised, I need to know how it's implemented at the lower levels (so I know how it will work in specific situations).
For all I know, at the lowest level, it could have implemented a game in response to #pragma (gcc reference there (http://www.google.com/search?hl=en&biw=1280&bih=685&q=%23pragma+and+gcc+game&oq=%23pragma+and+gcc+game&aq=f&aqi=&aql=1&gs_sm=e&gs_upl=1433l2049l0l2175l5l4l0l0l0l0l118l293l2.1l3l0)).
It could do something scary like std::vector (which is to recopy everything everytime it runs out of space... which defeats the point of being dynamic).
It's a linked list. So it doesn't do that (no linked list implementation would). You're right, that would defeat the entire point.
Vector was an example of scary behaviour. I didn't mean that list does something similar to recopying, but something just as scary (iterator can go out of bounds with list and deque).
Point is, if vector (as a std) does scary inefficient stuff like that, iterator can hop out of bounds, and list has an inconsistent O() for size, they don't leave a good impression.
Again -- instead of just assuming
I gave appropos citation. Another programmer confirms what I am saying, you had said earlier, implementation specific. So it's not an assumption. In-fact, it'd be an assumption to assume it's O(1). I personally take it as a worst-case/best-case, given TemplateList has worse case of O(1) there's really no competition.
That wouldn't be easy. That would drastically change the overall structure of the class and turn it into a mess. vector is already complicated enough without being a weird hybrid mash.
Not that hard. Class with vector (of pointers), list. Items add to list, set vector size to match list size, populate vector with addresses of list items on operator[] call if the vector is not same as list size.
And you can actually do something even more clever. AN array of pointers that point to the individual list items so modification to the array == modification to the list.
If this is what you are after, then writing your own class would be a reasonable thing to do, since it is not offered in any of the standard classes. I was under the impression you just wanted a linked list.
But of course there are performance tradeoffs with this as well. Inserting elements in a list is no longer O(1), there's a higher memory footprint, etc, etc.
Inserting elements is still O(1), as array updates isn't actually called until the array is needed. Array updating when the array does not match list size is O(1+n) (1 being the check, n being number of list items to iterate), but subsequent calls are O(2) (array size check, returned item).
Compared to an array, which is O(1) it is less efficient (this could be circumvented if it wasn't automatically done IE no failsafe), but compared to walking the list to an item (especially if you have numerous item calls to make) it is faster (at O(A-B), A being current pos, B being intended pos), and would also allow for even faster node swapping.
In-fact, I've already built given function. If memory overhead is an issue, converting from a TemplateList to a TemplateArray (and clearing the List) would be more conductive. But if you expect the list to be expanded but need O(2) (compared to O(A-B)) time it's worth it. The memory versus cost ratio.
I didn't see any vector complaints?
Recopying on every resize.
But just because std made that mistake
And here in, lies the irony of defending std::list.
Well in the end if you do decide to reinvent the wheel, I hope you at least run some tests to compare its performance with std container classes. You might be surprised at the result -- std performs quite well.
Feel free to set up (or suggest) a test I can implement to compare. I'd love to see if it's optimised.
-
Actually, I'd argue that the latter is much more readable, because it actually says what it is doing.
Readability is not the exclusive criterion, nor should it really be expected in coding (given, this is coding, assembly is not expected to be readable either), and is a novel appeal when no other justification exists given what is readable depends on the view of the coder - a subjective basis that is altered on a whim. If readability was a preference, a GUI interface would have been supplied (like gamemaker).
I am not sure how exactly my code is not doing what it says. You have a renderer that renders, an image queue that queues images and a imagefile that loads images. How exactly would you make it any more explicit than that?
-
You're spending time optimizing something without profiling it first. Optimization is a very hard topic. Guessing is not a good idea.
Two things generally keep that in-check. Iterational testing (previous code's mistakes are the next code iteration's improvements), and visualisation of how the present written code will impact future functions (what it does etc). I know adding traceable error messages is less efficient than none, but I know bug-tracking is a lot faster with them available.
I'm not saying that you should not write your own list. But it should be only for a learning purpose.
Learning is the other reason. But adaptability is what gives it the edge.
If in an application you need a container, most of the time STL containers are better than custom class (and almost always vector is the best choice).
I would need to test it before we could comment, but I am sure a custom-adapted function is more efficient than a generalised one.
-
I don't see how that restricts the implementation,
It forces you to have an int that's always accessable via a reference, which may not be possible if the int is part of another object.
It also prevents you from monitoring writes to that int -- to check for boundary checks, illegal writes, or make other internal state changes depending on the data written.
O(n) is worst-case and O(1) is best case, compared to my own class which is O(1) worst-case and O(1) best case.
Fine fine. I'll concede on this point since you're clearly dedicated to it. Whether or not it's a good idea is still questionable in my mind.
Really the major reason for my interjection in this thread was your ill-advised operator abuse.
Point is, if vector (as a std) does scary inefficient stuff like that
I assume you're talking about copying on resize.
vector guarantees contiguous memory allocation. That's the whole point. It's fast random access. There's no way to keep it all contiguous in memory if you don't move everything when you run out of space.
It's not inefficient if you use it right.
iterator can hop out of bounds
Iterators are thin layers over pointers. Just as you can have a bad pointer (or a bad index), you can have a bad iterator. std doesn't double-check every access because that would make it too slow for practical use. They opt for speed over safety.
and list has an inconsistent O() for size, they don't leave a good impression.
Don't take this the wrong way, but I think you're just in a funk where you want to build a better mouse trap. I've been there before. It's easy to find fault in existing implementations and think you can do better. But when you consider how rubust and flexible the standard container classes are, the performance and elegance they offer is surprisingly high. They're very reusable.
Does that make them perfect for every task? No. Do you have to go with your own implementation sometimes? Yes, although it's quite rare. Is this particular instance one of those times where you'd have to go with your own implementation? I doubt it, but it's your call.
One of the advantages to using existing libs is that you can build your program on the backs of other people's foundations. This makes it easier to write "programs" rather than writing "code".
That's besides the point that you're trying to optimize before you have anything written. Optimizing one area of the program won't matter if the bottleneck is elsewhere. Get it working first, optimize later. Like I say, if it turns out std::list is no good, you can drop in your own class at any time in the future. All you'd have to do is change a typedef. And if it turns out that std::list works fine, you just saved yourself a good month of wasted time and effort.
Class with vector (of pointers), list. Items add to list, set vector size to match list size, populate vector with addresses of list items on operator[] call if the vector is not same as list size.
What's the point of having the list if you have a vector? They're contradictory storage containers.
vector has slow insertion and fast random access
list has fast insertion and no random access.
combining both gives you the worst of both worlds. You can't access the list randomly and you can't insert/remove items in the vector quickly.
Maybe I'm missing the point here.
[vector] Recopying on every resize.
It doesn't. It recopies when you exceed its capacity. The capacity can be preset with a call to reserve.
-
O(n) is worst-case and O(1) is best case, compared to my own class which is O(1) worst-case and O(1) best case.
Still, you should check with a profiler, if this worst-case O(n) is really a bottleneck and deserves spending so much time on it.
Readability is not the exclusive criterion, nor should it really be expected in coding
I strongly disagree with you here. Readibilty is a very important criterion for maintainability and thus should be expected in coding. After all, others are supposed to read your code, too.
I am not sure how exactly my code is not doing what it says. You have a renderer that renders, an image queue that queues images and a imagefile that loads images. How exactly would you make it any more explicit than that?
It's not explicit - that's the problem.
It's implicit, that "Queue = ImageLoader" appends the image to the image queue. After all, it could also prepend or insert in the middle.
The same goes for overloading the ++ and -- operators. They don't have an intuitive meaning for lists and should thus not be overlaoded.
Is there any special reason, why you don't want an STL-like interface?
-
I'm actually starting to wonder why you'd even need to call size() frequently enough for it to be a performance issue. The only times I can see needing it are for serialization or output to the user -- neither of which would be timing critical.
-
It forces you to have an int that's always accessable via a reference, which may not be possible if the int is part of another object.
It also prevents you from monitoring writes to that int -- to check for boundary checks, illegal writes, or make other internal state changes depending on the data written.
If it's illegal writes, then likely the method needs to be set to protected or private.
If it's boundary checking, chances are it's modification is part of a bigger function anyway (and thus not merely setting it - I.E. setting the size of a dynamic array, accessing a variable in an array).
Not sure what you mean on 'other internal state changes'?
Point was, you can merge functions into one where applicable.
Really the major reason for my interjection in this thread was your ill-advised operator abuse.
That's a valid enough point. I am one of those people who likes to make it so you can do most things in a few short commands. I've got the numerous classes working, I just need to (re)build the FileProc/HTMLFileProc/StringTokeniser classes where applicable. Despite the protests over the ++/-- operators (which I can understand), you'll like the assignment operators.
Point is, if vector (as a std) does scary inefficient stuff like that
I assume you're talking about copying on resize.
[vector] Recopying on every resize.
It doesn't. It recopies when you exceed its capacity. The capacity can be preset with a call to reserve.
Exceeding it's capacity (or changing it's size) is a resize. It has to copy when it resizes or the data will be lost.
vector guarantees contiguous memory allocation. That's the whole point. It's fast random access. There's no way to keep it all contiguous in memory if you don't move everything when you run out of space.
It's not inefficient if you use it right.
Aside from a hat-tip to realloc, first statement is true but my point is it needs to copy less frequently rather than not at all. Latter statement is true, but classes shouldn't have the capacity to be used wrongly.
It's a kinda bizarro universe dynamic array.
They opt for speed over safety.
It's possible to have both. For example, for TemplateList, CurrRight or CurrLeft will return false if you've reached the start/end (or the list hasn't been initialised yet) but it won't go out of bounds. If you access an item with an uninitialised list, you obviously get a crash (it's avoidable by supplying a static hardcopy but I get the impression this would be frowned upon), but it's down to the user to ensure there's something there.
I am not sure exactly how walking a list could even go out of bounds.
I've been there before. It's easy to find fault in existing implementations and think you can do better. But when you consider how rubust and flexible the standard container classes are, the performance and elegance they offer is surprisingly high. They're very reusable.
I am sure they are very re-usable. In normal circumstances, I try to use as much as the C standard library's functions rather than create my own. My problem is, the STD and STL classes usually require you know precisely what they do, how they do it, and what functions are available. By the time I've researched however many classes, it's probably quicker for me to construct my own class that I understand inside out, and can expand it's functions if the need arises.
The problem I find is 'just one function...' problem where, you reach 50% in your code, and you realise the class or function set you're using hasn't got that 'just one function...' you need (like case insensitivity with strstr, for example, or dynamic memory allocation of sprintf for windows). At which point you either have to draft your own or implement a hacky work around.
I know the hassle of reinventing the wheel. I've been there numerous times. But I also found the hassle of not reinventing certain parts of the wheel.
Optimizing one area of the program won't matter if the bottleneck is elsewhere. Get it working first, optimize later.
Optimisation usually requires you re-write the foundation code in the first place. Which usually means it's better to scrap and redo the code (another code iteration) than to waste hours re-writing a function with a 'jumper string' pulling effect (pull one function, another comes undone).
I find it better to optimise first. More specifically, write short example code to test assumptions, if assumptions wrong, update, if assumptions correct, expand, clarify, incorporate. Test incorporated function. Repeat. Doing this keeps bugs to such a minimum you'd not believe it.
And if it turns out that std::list works fine, you just saved yourself a good month of wasted time and effort.
It's been 6 days since the first post. I have 6 main classes (TemplateList, TemplateArray, CharList, CharArray, TemplateListAdv, CharListAdv). The latter two are the List/Dynamic array hybrids. All the classes can assign to each other (fully tested, no apparent issues). There are 3 additional helper classes. 2 days I spent on the website stackoverflow asking questions to clarify assumptions about inheritance, templates and assignment operators.
Bear in mind I type like a zoned out monkey when it comes to code.
From TemplateList you could easily derive the ImageQueue class (subclass, define as sf::Image or custom class), AnimatedSprite (subclass, single sf::Sprite variable, ImageQueue internal, sf::Clock), etc etc.
Just mentally designing FileProc before I move on.
What's the point of having the list if you have a vector? They're contradictory storage containers.
vector has slow insertion and fast random access
list has fast insertion and no random access.
combining both gives you the worst of both worlds. You can't access the list randomly and you can't insert/remove items in the vector quickly.
Maybe I'm missing the point here.
Actually, combining both gives you the best of both worlds, fast insertion, with random access. The downside would be memory usage (but given it contains pointers rather than copies, overhead wouldn't be that much).
Naturally if you alternate between adding a single item and then single random access you could force it to be inefficient. However it's more intended you add a load of items, access them at random, do some work, access it at random, then add more items, repeat.
It'd be good, for example, for loading a stack of images, then granting you the ability to modify/add images to it later on whilst granting you the ability to rotate which image is selected (using sf::Clock for example) via the [] operator.
-
O(n) is worst-case and O(1) is best case, compared to my own class which is O(1) worst-case and O(1) best case.
Still, you should check with a profiler, if this worst-case O(n) is really a bottleneck and deserves spending so much time on it.
It does. List classes become highly useful when loading files (either in text mode or binary mode), because it's a reported problem using ftell may not accurately return the size of the file (the details were a bit sketchy, but what size the file is depends on which mode (text or binary) it's in). Apparently relying on this caused users issues so I wanted to bypass that altogether - just load the characters via fgetc, whilst counting how many there are in a list.
However, the list needs to be converted into a (dynamic) array, and walking a list of 89000+ is not pleasant. Especially if I plan to load bigger files or more of them. So a definite O(1) is required.
It's not whether or not it's a bottleneck now, but whether or not it will be a bottle neck later on.
Readability is not the exclusive criterion, nor should it really be expected in coding
I strongly disagree with you here. Readibilty is a very important criterion for maintainability and thus should be expected in coding. After all, others are supposed to read your code, too.
Very important criterion in maintainability yes, but code does not always have the benefit of being readable (hence comments, and programming courses), of which assembly is one such example. One cannot push the 'easy to read' element too far, otherwise code performance can suffer.
For example, a coder might complain the bitwise operation/function is not easy to read (?) but if it's the only way of achieving the solution there isn't much point.
If it's any reassurance. I look at other programmer's code/hacky methods and my eyes glass over. Comparatively, the code I'm writing is fairly clear cut (on the lower levels) as to what it is doing (with the help of the occasional comments to clarify specific functions).
It's not explicit - that's the problem.
It's implicit, that "Queue = ImageLoader" appends the image to the image queue.
Given Queue is of a type ImageQueue, it's obvious it queues images. Which means there is only one logical order for it: FIFO.
After all, it could also prepend or insert in the middle.
Not sure why it'll prepend (If you're thinking of LIFO, that's a stack, not a queue). And inserting in the middle is not even logically possible (where's the 'middle' for the first and second item?), even if it was, one would have to ask how that is a queue?
The same goes for overloading the ++ and -- operators. They don't have an intuitive meaning for lists and should thus not be overlaoded.
I'm more of the opinion they should be overloaded even if they aren't going to be used to supply that functionality down the line.
Is there any special reason, why you don't want an STL-like interface?
It's not intuitive enough. Ironically. I can't just pick it and use it, I have to do groundwork research on how they operate. Whilst you'd might say about research is a good practice, it really hinders learning curve. I'll build my tacky classes, once they're set, I'll release them with example code for review and feedback and see what people think of it.
One of the aims is to be able to add such functionality that I could create software with a decent GUI using SFML within a day. I know some coders can write weird code that pulls this off, but I'm a 'zoned out monkey coder', so I want to be able to write straight-forward calls like those above.
-
Point was, you can merge functions into one where applicable.
It's a maintenance thing.
My point was, there are things you can do with separate get/set functions that you can't do with an all-in-one get function. The opposite is not true.
Hence, it limits your implementation.
If your particular implementation should happen to work into an all-in-one interface, then yeah you can combine it.
However, should the implementation need to change in the future (due to additional needs, or a change in overall design, or whatever), it might be difficult/impossible to keep the all-in-one function. Which means you have an API break, which means you have to rewrite not only the class, but all code that uses it.
So yeah -- it's something to avoid.
you'll like the assignment operators.
As long as they make sense conceptually and aren't simply a way to avoid typing out a function name, then I'm fine with it =P
Exceeding it's capacity (or changing it's size) is a resize.
But see, exceeding it's capacity or changing it's size are two different things, which I'm not sure you're grasping.
A vector may only have 10 elements in it, but will have space allocated for 20. (ie: a size of 10, a capacity of 20).
You can add and remove any number of elements to the end of that vector without needing any reallocation, until you exceed 20 elements, at which point, the capacity needs to be increased and the memory reallocated.
See std::vector::reserve and std::vector::capacity. They're different from std::vector::resize and std::vector::size.
Aside from a hat-tip to realloc,
realloc causes complex types to explode, hence why it can't be used in such a class unless you limit that class to contain POD types only.
my point is it needs to copy less frequently rather than not at all. Latter statement is true, but classes shouldn't have the capacity to be used wrongly.
vector actually makes an effort to "guess" as to how much capacity you need in anticipation of future growth. Yeah, it will get it wrong a lot, but it's pretty much impossible to get it right all the time (or even a high percentage of the time).
As for being able to use a class wrongly -- that's where the performance-vs-safety issue comes in. Although in this case we're not really talking about using vector "wrong", just "inefficiently".
Optimisation usually requires you re-write the foundation code in the first place
I don't know about "usually". Sometimes, yeah.
But we're not talking about ripping apart and reoptimizing an entire program, here. We're talking about replacing one linked list with another. They're both going to work more or less the same way, so really there's no reason why they couldn't/shouldn't be interchangable.
I find it better to optimise first. More specifically, write short example code to test assumptions, if assumptions wrong, update, if assumptions correct, expand, clarify, incorporate.
I find that optimizing is a very small part of the actual work I do on a project.
I keep it in mind when designing to avoid doing things that are obviously slow or wasteful, but other than that I just run with it. Running into performance issues that actually needed to be seriously addressed afterward is actually quite rare. C++ is fast.
Bear in mind I type like a zoned out monkey when it comes to code.
I guess I just assumed everyone is as occupied with real life as I am sometimes. =P
Actually, combining both gives you the best of both worlds, fast insertion, with random access [snip]
it's more intended you add a load of items, access them at random, do some work, access it at random, then add more items, repeat.
I guess I'm just having a hard time seeing how this would be useful. Your example at the end of your post didn't make a lot of sense to me. Why would you need to access images randomly?