To STL or not to STL, that is the question...

Quote:

---

Originally posted by Yves M
Well, STL is indeed difficult to read if you are not used to templates. If you don't know much of STL it's not making things better either. This is one of the reasons, I guess, students are not really taught to use STL at college. Then again there can be a host of other reasons.

---

Some C++ textbooks are introducing STL right away. For example "Acclerated C++" introduces the "vector" and "string" before talking about arrays and char *

It's all in how you introduce the topic. If a student has never seen a template, then a template won't scare them away and using vector<>, list<>, string, etc. is "natural" to them.

On the other hand, if the same student has been taught procedural, C-like coding, and then introduced to a templates, then things get trickier and more difficult for them to understand.

Here is what Stroustrup has to say in teaching C++.
http://www.research.att.com/~bs/new_learning.pdf

And here is his paper on why C++ is not just an OO language:
http://www.research.att.com/~bs/oopsla.pdf

Regards,

Paul McKenzie

Pardon me if some of this has been covered but I am still reading the post. I have been programing for 5 years now and I have found that there are cases where both are nice but I like the stl much more than the MFC objects.

quote:
--------------------------------------------------------------------------------
Oh and by the way, in STL I can code, say a vector which is full of memory leaks by doing this :



code:
--------------------------------------------------------------------------------
stl::vector<MyClass>
--------------------------------------------------------------------------------


If 'MyClass' has a memory leak in it, then I can't tell where the memory leak occurs, although it's perfectly valid in stl terms.

See what I mean yet ? STL is open to memory leaks !

In programming terms the above is not only possible, but very probable that you would do that.
--------------------------------------------------------------------------------

This is just bad programming by you. You should test out your class before you go using it anywhere.

quote:
--------------------------------------------------------------------------------
Originally posted by darwen
Code should never, ever be released in library form. It should always take the form of COM objects or DispInterface objects.
--------------------------------------------------------------------------------

Answer me this, why would you use MFC in a COM object anyways? I use only STL and ATL code in COM Objects because it reduces the number of dependencies. Also if you are developing a Service or win32 application (non gui) why would you bloat it in size by adding MFC references when the STL would suit the same purpose. Also by using the STL you can then using the same code in a GUI version of the app without having to re-write it.

In the case of derivation, you are just going to pass around an instance of it, so why not write a class where the container behind it is non-dependant and then just have functions to access what you need from the class including the functions to sort. The only time you need to write a function to sort for STL is when the object in the container is a nonstandard object (your on class) and then you just create a function to do the compare and pass that into the sort call.

By using STL anyone who is familiar with C++ (be it Borland under windows, or Linux/Unix programer, or MS Visual Studio Programmer) can look at the code and know what it is doing. Also the STL is developed and tested by some of the best developers in the community and conforms to the ANSI standard. As long as you are using the released build and not the beta builds you are usually sure you are getting a good version of the STL. MFC is hardly updated and some of its code dates back to Windows 3.1 days and hasn't been updated. You only see an updated to the MFC when a new compiler/IDE comes out from MS. If you need support you can get alot of support from the community for both, but if you need an update or a bug-fix, it is released and tested faster with STL.

Also STL is nice cause it is type independant. You only have to write a function for compare or sort which compares what you want and it then handles the rest. This function then works no matter what type of container you use (list, vector, map, etc.) Where as you would have to change and copy the same code if you did it for MFC.

As this is the VC++ forum, a thing to mention when talking about templates and the STL is how badly MS supports them in VC++. When templates first became part of the standard, MS took their time to come up with a VC++ version which supported them at all. And when it came to including the STL, the first implementations they delivered with VC++ were buggy, and the online MSDN documentation regarding the STL is unusable, near to nonexistant. They seemed to express the defiant attitude "OK, so the standard demands that we include the STL. Here it is. Let's see if people will really use it, or continue to use the MFC container, file and string classes as they are supposed to."
Another problem is they way the compiler handles errors in code using templates: Mostly unaware of the template level, on the level of the expanded code. So in most situations, when you have a simple syntax error in code involving the use of templates, instead of getting an error message referring to the statement you wrote, the compiler throws several lines of expanded template code at you, and your first reaction is something like "What the f...! I never wrote that code!" Likewise, whith an error in code calling a member of an STL class, you're likely to end up with the compiler flagging the error in the STL code, not in your code.

Those things, although they have little to do with templates and the STL themselves but with the way MS supports them, are however pragmatical points to consider, and I'm sure they contributed to making many developers reluctant about using STL (or templates in general) in the VC++ environment.

Quote:

---

Originally posted by Adam Gritt
This is just bad programming by you. You should test out your class before you go using it anywhere.

---

This is true. If the class can't be used in an STL container (causes "memory leaks"), it certainly can't be used where copying or assignment will take place, STL or no STL. Just passing or returning the object by value would make it unusable and unstable. I tried to make this point much earlier in the thread, but it wasn't picked up on. Once again:

Code:

---

DarwensClass foo()
{
    DarwensClass dc;
    return dc;
}

int main()
{
  DarwensClass a;
  DarwensClass b;
  a = b;
  DarwensClass c = a;
  DarwensClass d = foo();
}

---

If DarwensClass causes "memory leaks" and crashes when used in a vector, it will cause memory leaks and would more than likely crash the simple program above.

Quote:

---

By using STL anyone who is familiar with C++ (be it Borland under windows, or Linux/Unix programer, or MS Visual Studio Programmer) can look at the code and know what it is doing.

---

Which is the point being made in the previous posts by Yves. We understood what the code posted does, and would understand practically any of the samples given in MSDN. I don't know why darwen believes that others don't understand STL, just because he has a hard time with the syntax not being "clean".

Quote:

---

Also STL is nice cause it is type independant. You only have to write a function for compare or sort which compares what you want and it then handles the rest. This function then works no matter what type of container you use (list, vector, map, etc.) Where as you would have to change and copy the same code if you did it for MFC.

---

For the MFC array containers, you can use std::sort on them and not even have to write your own sort. So even if you did use MFC, the algorithm functions can be used on the MFC array containers. The std::sort is a perfect example of how an STL algorithm "adapts" to any kind of container that has iterators that meet the requirements. The CIntArray, CByteArray, CStringArray, and CArray<> template classes can be used in most STL algorithm functions. I even wrote an entry in FAQ on sorting MFC array containers using std::sort. If anyone hates STL so much as to not even use the algorithm functions, then there is something amiss somewhere.

Regards,

Paul McKenzie

Quote:

---

Originally posted by gstercken
As this is the VC++ forum, a thing to mention when talking about templates and the STL is how badly MS supports them in VC++.

---

MS is making strides with their current VC++ compiler to adhere to the standard (thanks in part to Herb Sutter's contributions). A lot of the template code that couldn't compile with VC 5.0 and VC 6.0 are now compilable with VC 7.0x.

Also, MSDN is not a good reference, even for the C-library functions. I wouldn't count on using MSDN to teach C++ or how to use C++ correctly -- that is reserved for books and the classroom. If you just need a refresher, then MSDN is usable, but IMO you can't use it as a teaching tool. Too many new programmers make this mistake of using MSDN as the "be-all, end-all" in C++ coding, and thus believe that STL is something not important or hard to understand.

Regards,

Paul McKenzie

Quote:

---

Originally posted by gstercken
Those things, although they have little to do with templates and the STL themselves but with the way MS supports them, are however pragmatical points to consider, and I'm sure they contributed to making many developers reluctant about using STL (or templates in general) in the VC++ environment.

---

That is true. I even ran into the issue of purchasing the DinkumWare version over using the VC++( bastardized dinkumware) version. Once I did that I ran into far less problems. With the new .Net 2003 compiler, ANSI support and therefore Template support is much better (98% of standard) and anyone would be hard pressed to find a better compiler right now. As to the Microsoft help, they are probably of the decision "we didn't write it so why should we support the documentation of it". Although it has gotten better, I find much of the development sites out there for STL to provide the most in depth documentation.

Re: Adam Gritt.

Ah but my point is : I've seen code with this sort of memory leak in it. You may say it's bad programming practice, and every class should be tested but : who has time to extrenuously test every class in an application ? I certainly don't.

In fact I've had to fix code with memory leaks such as this in them and it's taken days not minutes to track them down.

No, I didn't write them and yes we do consider the guy who wrote them an idiot which is why he's no longer with the company but in the real world you do have idiots which do things like this. At least the memory leak reporting in VC allows you to fix such things without much trouble.

I must admit saying that things should only be released in COM form was stupid as MFC is a library. I must get my dunce hat on.

In actual fact I've never had a problem with statically linking MFC to apps - these days size doesn't matter (certainly on desktops, palmtops may be another issue).

But then again, aren't I right in saying that templated code is expanded internally by the compiler ? Maybe not, I dunno. But if it is then every call to every class in the STL will be expanded causing the exe size to grow exponentially. Then again, I'm not too sure about this point and I'm sure someone will say its not.
But if I'm right then in very large applications it's much more sensible to use a library such as MFC which is statically linked because it's of a fixed size and doesn't add 50 lines of code for every class member call (or whatever - I'm generalising I know).

Nope, still prefer MFC thanks.

Darwen.

I feel I must add to this discussion.

Darwen: If you hate STL, then don't use STL, it's your right to decide to do so. It's as much a choice whether or not to use STL as is the choice of programming language.
Are you missing out if you don't use STL... yup, you sure are. And you're missing out for not using VB which is much easier for COM, you're missing out for not using Assembly which can be much faster, you're missing out for not using MSDOS which doesn't need a gui....


I've been doing C++ programming for over a decade now. I've probably written a few million lines of C++ code by now.

I've never really needed STL. In fact, In all that time, I've never even written a template class of my own (except for testing/learning purposes). I just never seemed to get a problem where a solution with templates was a better approach than a solution without. And it's generally a bad idea to use features 'just because it's there'.
For MFC code (the large bulk of my Windows apps), the MFC container classes have always managed to do what I needed.

If you're linking with MFC, then it's a good idea to use the MFC containers, because it's there anyway. You don't get any extra size overhead by using them. Using STL however WILL add some extra code.

--
Until some years ago, there was a problem with using templates, because compilers/linkers were fairly dumb. Instantiating entire template classes, even if you used only a small portion of it, leading to bulky exe's (I've seen compilers churn simple bits of C++ code (up to 10 lines or so) into 12Mb exe's).
At least this has disappeared on a module per module basis. But last time I checked (with VC6), it still added plenty overhead if you use DLL's.
If you have many interdependant DLLs, and use identical STL derived classes in them, you end up with instances of the same code over and over and over.
With MFC, there is exactly one instance of the code in the MFC DLL. Regardless of in what DLL's use the container (they do need to link with the MFC DLL of course)
This for me is a big issue. When (just out of curiosity) I changed the code for one project to use all STL containers instead of MFC containers, I ended up with an additional 25Mb of code in a total of 53 DLL's. Quite a severe penalty if you ask me.
Of course... I may be missing out on a compiler feature, C++ language feature or just overlooking the obvious. Anyone care to enlighten me ? :-)

Quote:

---

Originally posted by darwen
Ah but my point is : I've seen code with this sort of memory leak in it. You may say it's bad programming practice, and every class should be tested but : who has time to extrenuously test every class in an application ? I certainly don't.

---

All code should be tested. Extrenuously? Well, there is a point-of diminishing returns. However, checking a class for memory leaks should not be beyond that point.

Quote:

---

Originally posted by darwen
But then again, aren't I right in saying that templated code is expanded internally by the compiler ? Maybe not, I dunno. But if it is then every call to every class in the STL will be expanded causing the exe size to grow exponentially. Then again, I'm not too sure about this point and I'm sure someone will say its not.
But if I'm right then in very large applications it's much more sensible to use a library such as MFC which is statically linked because it's of a fixed size and doesn't add 50 lines of code for every class member call (or whatever - I'm generalising I know).

---

First off, as you guessed, you are wrong about the "exponential" growth. Usually (the specifics are left to the vendor of the compiler), the compiler will expand the definition for a class or function once and compile it. Not all template code is inline. In this case the growth would be linear -- on par with just about any other code.

Second, the complaints you mention would apply to all template classes and functions, not just to the STL. It seems that you don't like templates, not just the STL. Is this a fair assessment?

Last, MFC adds a few hundred thousand if not million lines of code behind the scene and can add MB's to the size of memory an application takes in memory. Usually using template code (STL or not) will not add that much. However, OReuben is correct in that if you are already using MFC, then using the MFC containers will not add more overhead, whereas using templates (or the STL) will (though probably not as much as you think).

Anyway, if you don't like templates, don't use them. Those that feel comfortable using them will.

- Kevin

OReubens:
Yes indeed, STL is inline so it's expanded by the compiler. There are various mods that will change that separate link instances based on class type which can minimize on the overhead.

Not that I wanted to get into all this again but since my buddy over there has realized its not some much fun on the receiving end of the abuse, and I think this can be settled easily so here it is:

STL Vector push_back will be my benchmark example:
All code is from 'vector' header file in VC6. I do understand they cleaned it up in .NET which is nice.

Code:

---


void push_back(const _Ty& _X)
    {insert(end(), _X); }
void insert(iterator _P, size_type _M, const _Ty& _X)
    {if (_End - _Last < _M)
        {size_type _N = size() + (_M < size() ? size() : _M);
        iterator _S = allocator.allocate(_N, (void *)0);
        iterator _Q = _Ucopy(_First, _P, _S);
        _Ufill(_Q, _M, _X);
        _Ucopy(_P, _Last, _Q + _M);
        _Destroy(_First, _Last);
        allocator.deallocate(_First, _End - _First);
      _End = _S + _N;
      _Last = _S + size() + _M;
      _First = _S; }
    else if (_Last - _P < _M)
        {_Ucopy(_P, _Last, _P + _M);
        _Ufill(_Last, _M - (_Last - _P), _X);
        fill(_P, _Last, _X);
        _Last += _M; }
    else if (0 < _M)
        {_Ucopy(_Last - _M, _Last, _Last);
        copy_backward(_P, _Last - _M, _Last);
        fill(_P, _P + _M, _X);
        _Last += _M; }}

---

I think its been decided that one letter variable names is bad programming....and very bad design. All the other functions are inline as well and in that header file.

Since this is inline, you can expand that mess and see that you're looking at around 20 odd lines of inline code per insertion. Generally more lines, more overhead...Never mind the overhead from the assignments.

Here is my own 'vector' style class. Has all the fat cut out and is drop in compatible with vector.
Its a template class for generic list type.
tpListType is the generic list type.

Code:

---

//linknode is defined to have a tpListType data, and linkNode<tpListType> prev and next ptr. Simple dblLinked list config.
bool push_back(const tpListType& Elem){
    if(!first){
        first = new linkNode<tpListType>;
        if(!first) return false;
        first->data = new tpListType(Elem);
        if(!first->data) return false;
        last = first;
        NumberOfElements++;
        return true;
    }
    else{
        linkNode<tpListType>* ptr = new linkNode<tpListType>;
        ptr->data = new tpListType(Elem);
        if(!ptr->data) return false;
        ptr->next = 0;
        ptr->prev = last;
        last->next = ptr;
        last = ptr;
        NumberOfElements++;
        return true;
    }
}

---

Easy to read, completely encapsulated, meaning, that no outside user can modify internal data, once in list, the internal data can only be modified by the class though calls. This protects the data from anybody using it. I consider this good design. When you build a car, you don't let a driver easily reach in and yank on the valves. Don't have to worry about list size being wrong since nobody should be messing with variables like NumberOfElements.
I believe its understood that user safe objects are good design.

And then there's CArray which just isn't worth the hassle of pasting....

Benchmarks:
Compiled in release, would do debug, but I'm still waiting for CArray to come back....

std::vector<int>
MyTemplateList<int>
CArray<int, int>

this loop on a Pentium 2Ghz machine for each list, 1 millions inserts
for(int i = 0; i < 1000000; i++){
// add 1 element
}

vector.push_back(i) = 1.2 seconds.
MyTemplateList.push_back(i) = 0.6 seconds.
CArray.Add(i) = 12 seconds.

So as you can see, and feel free to try, user written is fastest (providing done right), STL is middle and CArray is so poor that last is too good for it....
But to give CArray some credit, its far more defensible and easier to debug then STL.

So you decide which you feel is "better"....Again I vote user written because you control the performance and you know you can be at least as fast as the library, have more functionality and be better designed, which is everything you could want in a program or library.

Why are you comparing vector.push_back() with your list's push_back(), compare with std::list's push_back, it's obvious that inserting in vector is more expensive than in list.

Actually, I bet vector<>.push_back would be much, much quicker (than even list<>.push_back) if you reserved the memory beforehand:

Code:

---

std::vector<int> x;

x.reserve(1000000);
for(int i = 0; i < 1000000; i++){
    x.push_back(i);
}

---

Quote:

---

Originally posted by oktronic
vector.push_back(i) = 1.2 seconds.
MyTemplateList.push_back(i) = 0.6 seconds.
CArray.Add(i) = 12 seconds.

So as you can see, and feel free to try, user written is fastest (providing done right), STL is middle and CArray is so poor that last is too good for it....
But to give CArray some credit, its far more defensible and easier to debug then STL.

---

Set aside the readability of the code: What you have implemented here is a linked list, not a vector. And while a vector's strong point is to access elements in constant time using an index, the cost for inserting and removing elements depends highly on the implementation (especially the strategy used to resize the array when needed), and that's why CArray is so slow here: With its default grow value, it is not optimized for insertion of a large number of elements at the end. You can easily change that if you call SetSize(1000000) and then re-run your benchmark.
In contrast, the data structure you implemented (a linked list) is especially efficient at adding elenments at the end (the case you have used for the benchmark), but what about running a benchmark which tries to retrieve an element at an arbitrary index n times?
Anyway, given that you cheated by comparing a linked list with a vector for appending elements at the end, I think that std::vector does a terribly good job in taking only twice the time as your linked list implementation... ;)

Quote:

---

Originally posted by oktronic
Here is my own 'vector' style class. Has all the fat cut out and is drop in compatible with vector.

---

Just to add to others comments:

a)Your version returns a bool -- vector::push_back() returns void.

b) Current standards state that when "new" fails, a bad_alloc exception is thrown, not a NULL return value. It may work for VC 6.0 and maybe the current version of VC 7.0, but from all indications, MS will start to use the standard way to report a failure of operator new, so your code will have to be rewritten if you port it to a newer version of VC++ (or another compiler).

c) Your code assumes that the allocator is operator new[], and not a possible custom allocator.

d) Not seeing your constructor, operator =, or copy, it's hard to put up timing just for push_back. It all depends on what you want to do, and real programs don't just call push_back. Also, do you have a reserve() function for your class? If not, did you try this code:

Code:

---

std::vector<int> IntV;
IntV.reserve(1000000);
for(int i = 0; i < 1000000; i++)
{
  push_back(i);
}

---

This should run somewhat faster than the time you posted (maybe still not as fast as your version, but it should be faster).

Maybe some MFC expert on CArray can chime in on whether there is a "reserve"-like function for CArray. If there is, you need to re-time the tests, taking in consideration that these functions exist.

Regards,

Paul McKenzie

Quote:

---

Originally posted by KevinHall
Actually, I bet vector<>.push_back would be much, much quicker (than even list<>.push_back) if you reserved the memory beforehand:

Code:

---

std::vector<int> x;

x.reserve(1000000);
for(int i = 0; i < 1000000; i++){
    x.push_back(i);
}

---

---

Hey, you beat me to it!

Regards,

Paul McKenzie

Quote:

---

Originally posted by gstercken
Set aside the readability of the code: What you have implemented here is a linked list, not a vector.

---

Good catch. It is a linked list and not a "drop-in" for vector, especially if you rely on vector's contiguous storage requirements (which linked lists do not have).

However, don't be surprised if the version of vector<> that has the resize call comes close, if not beat the posted linked-list version.

Regards,

Paul McKenzie

Comparing 1Mil inserts into a LIST to 1mil inserts in a dynamic array, and of course it's going to be slow. You can't compare oranges and apples.

CArray is a dynamically growing array which starts at size 0, and dynamically adjusts itself as you insert items. Retrieving items is fast (as fast as getting from a pointer to a static array). Inserting/deleting gets to be slow because of continuously having to reallocate and move/copy the array contents.
CList (double linked list) would've given comparable results. to the STL class.

Unless you specify otherwise, CArray will grow exponentially (but minimum 4), but using SetSize() you can specify an initial size and a grow-by size (which'll result in linear growth).

Quote:

---

Originally posted by Paul McKenzie
However, don't be surprised if the version of vector<> that has the resize call comes close, if not beat the posted linked-list version.

---

Actually, I would dare to state even without trying it that both CArray and std::vector with a preallocated size will beat his implementation by far, only due to the memory allocation overhead with the linked list.

Code:

---

void list_test()
{
    std::list<int> li;
    int i;

    for (i=0; i<1000000; ++i)
    {
        li.push_back(i);
    }
}

void vector_test()
{
    std::vector<int> vi;
    int i;

    vi.reserve(1000000);
    for (i=0; i<1000000; ++i)
    {
        vi.push_back(i);
    }
}

---

I ran this code (release build with MSVC 6.0) and profiled it 30 times (with us resolution). Here are the results:

list_test(): 905.5 +/- 3.7 ms
vector_test(): 89.1 +/- 1.1 ms.

So it looks like that if you reserve the space beforehand, just using push_back() (not inserting at the beginning or the middle of the vector), that std::vector is 10 times faster than std::list for MSVC 6.0 release builds.

MSVC 6.0 debug build results are similar (though showing only factor of 4 difference):

list_test(): 8.3 seconds
vector_test(): 2.0 seconds

Quote:

---

Originally posted by KevinHall
So it looks like that if you reserve the space beforehand, just using push_back() (not inserting at the beginning or the middle of the vector), that std::vector is 10 times faster than std::list for MSVC 6.0 release builds.

---

Yeah, that sounds plausible. Now, while you're at it already, would you mind adding oktronic's code to your benchmarking? Just for interest...

I'll try. He didn't leave very complete code to compare though.

- Kevin

All there have reserve functions.
reserve for mine and STL and SetSize in CArray.
The object of the benchmark was to compare all three in the same situation and see how they held up. I'm pretty confident that the spread will remain the same if all situations were tested.

In mine, the new operator is overloaded for custom memory allocation and for reserved memory operations. In this benchmark they all used default release mode new. So each had to grow dynamic. Which is important test since 90% of the time you don't know how much you are going to hold, such as a stream of data unless its polite enough to give you its size first. Many programs have the "Here's a bunch of data" philosophy.

If I did all the benchmarks again with reserved memory, you would find that, while they all would be faster, that the spread would be about the same.

All three have a operator[] for indexing and assignment.
Mine only has retrieval not assignment to protect against array out of index. Done on purpose to force users to use the provided functions. By doing so, I don't get calls where I get blamed for exceptions, well I still get blamed, but I get a nice fee when I find the problem in the users code.

Generally I don't use standard exception handling. I have a set of custom handling to let everything shutdown as nice as possible. In several programs I have complete custom memory allocation which takes care of any and all exceptions and cleans up. While NT up has better handling then the older versions, my software must run unhindered on any windows system with full error reporting, so I can't slap blue screens at people. That's why I return bool, which will drop into replace vector. I think its pretty decided (except with MS with doesn't always) that a bool return type means, it worked or it didn't, so anybody using the class will need to check to ensure success, which is faster and less code for them then try-catch blocks and if there's a full system error and if you're using my construct, you'll be politely informed of the error and the program will even offer to save, clean up and restart the program an bring you back you were, if possible.
So I use boolean returns often and let the programmer or program construct manage the error.

as for operator[], vector would probably be a little faster since all it does is get the begin pointer and add the offset. However if you're out of index it will crash. Mine on the other hand, verifies the index to be in bounds and will return an empty object type if it is, but I return a value not a reference so I can do that. The overhead for this check is minimal though and if you consider the time spent inserting the elements and the index time, the total time will still be in favor of mine, never mind the bonus of having a class that doesn't crash. Which again, I feel any SDK can have both performance and user safety, which STL doesn't provide. MFC has the full advantage over STL in safety at the sacrifice of performance.

So again, its user preference, if you want a class that will not crash no matter what values you give it, or what functions you call, as well as some kickin' performance, create your own and put all you want in it.
You want some good performance and the price of debugging, user safety and your head exploding while looking at one of the header files, then use STL.
And if you want something "Microsoft" safe, completely "Microsoft" compatible, at the expense of some serious performance, then use MFC.

Quote:

---

Originally posted by oktronic
All there have reserve functions.
reserve for mine and STL and SetSize in CArray.
The object of the benchmark was to compare all three in the same situation and see how they held up. I'm pretty confident that the spread will remain the same if all situations were tested.

...

If I did all the benchmarks again with reserved memory, you would find that, while they all would be faster, that the spread would be about the same.

---

Pretty confident statement. Mind if you send me your code so I could test it?

Quote:

---

Originally posted by oktronic
In mine, the new operator is overloaded for custom memory allocation and for reserved memory operations. In this benchmark they all used default release mode new. So each had to grow dynamic. Which is important test since 90% of the time you don't know how much you are going to hold, such as a stream of data unless its polite enough to give you its size first. Many programs have the "Here's a bunch of data" philosophy.

---

But you still have not addressed the issue of using a linked list rather than a vector.

Quote:

---

Originally posted by oktronic
All three have a operator[] for indexing and assignment.
Mine only has retrieval not assignment to protect against array out of index. Done on purpose to force users to use the provided functions. By doing so, I don't get calls where I get blamed for exceptions, well I still get blamed, but I get a nice fee when I find the problem in the users code.

---

You're just limiting the feature set here. Nothing that really affects performance.

Quote:

---

Originally posted by oktronic
That's why I return bool, which will drop into replace vector. I think its pretty decided (except with MS with doesn't always) that a bool return type means, it worked or it didn't, so anybody using the class will need to check to ensure success, which is faster and less code for them then try-catch blocks and if there's a full system error and if you're using my construct, you'll be politely informed of the error and the program will even offer to save, clean up and restart the program an bring you back you were, if possible.
So I use boolean returns often and let the programmer or program construct manage the error.

---

Handling "problem cases" should not be taken into consideration of performance.

Quote:

---

Originally posted by oktronic
as for operator[], vector would probably be a little faster since all it does is get the begin pointer and add the offset. However if you're out of index it will crash. Mine on the other hand, verifies the index to be in bounds and will return an empty object type if it is, but I return a value not a reference so I can do that.

---

That's not necessarily true. The user can catch an exception. And what is an "empty" object? For an integer, is that zero? How would a program differentiate an "empty" integer from a valid integer? This could be very, very important for an application!!!

Quote:

---

Originally posted by oktronic
So again, its user preference, if you want a class that will not crash no matter what values you give it, or what functions you call, as well as some kickin' performance, create your own and put all you want in it.

You want some good performance and the price of debugging, user safety and your head exploding while looking at one of the header files, then use STL.

---

:rolleyes: Ok... if users don't want to catch exceptions that they know could be thrown, then yes a program can crash. However, the user would just then not be checking for errrors. In the case of your class, that would be analogous to the user not checking the return value of push_back. What would happen to a user application if they didn't catch that? I'm not sure.... it depends on the user app.

In the end though, you still have not addressed the issue of linked list vs. vector. Please comment!

Quote:

---

Originally posted by oktronic
In mine, the new operator is overloaded for custom memory allocation and for reserved memory operations.
...
Mine only has retrieval not assignment to protect against array out of index. Done on purpose to force users to use the provided functions. By doing so, I don't get calls where I get blamed for exceptions, well I still get blamed, but I get a nice fee when I find the problem in the users code.

Generally I don't use standard exception handling. I have a set of custom handling to let everything shutdown as nice as possible.

---

These alone are all contradictions to the statement you made before: That your class is "drop in compatible with vector".

Besides that, you didn't get into the problem that your implementation is no vector / array, but actually a linked list.

oktronic,

So you have something that is easier for you to debug. Great! I just don't believe all the other big claims you made. And for others, the STL might be easier to use than your class. Personally, in most cases I'd rather catch an exception for the "problem" cases than constantly having to check a boolean return value.

But we're still interested in your opinion on the linked list vs. vector issue.

- Keivn

Quote:

---

In mine, the new operator is overloaded for custom memory allocation and for reserved memory operations. In this benchmark they all used default release mode new. So each had to grow dynamic. Which is important test since 90% of the time you don't know how much you are going to hold, such as a stream of data unless its polite enough to give you its size first. Many programs have the "Here's a bunch of data" philosophy.

---

Again the methodology for choosing the next larger size is a tradeoff of speed vs memory.
A system that uses a larger growth step will be faster because it needs fewer resizes, at the expense of more memory consumption.
It's unfair to compare the default method of one class to another one.

Suppose I wanted to fake good results in your benchmark. I could design a class that would grow the size by 1mil items on the first attempt, and I'd get the best benchmark. Benchmarks are only fair given identical systems. otherwise you also need to account for the difference in the way they handle things. Soemtimes memory consumption will be at a premium, and sometimes speed.

Quote:

---

Generally I don't use standard exception handling. I have a set of custom handling to let everything shutdown as nice as possible.

---

OOoh, BAD BAD BAD. I would never want a library that on it's own shuts down because of calling an out of bounds. The proper C++ way is to thrown an exception so that possibly the code can correct/solve the out of bounds in a proper way. An out of bounds isn't necesarily a reason to have the app terminated.

The user (==programmer) of the class should decide what to do with an out of bounds. not the class itself.

Quote:

---

Mine on the other hand, verifies the index to be in bounds and will return an empty object type if it is

---

I have several classes I use in CArray's that don't have anything close to a "empty object". I don't think it's agood idea to assume you can always create an empty object.

Quote:

---

but I return a value not a reference so I can do that.

---

This again comes at a penalty. It requires a temporary object to be created. This is trivial for a simple type like an int, but calling a copyconstructor/assignment operator can be a big issue for some objects.
Again, I have classes where I have an array of references to objects, if it'd have arrays of objects (or even returned objects on each call to []), the code would be noticably slower.

Ok, so I've tested what I think oktronic's class looks like (again 30 tests with MSVC 6.0 release build). Here are the results (and to be fair to oktronic, I don't have the sources to his class):

list_test(): 908.1 +/- 1.9 ms
MyTemplateList_test(): 898.9 +/- 7.0 ms
vector_test(): 91.9 +/- 1.4 ms

So, it would appear that oktronic's class's push_back() may be a bit faster (although it is awefully close considering the possible timing errors). PLEASE NOTE: This test is not representative of all functionality of any class (please see OReuben's comments above).

- Kevin

Code:

---

template <typename tpListType>
class linkNode
{
public:
    tpListType* data;
    linkNode<tpListType>*  prev;
    linkNode<tpListType>*  next;
};

template <typename tpListType>
class MyTemplateList
{
    linkNode<tpListType>*  first;
    linkNode<tpListType>*  last;
    size_t                  NumberOfElements;

public:
    MyTemplateList() {first=last=NULL; NumberOfElements=0;}

    //linkNode is defined to have a tpListType data, and
    //linkNode<tpListType> prev and next ptr. Simple
    //dblLinked list config.
    bool push_back(const tpListType& Elem)
    {
        if(!first){
            first = new linkNode<tpListType>;
            if(!first) return false;
            first->data = new tpListType(Elem);
            if(!first->data) return false;
            last = first;
            NumberOfElements++;
            return true;
        }
        else{
            linkNode<tpListType>* ptr = new linkNode<tpListType>;
            ptr->data = new tpListType(Elem);
            if(!ptr->data) return false;
            ptr->next = 0;
            ptr->prev = last;
            last->next = ptr;
            last = ptr;
            NumberOfElements++;
            return true;
        }
    }
};


void MyTemplateList_test()
{
    MyTemplateList<int> li;
    int i;

    for (i=0; i<1000000; ++i)
    {
        li.push_back(i);
    }
}

---

Quote:

---

Originally posted by KevinHall
So, it would appear that oktronic's class's push_back() may be a bit faster (although it is awefully close considering the possible timing errors). PLEASE NOTE: This test is not representative of all functionality of any class (please see OReuben's comments above).

---

A bit faster... than std:list, of course, but still about 10 times slower than std::vector, which is what he actually claims to replace by his implementation.

Quote:

---

Originally posted by gstercken
A bit faster... than std:list, of course, but still about 10 times slower than std::vector, which is what he actually claims to replace by his implementation.

---

I know. And that of coarse ignores the other performance issues OReuben brought up.

The whole purpose of STL (and the MFC container classes, and almost any other library I know for that matter) is to provide the programmer with a toolkit of adequately tested classes/functions that perform well under most circumstances limiting worst-case scenario's as much as possible, and providing a workable tradeoff between speed and memory usage.

And as with any tradeoff, it's sometimes not going to be good enough. I have had my share of problems where 'generic' solutions just wouldn't do. Reinventing the wheel (but with added grip and better profile for wet surface and a chery on top) is sometimes necessary.

It's hard to do decent benchmarking. Last time you checked... how many times did you actually had to write real code that did:

Code:

---

for (i=0; i<1000000; ++i)
    {
        li.push_back(i);
    }

---

;-)

Again, very true. I was just trying to use oktronic's test for comparison against his own claims.

Sorry you guys posted while I was posting, so I'll try to answer your questions.

Quote:

---

In the end though, you still have not addressed the issue of linked list vs. vector. Please comment!

---

My class can handle dynamic or static memory, contiguous or linked. More specifically, you can hand it any type of memory and it will use it until your size limit is hit, and then it will go dynamic, or fail depending on options. If you refer to the vector code, you'll see that's all it is, a dbl-linked list container. It has some extra functionally, but still, inside that's all it is. Unless you are only defining a linked-list as only a dynamic list?

This includes file buffered memory handling, since some lists are far to great of size to use in memory.
So you can hand it whatever you want and it will work with it, I've built in many different ways, such as file buffering, however, you can assign your own allocator just like vector does. Multiple storage ways are necessary for things like external memory, such as a video card. I try to pack functionality in where I can.

Quote:

---

This alone is a contradiction to the statement you made before: That your class is "drop in compatible with vector".

---

Agreed, this is one case where it doesn't drop in perfectly. This is because vector isn't safe with types. However, you can specify what you wish to be a error value in your empty type. Which is really just a dummy type with the value that I return, if none is specified, then its just a empty type of the list type. The object of the class is to be perfectly safe. I've eliminated try-catch handling aswell which is another change. But really what I'm trying to avoid is the user dropping in my class and 100s of things don't compile. This way, the program will compile and the user will need to make some modifications to use the additional features. Generally I only do 100% drop in for controls, where I can.

Quote:

---

I'll try. He didn't leave very complete code to compare though.

---

Sorry Kevin, I'd love nothing more then to post it, but I don't make up the rules...

However the principle is very easy. I did edit that code I provided to remove debug stuff, but the rest is pretty standard double-linked list. Just need a front and back pointer and a node that holds the data, prev and next pointers and you should be pretty accurate. If you are going contiguos then drop the prev and next pointers and use offsets. If you want, and trust me to do so fairly, you can give me any tests you would like and I'll give you the results.

But honestly, STL isn't going to be able to beat it out for the one reason of that STL does more. For allocator class it has to be instantiated, the iterators need to be assigned, additions and so forth. I keep track of everything, which I can do safely since nothing can me modified externally.
A worse class is map. I was going to use it as my example but between map and xtree its a mess and my replacement class is optionally balanced so I would have had to chop it up to get a comparable benchmark that you could work with.

Quote:

---

Originally posted by oktronic
If you refer to the vector code, you'll see that's all it is, a dbl-linked list container.

...

But honestly, STL isn't going to be able to beat it out for the one reason of that STL does more. For allocator class it has to be instantiated, the iterators need to be assigned, additions and so forth. I keep track of everything, which I can do safely since nothing can me modified externally.

---

std::vector is NOT a linked list!!!

Quote:

---

Originally posted by oktronic
If you want, and trust me to do so fairly, you can give me any tests you would like and I'll give you the results.

---

Try the tests I posted and used including the reserve(). Of coarse as OReubens pointed out this isn't real-world, but it would be interesting nonetheless.

- Kevin

First for kevin:
Check out the STL code Vector in the include directory. You will find that it is indeed a linked list. But again, if you are defining a linked-list as only a dynamic, then yes and no, however at the system level, it most definently is.

I think we need to agree on a few points.
One, when compiled, the code with the fewest intructions are going to be processed in less time if the same memory allocation and retieval.

Second. If you have pre-allocated memory, its going to be accessed faster then memory you have to allocate then access.

This seems to be the biggest issue.

If you take my code and break it into instructions, you will find that it has less instructions then vector. You can tell this simply by the number of lines of code in each since they essentially do the same thing, however you can grab the ASM from VC and check yourself. Second, if both are running the same memory routine, that the one with the least instructions will process faster.
Since the main concern is memory. First, Windows is has a linked-list memory implementation. Which means, that when you allocate memory, even on the stack, it is not contiguous. The system is the only thing that stores stuff contiguously. You can look this up if you feel I'm not being accurate.

So what this means, is that give the same memory constraints, whether heap, register or stack, pre-allocated or dynamic, that the one with the least amount of instructions is going to be faster.

Which is the case with my sample. You can count the STL C++ lines and see that there are twice as many. It still has to allocate the memory somewhere and as long as both allocate the same way, mine will be faster no matter what machine you run it on.

As for the sample test, its purpose was to give all three the most common used implementations. Which is dynamic growth at 1 element per insertion. Which is what that sample did. Sure if you pre allocate one and make the other grow one at a time, the one that grows with slow down.

for Kevin:

Quote:

---

OOoh, BAD BAD BAD. I would never want a library that on it's own shuts down because of calling an out of bounds.

---

The class doesn't shut the system down, the construct (aka framework) does. There are plenty of functions that can be set up to do any form of custom handling.

PS: lol, sorry for all the editting, I'm in a hurry to go home and am not checking my grammer. Which I'm going to head out, I'll hopefully answer any other posts later.

Quote:

---

Originally posted by oktronic
First for kevin:
Check out the STL code Vector in the include directory. You will find that it is indeed a linked list.

---

Excuse me, but:

Code:

---

std::vector<int> s(2);
s[0]=129;
s[1]=981218;

int *arr=s.begin();
if(arr[1]==981218) // if this is safe
        cout << "definitely not a list";

---

This is in MS and SGI STLs.

Quote:

---

Originally posted by oktronic
First for kevin:
Check out the STL code Vector in the include directory. You will find that it is indeed a linked list.

---

A vector is guaranteed to have its storage in contiguous memory, just like an array. I don't see how this can be a linked list, especially when a vector<T> can be used with legacy functions that require a pointer to a buffer of T.

Code:

---

#include <vector>

void LegacyFunc(int *pInt, int nItems)
{
}

int main()
{
  std::vector<int> IntList(5);
  LegacyFunc(&IntList[0], IntList.size());
}

---

This code is guaranteed to work correctly, since vector's internal data representation is a contiguous buffer, not a linked list. If your linked-list class can be used as above, then you can compare it with vector (even if you call it linked-list). If it cannot be used as the code above uses it, it is not compatible with vector, and you are comparing apples with oranges.

Regards,

Paul McKenzie

Quote:

---

Originally posted by oktronic
First for kevin:
Check out the STL code Vector in the include directory. You will find that it is indeed a linked list. But again, if you are defining a linked-list as only a dynamic, then yes and no, however at the system level, it most definently is.

---

from the file "vector" found in C:\Program Files\Microsoft Visual Studio\VC98\Include

Code:

---


template<class _Ty, class _A = allocator<_Ty> >
    class vector {
public:
    typedef _A::pointer _Tptr;

    //...

    typedef _Tptr iterator;

    //...

protected:

    //...

    iterator _First, _Last, _End;
};

---

Using the standard allocator, the iterator is a pointer an object. Thus we would have something like:

Code:

---

class int_vector {

protected:

    int* _First, _Last, _End;
};

---

This is certainly NOT a linked list. A linked list would need a pointer to a node, which is most definately not what this is. As the Paul and AvDav have pointed out, a vector must be allocated in the same way an array is -- i.e. in contiguous memory.

Quote:

---

Originally posted by oktronic
I think we need to agree on a few points.
One, when compiled, the code with the fewest intructions are going to be processed in less time if the same memory allocation and retieval.

---

I believe this is incorrect. Not all assembly instructions take the same amount of time to execute. And we should all know better than assuming that all C++ instructions take the same amount of time to execute. Let us take a look at an extreme example:

Code:

---

void a()
{
    int i;
    int x;
    for (i=0;i<1000000000;++i)
        x = i;
}

void b()
{
    double x = sqrt(2.0);
    int z = x;
    cout << z << endl;
    string s("Hi there!");
    cout << s << endl;
}

---

*Which of these two functions has fewer assembly instructions?

*Which of these two functions has fewer C++ instructions?

* Which will run faster?

Quote:

---

Originally posted by oktronic
First, Windows is has a linked-list memory implementation. Which means, that when you allocate memory, even on the stack, it is not contiguous. The system is the only thing that stores stuff contiguously. You can look this up if you feel I'm not being accurate.

---

Are you saying that the following:

Code:

---

int* x = new int[500];

---

will not allocate contiguous memory for x?

Quote:

---

Originally posted by oktronic
for Kevin:

quote:
--------------------------------------------------------------------------------
OOoh, BAD BAD BAD. I would never want a library that on it's own shuts down because of calling an out of bounds.
--------------------------------------------------------------------------------

---

That wasn't me who stated that. :D

- Kevin

Ok, we're going to need to take a step back here.
I'm talking on a system level and you're talking C++ semantics.

int* ptr = new int[50];

while this is "contiguous" relative to a C++ interface. However, at the operating system level, it isn't.
Window's uses a linked list implementation to store memory.
This is how it allows memory segmentation.
So even though you asked for 50 ints, that memory can be scattered anyway through out memory with pointers at segmentation points that point to other locations. Not that I can remember back that far, but I believe this is called paging.
This is also why when you have, let’s say 2GBytes of system memory, that when you ask for 1 Gig that it may very well fail. This is because you are asking for 1 Gig and they system will actually require more for pointers to each segment.

This article has some useful information. However, its incomplete as its hard to find decent references for this. But it should show you that you're memory is segmented by the operating system with pointers between segments done as pages. The operating system determines all this for you.

http://www.cs.wpi.edu/~claypool/cour...slides/mem.pdf

Here a more advanced example.
Again, I didn't read through looking for his errors as I'm sure there's going to be a few since I think its a graduate assignment,
but from the brief scan it looks ok, just don't hold anything he says as gospel.

http://www.cs.buffalo.edu/~bina/cse4...02/VMOct17.pdf

While looking at .NET, I've noticed that they have re-written STL in .NET and while its still a mess, its much cleaner then its predecessor, they've replaced single variable names with actual names. And I've noticed that they have added exception handling into their class, which now means that they will have even more overhead while using STL, but its now a little safer.

But anyway, what the memory stuff means is that iterating between "contiguous" and between a list of pointers to elements may take the same amount of time, since the memory you're using very well is a list itself.

But besides all this, since vector is indeed reallocating its entire memory block each time, then wouldn't that be horribly inefficient? As I said before, data streams, such as a character array, rarely give you their size first, they usually have a terminator, such as a string has a NULL and a file an EOF.
So I recommend trying the 2, allocate a chunk of memory for my linked list to hold the data and shift the pointers around and then try the same block size for vector. I think you'll be surprised at the difference in performace.

So I'll shift terminology, been working a little too much at the system level as of late.

So I'll add another negative to STL, horrible memory management using shifting contiguous memory for allocation forcing the system to keep shifting memory around to compensate.

Quote:

---

Originally posted by oktronic
But besides all this, since vector is indeed reallocating its entire memory block each time, then wouldn't that be horribly inefficient? As I said before, data streams, such as a character array, rarely give you their size first, they usually have a terminator, such as a string has a NULL and a file an EOF.

...

So I'll add another negative to STL, horrible memory management using shifting contiguous memory for allocation forcing the system to keep shifting memory around to compensate.

---

Why would std::vector need to reallocate memory every time if it really a linked list?

As far as bad memory management goes, that's something that is a trade off in performance -- std::vector is more efficient in accessing members; std::list (and your class) are more efficient in adding members at random places in memory. If you know ahead of time that you'll just keep adding members at the end, then std::vector can be more efficient (see the results of my test earlier or perform the tests you said you would perform).

Aarrrgghhhh.... It doesn't matter. I don't think you'll understand what I, Paul, AvDav, gstercken, OReubens are saying.... or anyone else for that matter. Oh well!

- Kevin

[QUOTE]Aarrrgghhhh.... It doesn't matter. I don't think you'll understand what I, Paul, AvDav, gstercken, OReubens are saying.... or anyone else for that matter. Oh well!
[QUOTE]

Unfortunately Kevin, I feel that you don't understand, the mentioned linked list is in the system, I provided 2 documents to help explain that. If you don't understand them, please feel free to ask me any questions, but please do not tell me that I don't understand. I understand I've gone a little beyond the scope of just STL, but your belief that a pre-allocated "contiguous" memory is faster then a external pre-allocated linked-list implementation is flawed at the system level.

[QUOTE]stdvector is more efficient in accessing members; stdlist (and your class) are more efficient in adding members at random places in memory[QUOTE]

More efficient then what?

vector does this begin() + elem for operator[].

are you telling me that this:

int ptr = new int[50];

int a = ptr + 50;

is more effiecent then a dereferencing a pointer?

int a = *tempptr ;

if you read the documentation, you would see that the call
ptr + 50
is actually a reference to an address, then the system has to iterate through memory to the page frame that contains element 50.

if you were to simply dereference a pointer to that address like so

*tempptr;

then all the system has to do is go to that address....you do the work for the system instead of the other way around.

So while I'm busy misunderstanding, can you explain to me why using my own list is more inefficient then iterating through system memory list to the 50th element? The hit in memory allocation comes from the system having to allocate a chunk of memory and set up the memory in the system. If you pre-allocate memory, just like vector does, then you don't have to ask the system memory for the hit, and all you have to do is copy the data into the pre-allocated memory. Which is the same thing that vector does except that I have pointer to each of the elements. An extra 8 bytes of data per node. Then I iterate through the list, just as the system would have to, to reach the element you want. But there is a minor hit, but were?

I actually know the answer, and you will find the answer in the documentation provided, but the question I have for you Kevin, is can you find it?

Now personally, I think I'm going beyond the scope of this thread, so I'd recommend that everybody take Kevin's example, pre-allocate memory for data storage and run your benchmark. I think that speaks for itself.

First, why are we comparing personal code to STL code? I thought this was supposed to be MFC vs STL. However, before we can really decide that we have to agree to what implementation of the STL we are going to look at. MFC is usually either 4.2 or 7.0/7.1 (4.2 was what shipped with VC6). With STL you can use the default that comes with VC6, or VC7.0/7.1 or you can use SGI or STLPort or Dinkumware. Each one, although similar in its interface, does differ in its implementation. Also you can't complain about Memory Leaks in STL without saying the same of MFC because both have become time tested now. If memory leaks exist then either you did some improper programing using them or its your object that has the problem. I have run into cases where it was an implementation problem in the use of MFC or STL.

Now, when programming with MFC you usually end up including the world in your application. No matter where you are (with a few exceptions) you can create any MFC object that exists without have to change the includes as long as you are linked back to stdafx.h. With STL though you tend to only include that which you need. If you are just using a List you only include list. If you need to sort then you have to include algorithm.

Darwin, have you ever done COM programming (C++ not VB)? If so have you used MFC in your COM programming?

oktronic,

your posts clearly reveal a series of fundamental misconceptions about how memory is organized and accessed. While it is true that dynamic memory is allocated in blocks which are maintained by the system in linked lists, this occurs on a completely different level of granularity than the single elements of an array or other type of container that one might implement. In other words, 1000 bytes allocated with a single new or malloc are of course guaranteed to be in contiguos memory, that is, the single bytes have consecutive addresses, which has important consequences for any algorithm operating on them, namely the possibility to immediately access any single element in constant time by just calculating its address from an offset. OTOH, the memory address of an element of a linked list does not allow you to make any assumption about the addresses of other elements, as the elements are generally allocated with separate calls to the memory manager, so to find an element, you have to walk the list element by element, which takes linear time: The more elements you have, the more time it takes to find a specific one.

The slide shows you are referring to with the two links, OTOH, are about virtual memory and the mapping of logical addresses to physical addresses. However, this is mainly a hardware issue, done by the MMU, and completely transparent to software, so it can be ignored in this discussion. To the software, a (logically) contigous block of memory is accessible as a single block, even if the block actually spreads over different blocks of physical memory, as the mapping is done by the hardware. Software will see the block as one single block, to every effect, even considering performance.

So we are actually dealing with three different levels of abstraction: The hardware mapping of virtual memory to physical memory (which we can safely ignore in this discussion, as we have seen), the way the memory manager maintains separate allocation units as chunks in a linked list (which is also completely meaningless for this discussion), and the way our algortihms and data structures organize and access the memory they allocate (which is what this discussion is all about).

Quote:

---

Originally posted by oktronic
if you read the documentation, you would see that the call
ptr + 50
is actually a reference to an address, then the system has to iterate through memory to the page frame that contains element 50.

if you were to simply dereference a pointer to that address like so

*tempptr;

then all the system has to do is go to that address....you do the work for the system instead of the other way around.

---

Yes, this clearly shows your misconception. Adding a value to a pointer is simply an arithmetic operation, no iteration through memory is involved here. Dereferencing that pointer will just access the contents of memory at that address, always in constant time. The fact that this might require the MMU to translate that logical address to a physical one is, again, completely meaningless, as it occurs on a very low level and still in constant time.

Quote:

---

Originally posted by oktronic
So while I'm busy misunderstanding, can you explain to me why using my own list is more inefficient then iterating through system memory list to the 50th element?

---

Simple: Because using your linked list, this will involve 50 pointer operations: Each time, an offset is added to a pointer (to access the member containing the next-pointer) and dereferencing the result (to get a pointer to the next element). Note that each dereferencing operation will also invoke the MMU for an address translation. The cost for this operation grows proportionally with the number of elelments in the list. OTOH, when using an array, accessing the 50th element is just a matter of a multiplying 50 by the size of an element and adding the result to the array's base address (a simple arithmetic operation, no memory operation involved here!). Then you dereference the resulting address (which will, again, invoke the MMU, but only once), and access the element. Note that this remains exactly the same if your array has 1.000.000 elements instead of 50.

And this brings us to the key point when comparing different data structures (here: containers) against each other: The distinguishing feature of a certain type of container is not its actual implementation (although it practically boils down to that, in the end), but rather the complexity guarantees it makes with respect to certain operations. For example, the data structure commonly known as array or vector (and implemented by std::vector or CArray) guarantees O(1) complexity for accessing arbitrary elements. That's the outstanding quality of arrays, and that's why we use them when we need to access elements in constant time. Note that no guarantees are made for other operations such as insertion and removal of elements: They may be O(log(N)), O(N), even O(N*N) - that's up to the implementation.
Somewhat at the other end of the spectrum, we find the linked list. We know that the cost of finding a specific element is generally O(N), but have the guarantee that adding or removing a known element is done in constant time, O(1). So a list (as implemented by std::list or CList) is the container we choose when adding or removing elements should be always fast, regardless of the size of the list, but we don't need random access to the elements. Likewise, every other type of container (binary tree, queue, stack, hash table...) makes different guarantees about the complexity of different operations, especially when it comes to sorting or accessing elements in a certain order.

Now looking back at what you state about your 'MyTemplateList' implementation:

Quote:

---

Originally posted by oktronic
My class can handle dynamic or static memory, contiguous or linked. More specifically, you can hand it any type of memory and it will use it until your size limit is hit, and then it will go dynamic, or fail depending on options. If you refer to the vector code, you'll see that's all it is, a dbl-linked list container. It has some extra functionally, but still, inside that's all it is. Unless you are only defining a linked-list as only a dynamic list?

---

It seems as if your container wants to be some kind of general allround container, using dynamic or static memory, contiguous or linked as needed, just to fit any needs. This makes it neither a real array nor a real linked list, as it makes no guarantee whatsoever about the complexity of well-defined operations.
So it seems you really missed the most important point about why there are different types of containers, and it explains why you deliberately tried to compare the performace of a linked list with that of an array.
I think you should strongly consider reading about the subject (Donald Knuth's "The Art of Computer Programming", especially Vol. 1, "Fundamental Algorithms" and Vol. 3, "Sorting and Searching" are a good starting point. First published in 1963, they are still highly relevant). Furthermore, regarding sources like the two you pointed out, you should understand that they refer to memory management issues on a completely different level of abstraction than what we are discussing when talking about containers.

Quote:

---

Originally posted by KevinHall

Code:

---

void list_test()
{
    std::list<int> li;
    int i;

    for (i=0; i<1000000; ++i)
    {
        li.push_back(i);
    }
}

void vector_test()
{
    std::vector<int> vi;
    int i;

    vi.reserve(1000000);
    for (i=0; i<1000000; ++i)
    {
        vi.push_back(i);
    }
}

---

I ran this code (release build with MSVC 6.0) and profiled it 30 times (with us resolution). Here are the results:

list_test(): 905.5 +/- 3.7 ms
vector_test(): 89.1 +/- 1.1 ms.

---

Quote:

---

Originally posted by KevinHall
Ok, so I've tested what I think oktronic's class looks like (again 30 tests with MSVC 6.0 release build). Here are the results (and to be fair to oktronic, I don't have the sources to his class):

list_test(): 908.1 +/- 1.9 ms
MyTemplateList_test(): 898.9 +/- 7.0 ms
vector_test(): 91.9 +/- 1.4 ms

---

Actually, I overlooked something in my tests. vector_test() and list_test() actually deallocates the entire list at the end of the function. MyTemplateList_test() did not. Taking that into account, I'm quite sure that the STL outperforms the MyTemplateList that I tested with (see previous post for code).

- Kevin

Quote:

---

Because using your linked list, this will involve 50 pointer operations: Each time, an offset is added to a pointer (to access the member containing the next-pointer) and dereferencing the result (to get a pointer to the

---

I wasn't comparing it to a linked list.
I was comparing ptr + 50 to *tempptr.

Quote:

---

Adding a value to a pointer is simply an arithmetic operation, no iteration through memory is involved here.

---

Exactly, I was hoping Kevin picked that up, that's why I set that up for him since he didn't seem to understand. That's one of the differences between array iteration and ptr. Its 1 operation to get array address, one addition to new address, 1 operation to get value from address.
However for a simple de-reference, its 1 to get address, 1 to get value. Which is one less operation, so its faster. Which is the point for pre-allocated memory.

you see if you have block of memory for data segment, even for a linked list, if I take first pointer, just like vector does, and I do the same thing to my reserved segment, and set the offset, then it will be just as fast as vector, even though its a linked list.
Twice now I have asked you to simply modify the code Kevin provided and pre-allocate memory for it. So please do so and you will see the results for yourself making this argument moot.

Quote:

---

your posts clearly reveal a series of fundamental misconceptions

---

Actually, Since you seem to have a interesting understanding of the concepts, you should read the second document provided. Its more advanced then the first, but I think you should be able to understand how a page system works. You made several incorrect points about the system, but I think you're able to understand them so I would suggest picking up an advanced operating design book next time you're out.

Quote:

---

I think you should strongly consider reading about the subject (Donald Knuth's "The Art of Computer Programming", especially Vol. 1, "Fundamental Algorithms" and Vol. 3, "Sorting and Searching" are a good starting point.

---

Read them all, got them in my library. Meet Knuth here at Stanford. I should mention I live in the Bay Area and have done some work there.
What kind of bothers me a little, is you quote his book and yet I don't think you know what's in them. So I will suggest the same thing to you, read them and then quote them. But please don't just quote any random books to try to make a point. If you have specific points you feel these books illustrate, then quote the points at least then I might get to see that you understand the point you are making.

While you are about 60% right in your post, there's a lot of holes and I could go on about this for months, operating system design can be a lot of fun and a lot of irritation, but in the interest of this thread, please just add pre-allocated memory to Kevin's class and run your benchmark. If you have any problems with that let me know and I'll explain.
But please, less telling everybody that they are wrong and more time proving your points. I have handed you the ability to prove me wrong, use it.

STL is really nifty tool to make a programmer life easier .. but STL code is hard to maintain and debug.
For example

class AFX_EXT_CLASS CBulletInfoEntry : public CObject
{
DECLARE_SERIAL(CBulletInfoEntry)

public:
int nKey; // the Key: (nRow<< 4 | nCol)
RGBCOLOR nColor;
int nRow;
int nCol;
};

typedef std::set<CBulletInfoEntry> BULLETMAP;

BULLETMAP::iterator it = m_Map.find(Key(iRowl, iCol));
ASSERT(it != m_Map.end()); // the entry should exist

// At this point i want to view the values of 'it' which is basically a item of BULLETMAP and namely CBulletInfoEntry. But I cannot do this in the debug or watch window. This is one debugging difficulty we face when using STL.
i.e it->nCol ?
it->nRow ?

Also I cannot do this in debug window it,10 ( to see all the 10 items)

STL is very good at getting the job done quickly. But if there needs to be modification to existing design or if there is a bug then STL is more harder to debug and maintain vs MFC.

Quote:

---

Originally posted by voidspace
STL is really nifty tool to make a programmer life easier .. but STL code is hard to maintain and debug.

---

That only depends on how you use it.

Quote:

---

Originally posted by voidspace
typedef std::set<CBulletInfoEntry> BULLETMAP;

BULLETMAP::iterator it = m_Map.find(Key(iRowl, iCol));
ASSERT(it != m_Map.end()); // the entry should exist

// At this point i want to view the values of 'it' which is basically a item of BULLETMAP and namely CBulletInfoEntry. But I cannot do this in the debug or watch window. This is one debugging difficulty we face when using STL.
i.e it->nCol ?
it->nRow ?

---

First off I would like to point out that the correct reference would be it->second.nCol or it->second.nRow. That is just a matter of understanding how the STL stores the information in a map. Second the only reason the other stuff is so nice in the debugger is because MS has that information configured that way in the autoexp.dat. I have actually added my own aditions so my maps, vectors and lists do similar things. For instance, adding the following line to your autoexp.dat will make the STL string template display correctly:

std::string<*> =<_Ptr, st>

Now it will display the same as a CString would.

Quote:

---

Originally posted by voidspace
Also I cannot do this in debug window it,10 ( to see all the 10 items)

---

Actually this can also be done in the debug window depending on what you are using, it is just a bit more in-depth because you actually have to break it out and remember that it is a pointer and in a map the items are not stored contiguously.

Quote:

---

Originally posted by voidspace
but STL code is hard to maintain and debug.

...

At this point i want to view the values of 'it' which is basically a item of BULLETMAP and namely CBulletInfoEntry. But I cannot do this in the debug or watch window. This is one debugging difficulty we face when using STL.

Also I cannot do this in debug window it,10 ( to see all the 10 items)

---

Yes, yes, yes. But this is more the fault of the debugger for not allowing such information to be seen easily. Have you ever noticed how MSVS allows you to see the contents of a _variant_t type just fine without expansion -- even though the definition of that class is not simple? I dream of the day MS has better watching of STL data!

Quote:

---

Originally posted by Adam Gritt
I have actually added my own aditions so my maps, vectors and lists do similar things. For instance, adding the following line to your autoexp.dat will make the STL string template display correctly:

std::string<*> =<_Ptr, st>

Now it will display the same as a CString would.

---

:eek: :eek: :eek: :) :) :) Please enlighten the rest of us and list the link to appropriate web documentation concerning this. Also, would you mind posting what additions you have made? That will make my life (and others') easier!

Thanks!

Quote:

---

Originally posted by KevinHall
:eek: :eek: :eek: :) :) :) Please enlighten the rest of us and list the link to appropriate web documentation concerning this. Also, would you mind posting what additions you have made? That will make my life (and others') easier!

Thanks!

---

MSDN,
"Visual Studio"
"Displaying Elements of a Custom Data Type"

Quote:

---

Native Code
When you are using interface elements such as the Watch window, the Visual Studio debugger automatically expands common data types to show their most important elements. If you have your own custom data types that you want the debugger to autoexpand, you can add rules to the file autoexp.dat, which is located in the \bin directory. Instructions on how to write autoexp rules are located in the file itself.

Note The structure of this file and the syntax of autoexp rules may change from one release of Visual Studio to the next.

---