Your opinion on the functionality of a template dynamic list

[Joshua Flynn]

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.

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.

[Joshua Flynn]

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.

[Silvah]

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.

[Disch]

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).

[Joshua Flynn]

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.

[lefreut]

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).

[Joshua Flynn]

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:

Code: [Select]

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:

Code: [Select]

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.

[bzn]

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...

[Joshua Flynn]

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:

Code: [Select]


//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).

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.

[Joshua Flynn]

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?

[Joshua Flynn]

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.

[Disch]

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.

[bzn]

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?

[Disch]

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.

[Joshua Flynn]

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.