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

Well I just broke down and bought a copy of the standard.

What about this part of the standard. I think it is saying that there
are no reallocations in this case:

Quote:

---

The constructor template <class InputIterator> vector(InputIterator
first, InputIterator last) makes only N calls to the copy constructor of T (where N is the
distance between first and last) and no reallocations if iterators first and last are of forward, bidirectional,
or random access categories. It does at most 2N calls to the copy constructor of T and logN
reallocations if they are just input iterators, since it is impossible to determine the distance between
first and last and then do copying.

---

Ordinary array pointers provide random access iterators.

Do I miss understand this?

[EDIT]
Ah, I see, there are no guarantees about the initial allocation.

OK

Quote:

---

Originally posted by souldog
Well I just broke down and bought a copy of the standard.

What about this part of the standard. I think it is saying that there
are no reallocations in this case:


Ordinary array pointers provide random access iterators.

Do I miss understand this?

[EDIT]
Ah, I see, there are no guarantees about the initial allocation.

OK

---

Yeah. The standard makes garantees only about the number of actual elements in the vector (calls to T's constructor) but says nothing about the vector's capacity. When a vector reserves capacity (storage space) the space is simply blank (no T's are constructed). When a new T is needed the placement new operator is called to create a new T in already allocated space. Hense guarentees about how many Ts are constructed do not restrict the space allocated for future Ts.

THIS IS A CALL FOR SOME CLEAR STATEMENTS!!!

I will attempt to make some, but I am no expert. I am just tired
of hand waving. All of the following arte questions:

1. When the standard guarantees that the the contents of
a vector are stored in a single chunk of contiguous memory
this refers to a single chunk of contiguous virtual memory?

2. There is no guarantee made that if the contents of the vector
require more than one page of memory then when and if these
pages are brought into physical memory they will be arranged
contiguously?

3. The intel x86 processors use base-offset memory lookup on
top of the VMM?

4. The contents of a list are stored in several chunks of memory
each chunk containing a single element of the list? There are no
guarantees that these chunks are arranged contigously in VM?

5. In order to maintain contiguous layout in virtual memory, the
entire contents of a vector may be "moved" when elements are
added or removed, even at the end?

6. Since there is no guarantee for contiguous memory for a list,
there is no reallocation needed when elements are added or
removed. It is only neccesary to update the pointers?

7. Having the vector layed out in contiguous memory has
advantages with respect to locality of reference?
In particlar if a TLB is used (and all major modern platforms
use one) then iterating through a vector will not result in
page faults occuring until a page boundary is crossed? If spatial
locality of reference has been taken into account then this next
page may already be cached?

8. The considerations of question 7 are in no way guaranteed
to be applied to a list since spatial locality of reference is not
guaranteeed on an element by element basis?

9. Since the intel x86 processor uses a base offset mechanism
within a given page frame, it is not the case that iterating
through a vector is the same as walking along the pointers
in a linked list?

10. The standard guarantees that random access into a vector
is of O(1) complexity? This would not be possible if in fact the
memory for the vector was implemented as a linked list?

11. If random access is requested for a vector that is not paged
into physical memory, then it must be the case that a base offset
mechanism is being applied to VM to fetch the page? This is
posible since the vector has a guarantee that it is contiguous in
virtual memory? So it is not the case that a linked list of pointers
is walked even in VM?

12. Obviuosly custom allocation schemes will affect performance?
For that matter one could just lock the entire vector or list into
contiguous physical memory and bypass all page faults?


MOST IMPORTANT

13. One could hand roll containers, the language, or even the OS
for that matter. Is this a revelation?

So how about some answers to these questions

Quote:

---

Originally posted by oktronic

Quote:

---

And I have come to believe that much of the opposition is a psychology, a tiredness, a "I don't want to have to learn yet another thing."

---

I have to disagree with this. Many of the people who have held opposition to STL have shown they understand it and have chosen to not use it. I have seen many propose that Darwin (who started this thread) simply doesn't understand STL and that's why he doesn't like it, even though he has shown several times that he does understand it and has rejected it, with several valid points. There is nothing complex about using STL. If you understand templates you can understand it. I feel that Darwin understands templates, and him not liking STL does not mean he just "doesn't get it" as suggested.

Quote:

---

Design issues are mentioned at several points, yet particulars get clouded over by a fog of "ugly" and "difficult". When particulars do come up, they are responded to quickly, and despite the fact that so far the most of the issues have been ones of understanding how to use the standard containers (not deriving but extending orthogonally), what their guarantees are (algorithmic complexity issues), and the language features they use (templates and namespaces), well...

---

"ugly" and "difficult" are two major negative design flaws in any program. These are the "particulars". So I'm not too sure what you mean by "clouded over by a fog" since these are two of the major points in that reference. And again, I believe the main players in this thread understand STL, its purpose and its implementation.

---

Actually, I really don't want to bring darwen into this issue, because from the general quality of his posts, I have no doubts that he will eventually have to confront the standard containers head-on through some reason or another, and I think that after the first few test programs, he will finally have those epiphanies on why their structure is the way they are and not think twice about them. Although I am trying my best to keep focused on a general attitude, understand that darwen probably is not the major focus of my words and I don't feel it is appropriate to make that link. There are others displaying the attitude I am describing which I might focus more on if I were inclined to point fingers...

Actually, "ugly" is not a particular at all, and "difficult" equates to me to "i have yet to learn this" which falls straight inline with my earlier analysis. Which particular is ugly? I saw a code snippet inserted into this thread. It showed many ways to go about similar tasks, with much overlap in goals, to illustrate that there are several pathways one might go about acheiving the goals depending on what information one had handy. It focused on the standard's dictionary (std::map) and the types associated with it's use (iterators, pairs, ...). But I never saw "see this line.... this is ugly because XYZ". Just as I never saw "see this code... this produces bug XYZ".

It is important for code to be easily understandable within a development team so that code ownership and information lockout issues don't bite a team as people come and go. But that is not an argument to produce grade school code, either, and the choice is not between "simple" and "ugly". The choice is between clear code that follows closely the design or convoluted code with no apparent design. And the standard containers and algorithms have a very clear design. Its just that it is using a language feature that allows for a whole new class of type dynamics, one which allows for a completely different dimension of abstraction and connection outside the "contain or derive" hegemony, and it uses the iterator abstraction (i'll leave out the allocator abstraction, because I don't think that that is usually what is referred to by the use of "ugly" or "difficult" since the default usually is enough to get one familiar with the class and allocators only start popping up when particular sources of serialisation are needed).

Concerning the iterator abstraction, its something I've had a long relationship with. I remember one of my first intermediate level books I read was Jeff Alger's c++ for Real Programmers. And although it was written in a confusing time where c++ was in a state of major language flux and the author had obviously not acheived that solid a grasp of many of the newer issues on the horizon, it tackled containers with a passion, and showed alot of nice little type dynamics with the development of smart pointers into iterators, cursors, etc. And it was quite clear how this abstraction improves algorithmics. But template use was stunted at best, and the separation was not as complete as it could be. When I started to learn about the standard containers (which was afterwards, because I too have had to take that strange path from c to c++ over time instead of properly using the language from the start -- to be fair, though, my early c++ use started prior to the 98 ISO standard), it was quite clear to me their intent and usage, and I was quite impressed at their ability to abstract out all of the little pieces.

Now take a look at the MFC containers. I claim they are "ugly". Why? Because they do not provide an interface for algorithmic abstraction. One could build classes to do that, CList has its POSITION structure, and maybe wrap all of the abstraction up with static concept checks and there you go, an iterator abstraction over all of the MFC containers. Except that I also claim that MFC's containers have bad design and give yet more specific answers to a why by pointing to their rooting in the hierarchy, which requires one to bring inside any translation unit which wants to use it the entire CObject baggage. I personally don't use any GUI frameworks outside the presentation layer because they don't provide any tools which I can't find more useful variants elsewhere. But the use of a library component should not require the insertion of other library components. That is coupling. That is a poorer metric of reuse. That is bad design.

You have to see that that is my point. Where are the specifics in the other direction? Where is the library that has better designed containers, with specific points illustrating the metrics used. Because what I am saying is:

Listen. As a programmer, you will need to get a lot of things done, and the faster and more robustly you can get them done, the more valuable you are. So one of the things that can get you there is picking the right toolkit of libraries. The standard library currently has the best containers available according to my metrics, and might be a good place to start. If other libraries can provide better containers, show me the metrics used and the specific points where they are applied. Don't avoid the standard containers until then, though.

Quote:

---

Also posted by oktronic
One of the points proposed in this thread has been that simply, anything that STL can do, you can write yourself. Meaning that STL is just code. It is not built into the construct of the compiler, so there is nothing that it can do, that anything else can't do. So STL doesn't have a edge over anything else, since with a little effort, anything else can do the exact same thing. And since STL runs exception handling (in .NET, not VC6), which has a overhead, if you reproduce the STL code yourself, and omit the exception handling, you already have a performance boost over it. You can then systematically remove unnecessary code or optimize the code, you then have another performance boost over it. I know the first thing said will be that STL exception handling is the best way to handle errors, as its been already proposed. Unfortunately, its an overhead and doesn't provide efficient enough handling of errors. Even MS's GetLastError() is more efficient by simply returning a code to deal with the error with out the overhead. A simple "Only do work when there's a problem" approach that MS API has keeps code running fast when there isn't a problem. I personally think that if there is no error, then I don't want anything to take a hit.
Besides that however, the design flaws (which I'll agree are much better in .NET now that they have dropped the R&D code), such as hard to read and difficult to integrate into a complex environment, make STLs "edge" minimal.
As for the amount of "man-hours" saved, they are only saved if there isn't a problem and only lost if you don't already have your own libraries to use. If you have to debug STL, which in a production environment is done by "debuggers", which usually consist of fresh college grads who start there to gain experience, then the "man hours" are lost to inexperience in the cycle. Which is a negative to STL in production.

---

Anything that your computer can do can be done with pen, a paper, a competent mathematician, and enough labor-hours. The problem comes with the fact that there is more room for error and time was unnecessarily wasted when a tool already existed that could accomplish the same task.

Sure one can rewrite the standard containers. The problem comes with the fact that there is more room for error and time was unnecessarily wasted when a tool already existed that could accomplish the same task.

I am quite amazed at the fact that although I have repeatedly stressed the fact that no bugs in the standard containers have yet been introduced into this discussion, debugability continues to be used as an excuse to add more risk to a project, increase the likelihood of bugs, and waste labor-hours that translates directly to cold, hard cash.

And now we get added this idea that exceptions generate slower code, whereas the correct statement would be that the concept of exceptions does not require any machine instruction to be executed along the normal execution path. Only during a throw does stack unwinding need to add any code, and many compilers do things exactly this way. There have been a few compilers in the past, particularly early on after exceptions were introduced, that added overhead to function calls to set up a more organised stack frame or make calls to OS services to help out, but much of that is old news as more flexible stack unwinding algorithms were developed. And even though that more qualified statement could have been stated, it still would be a moot point since the interfaces provide very few functions that actually throw anything other than a bad_alloc which is a possibility during any dynamic allocation in your program that isn't placement or std::nothrow qualified. I suggest turning off exceptions and building a program that tests every allocation for NULL return errors and see what runs faster. Error return testing is often much slower than exceptions on most compilers these days precisely because the error test necessarily introduces code where the exception path need not except in those exceptional circumstances.

Quote:

---

Also posted by oktronic

Quote:

---

the discussion about system level memory being done in terms of list linking was pure smokescreen (another of the symptoms I mentioned earlier)

---

Quote:

---

It is all done through the descriptor tables the processor already is being pointed to internally, they are page lists (so we are looking at access only in increments of the page size), they are quickly indexable, and the transformation occurs for all virtual addresses mentioned in a machine instruction.

---

It does bother me a little that you call the claim that the system is a linked list configuration a smoke screen, then use the term page lists to describe it. So lets take a look at the structure that the system uses. Forgive any missing variables, but I'm running off my own memory since I don't have any documentation with me and its been a while since I've had to deal with it. MSDN has some articles on VM and how the system handles it.

I will provide this link which I hope will help illustrate, just remembered this is out here, I'm sure there are better:
http://www.windowsitlibrary.com/Content/356/04/1.html
This talks about how memory works in NT systems, the theory has evolved since NT in 2000 and XP, however, the principle is more or less the same.

Here is a very basic structure.

struct memoryPage{
void* data;
UINT size;
memoryPage* next;
};

Since the "next" points to the next page, this is a linked-list obviously. This is why windows has a linked-list implemented MMU or memory management unit. This is what I was talking about. I understand I confused several people with what I said, but I rush a little too much when I write and that's why I provided some links to help illustrate the point to clarify. But as you mentioned, people start getting defensive, and as a result information gets twisted.

What this boiled down to as a point is, that the way the system handles your memory does not mean that "contiguous" is any faster then a user-managed linked list. It depends on the page size and the efficiency of the code to manage it, which again is demonstrated in my original articles. This is why I ask you to try both. Create a pool of memory and manage it yourself and then try the system an benchmark the results. Granted I still need to do the work I promised and post it, but Thanksgiving is in the way, but when I've got access to my comp, I will do as promised.

Quote:

---

it only occurs prior to transformation if an access is required. There is nothing at all about the process of address transformation that suddenly makes the vector guarantees the same as a linked list, or anything freaky like that.

---

Again, I think we are talking about different things. The system attempts to store data in physical memory in such a way that the memory can be easily swapped between disk and physical, yes. Data is stored in several complex tables which do several things, two of which would be to protect system and application integrity, and provide efficient retrieval. However, you can't have super fast retrieval and safety. Safety will have overhead as there are system memory tables and application memory tables to ensure that you can't interfere or crash anything but your own program. The system must traverse these tables anytime you wish to reference your memory. So if you do the work of the system in your own program, then you could remove the hit the system would normally generate. Since you have programmed drivers, you can see how this is very possible.

So to sum up, a question of system performance came in to play and an explanation of how the system worked was necessary to quell the belief that you are guaranteed that any memory you get is in any way "contiguous". I hope this clarifies that point.

---

And I am not trying to flame you either.

But.

This is exactly the misunderstanding about the iterator abstraction and guarantees that I keep referring to when I suggest that the attacks are coming from people who do not understand the standard containers. I tried to make it clear in my first post, but let me amplify a little...

The same mistake was made with the entire misunderstanding between vectors and lists in this thread that prompted this entire diversion. You see, contiguous addressable memory refers to the fact that locations in the container can be referred to with pointer arithmetic without traversal. This allows the container to expose an iterator of the random access variety. This allows for the iterator to use this feature to optimise the mathematical order of complexity of a move operation by jumping around freely in the container. A list iterator, however, is only of the variety of a bidirectional iterator. It can move only in single steps, since the operation of a move is a dereference of a node pointer. Moving a particular distance requires the number of steps to be of the order of the size of the move. Each of these operations occurs at the level of algorithmic complexity of the actual addressable space. Pointer addition instructions are performed by the processor without regard to dereference. On 32bit x86, we are talking only a simple DWORD + DWORD instruction. It is the dereference that is a list lookup (like a simple pointer move to register), but the order of that lookup is not dependent upon any algorithmic environment variables. A full detailing of the algorithmic complexity would detail that only as part of the orders of operations not part of the algorithm's variability space, and gets lopped off as some constant order of magnitude. An iterator into a vector of 30 elements will have no problem jumping from its first element to its 29th element with one addition and one dereference operation. A list would need 28 dereference operations just to move to the 29th node (and probably a node offset addition and furthur dereference to expose the data). And that is the data complexity information will be calculated on, since all that is assumed by a dereference operation is that it takes some amount of time, which everyone agrees with. And noting the system's actual implementation of dereference does not change the fact that the vector has a random access iterator which alters its complexity guarantees from that of a list.

In other words, no matter what occurs during the dereference operation, the vector has the advantage in the move. And that is all that was being discussed. I know that when one feels they are being attacked, it is quite natural to jump back with proof that they really are special, even if it means changing the topic to something they know a bit better, but that is all that it was (topic changing). That is why I called it a smokescreen. It did not address the current topic of discussion.

And just to reiterate what that topic was: it was your misunderstanding, oktronic, of the algorithmic discussion between vectors and lists in the hand roll example. The example was to illustrate that intelligent people could hand-roll their own vector in no time at all with more flexibility, less bugs, etc. What I think that discussion has shown, however, is that intelligent people can mistake the concepts embodied by the standard containers, attempt to hand-roll one type and mistakenly produce a different one with different complexity guarantees, without the abstractions built in, and that this example pretty much underlines the point I and others have been making all along.

I didn't see your response, souldog, as I was busily typing mine, but I hope some of the issues have been answered. The main point which applies to your questions is that the system's way of mapping virtual addresses to physical addresses does not add any complexity issues directly involved with the distinction between vectors and lists. The only thing that is affected is the order of complexity of dereference, which does not vary according to any of the dimensions of the algorithms. It is a system environment dependent order of complexity, which can be abstracted out into the basic notion of a "dereference operation" when such is not under direct control. A vector iterator move still has far fewer dereference ops than a list iterator move, insertion still requires only two memory locations being changed (dereference-assigned) on a list, whereas a vector still requires all elements subsequent to the insert to be changed and possibly those prior when a new buffer must be allocated, etc. In other words, all of the generic algorithmics and complexity guarantees are not altered. Which is what explains the real, cold, hard timing calculations that demonstrate this.

However, I doubt that you needed to hear any of this from me, so I'll let the other side explain the point they are trying to make.

Hi galathaea,

I'd like to say first, that I really don't feel that this is going anywhere. I generally don't like to read a 2 page post to weed out a few points. In my opinion, the major problem in this thread is that there are lots of statements and yet not a lot of backup. Everything that I have stated can simply be proved or disproved by opening your compiler and writing a few lines of code to see whether what I have said holds true. That is why I have asked repeatedly for anybody who doesn't believe anything I've said to just try it. Stating that I am wrong with nothing to back it up but 2 pages of opinion, I feel, just wastes time.

But nonetheless,

Quote:

---

Actually, I really don't want to bring Darwen into this issue, because from the general quality of his posts, I have no doubts that he will eventually have to confront the standard containers head-on through some reason or another, and I think that after the first few test programs, he will finally have those epiphanies on why their structure is the way they are and not think twice about them

---

This is what I was talking about in my last post. You are assuming that Darwin just doesn't understand STL. "He will eventually have to confront the standard containers". He has, and he has said no. "after the first few test programs" is the exact kind of statement that causes this to go on and on.
He said, "I actually know both the STL and MFC very, very well having used both for a large number of years and prefer MFC.
" at his 5th post and he has constructively dissected STL through out this thread and made many valid points. Are you calling him a liar? He gets the same "you are wrong" response repeatedly through out the thread. And example would be Paul's response of "Looks like your trolling. ".
Or perhaps comments like this, "If you're going to talk about something, at least know the topic well enough to comment.".
Or this, "No I don't see what you mean, you don't understand the CRT at all, so your lack of understand leads you to this"
This is just a handful of comments the first dozen posts to Darwen.
Darwen on the other hand, asks lots of questions in his posts, and the usual answer is, "you just don't understand", or comments as you have responded above.
This is not the makings of an intelligent debate.
In my opinion, when a response is one of a simple, "you are too stupid to understand", then the person who said it probably doesn't understand himself. No matter how complex he writes his reasoning.
This is why the STL crowd hasn't proven or settled their argument. The only person who has actually done anything to support any thesis was Yves by writing some code and actually testing it. Granted his library was giving him some grief, but he actually attempted to prove his thesis with code. That is debate. When you say to someone, "try this and you will see for yourself", you are persuading someone, when you state, "you are wrong because you don't understand", then you prove nothing and show a lack of understanding yourself.
So Darwin is key in this debate. To say he "just doesn't understand" is to show that the lack of understanding is on your part, not his, in my opinion.

Quote:

---

Actually, "ugly" is not a particular at all, and "difficult" equates to me to "i have yet to learn this"

---

Various bits of STL have been posted and if you feel that someone's dislike of one letter variables means that they "have yet to learn this", then I think you have yet to learn about good design.
No programmer worth anything would ever say that one line functions, and uninitialized variables, and one letter names are pretty coding. Any well written program should read as easy for another programmer as English. If another programmer has to walk around your code trying to figure out what is what, then you have written your code poorly and in most production environments you would be warned then fired for such poor produce.

Quote:

---

The same mistake was made with the entire misunderstanding between vectors and lists in this thread that prompted this entire diversion

---

Something that I said at page 8 hardly qualifies as the reason for the STL division. I don't think you realize how long this thread is and when I got involved.

Quote:

---

You see, contiguous addressable memory refers to the fact that locations in the container can be referred to with pointer arithmetic without traversal

---

Of coarse, that is the definition. But the one problem with your statement is relativity. While it may indeed appear to be "contiguous" to your program, it may not be to the system. Which again is why I have provided several links to help explain that. Which bothers me that you feel that I don't understand what the difference between a linked list and an array is. But the misunderstanding is on your part, because I'm talking about how the system is handling your "contiguous" memory and you are talking about C containers. Which is another misconception in this debate. There are no rules when it comes to containers. Nothing says that a linked list has to allocate memory at each insertion. You can do the work wherever you choose. You can allocate yourself, or let the system do it for you. The same goes for vector. However, you should understand what the system is doing before you choose to use a method. So I would recommend you read the documentation in my last post so you can understand a little better what I am talking about.

Quote:

---

suggest turning off exceptions and building a program that tests every allocation for NULL return errors and see what runs faster.

---

I will indeed do this, when you have time, could you please show some code and statistics for what you believe is faster and slower so I and others can see what you have seen that makes you believe this?

Quote:

---

I know that when one feels they are being attacked, it is quite natural to jump back with proof that they really are special, even if it means changing the topic to something they know a bit better, but that is all that it was (topic changing).

---

Talking about STL's performance is very much on topic. Talking about how the system functions in relation to difference access methods which relate to STL is right on topic. To suggest to write code and test its performance, is not only on topic but a good debate method. So I don't see why you feel a topic change was occurring.

Quote:

---

In other words, no matter what occurs during the dereference operation, the vector has the advantage in the move

---

unless of coarse the list simply has to dereference a pointer to its element with out any calculation...or if the list managed its memory in succession in which case it could perform the same move as the vector...in which case it would be just as fast...I guess it all has to do with how the class was written. Which would go back to the design issue, can another programmer make more efficient class then the STL programmers, or are the STL programmer’s programming unsurpassable?

Quote:

---

What I think that discussion has shown, however, is that intelligent people can mistake the concepts embodied by the standard containers, attempt to hand-roll one type and mistakenly produce a different one with different complexity guarantees, without the abstractions built in, and that this example pretty much underlines the point I and others have been making all along.

---

I feel the argument has shown that there are too many "die hard" STL users who believe that STL is a "holy-grail" and when confronted with this, its stated that all who oppose it, just doesn't understand it. Many of us old-timers have been writing container classes long before STL and those who have written them understand how they work, how they perform and how they are adaptable, they understand this because they themselves had to do the work, something I feel that those advocating STL haven't done. STL was designed to be a quick and dirty container solution for programmers who needed it, just like Visual Basic was designed to make quick and dirty windows programs. So because of this, I feel the points are moot.

Quote:

---

Originally posted by oktronic
STL was designed to be a quick and dirty container solution for programmers who needed it, just like Visual Basic was designed to make quick and dirty windows programs.

---

I'd like to know where the designers of the STL and/or the C++ standards comittee say this! Anyone got a reference? :rolleyes:

And to think, all this time, I've just been a lazy programmer....

I think you are all missing the one key advantage STL has over any home grown solution yet it has been conclusively demonstrated here in this thread. FAMILARITY.

Both protractors and detractors here in the STL debate and have fiercly argued that they 'understand' STL. Both from a philosophical and design perspective as well as a semantic one. No home grown library can claim this. Not even MFC which is only applicable to the windows platform. This means that if you use STL within an application you can reasonabily expect that future developers will understand and be able to maintiain your code. Whether they like STL or not is of no consequence. The odds are that even if they disdain it they will understand it. You don't need to document its API or its semantics as you would for your own library. You don't need to teach it to your developers (assuming a professional staff). Full comprehension simply becomes a presumption.

If you create you own containers you invalidate the assumption. You must now create all of these artifacts. And even then, you'll almost never reach great enough developer penatration for the library to out-live your (or your company's) mantainence of it. If you do reach this critical level of penatration, then inevidabily your library will be adopted as a standard and be incorporated into STL.

All of that being said. STL represents the best algorithms and containers possible for the general case. The general case is not all cases. Like Kuth's seminal work on allocation strategies, there is often no apparent globally optimal approach. If you know somthing about your problem domain that is not invarent for the general case then you can possibly build a more efficent algorithm or container - but at the expense of significantly greater overhead in maintainence. But recognize that your library is applicable to a smaller problem domain than the STL general case and so therefor direct comparison may be invalid.

Creating your own library for structural or style issues with STL is understandable but structure and style are like religions. Debate is mear retioric because the issues defy quantification. But monentum is everything. Developers will be familar with and acustomed to the STL structure and style not because it is the 'best' but because it is the most common. Fighting a language standard is like trying to swim an ocean. To quote Moby "I don't want to swim the ocean. I don't want to fight the tide. I don't want to swim forever..."

McClark,
I don't think that point was missed by everyone. It is what I meant
by the one word response "standardization" and Galathaea and Paul have essentially said as much.
However, your statement of that sentiment is certainly the clearest.
Rest assured it will be ignored. (not by me)

When I stated that oktronic was talking BS, what I was referring
to was the statement that any company would absolutely not
want STL used on any programs it contracted. BS. Probably the
only person who benefits in a situation where oktronic uses his
library in a contract is oktronic. Why would a company want to
forever tie the product to the original programmer?

Quote:

---

oktronic
Various bits of STL have been posted and if you feel that someone's dislike of one letter variables means that they "have yet to learn this", then I think you have yet to learn about good design.
No programmer worth anything would ever say that one line functions, and uninitialized variables, and one letter names are pretty coding. Any well written program should read as easy for another programmer as English. If another programmer has to walk around your code trying to figure out what is what, then you have written your code poorly and in most production environments you would be warned then fired for such poor produce.

---

You must be aware that this is NOT STL. this is an implementation
of STL. Yes it looks to be badly written in terms of readability.
What does that have to do with STL? It is not a surprise that
microsoft would chose such an arcane implementation.


Hey mick, I think I am winning:)

Excellent points mclark.
STL hasn't been around long. A drop in the bucket compared to the theories and applications of the containers it employs.
Which begs the questions, why would a programmer who has been programming containers decades before STL was conceived, want to use it? Generic programming isn't new and the algorithms STL use aren't new either. Which wouldn't that really leave STL to be used by those who don't have their own generic classes, like new programmers to the field?

For Kevin, here is an interview with Stepanov, the creator of STL.
http://www.stlport.org/resources/StepanovUSA.html
Just took a quick search to find out the information. Hope it helps you. I think you will find it useful to do a few more searches to get a complete picture. Note his views on object orientation. His ideas for generic programming aren't particularly new and much of what he proposed has been proposed by many others. Stroustrup's role in its development is interesting as well.

Quote:

---

You must be aware that this is NOT STL. this is an implementation
of STL. Yes it looks to be badly written in terms of readability.
What does that have to do with STL? It is not a surprise that
microsoft would chose such an arcane implementation.


Hey mick, I think I am winning

---

when you design a program do you not think of its implementation?
A what does microsoft have to do with STL? They were the first to offer it before it became a standard and the code provided was from HP, its not their fault that its unreadable. Not that I'm a microsoft fan or do I enjoy defending them, but this is a case where they tried to do the right thing and provide the latest technology to help stay on top.
And what do you feel you are winning?

Quote:

---

Originally posted by oktronic
For Kevin, here is an interview with Stepanov, the creator of STL.
http://www.stlport.org/resources/StepanovUSA.html
Just took a quick search to find out the information. Hope it helps you. I think you will find it useful to do a few more searches to get a complete picture. Note his views on object orientation. His ideas for generic programming aren't particularly new and much of what he proposed has been proposed by many others. Stroustrup's role in its development is interesting as well.

---

I think this article only bolsters the point that the STL is not just "containers for dummies".... Here's what Stepanov had to say in that interview:

Quote:

---

ANSWER:
STL, at least for me, represents the only way programming is possible.

---

Now I have read the interview (quickly albeit, but I did read it).... Where is there a statement similar to yours in that interview?

Quote:

---

Originally posted by oktronic
STL was designed to be a quick and dirty container solution for programmers who needed it,

---

Please quote (not just a reference some paper I have to search through) and (not or) where that quote that can be found where someone who helped design the STL and/or was on the standardization comittee actually says something similar to the STL being a "quick and dirty container solution"!

the point being that it is not valid to point at the implementation
of STL used by microsoft and make any statements about STL
in general. If I were to take your library of containers and systematically replace all variables with single letter names,
use stupid macros throughout it and release it to people, would
this reflect anything on your original design?

You keep complaining about the the code in the dinkumware implementation, but this has nothing to do with STL.

My comments about Microsoft are probably unfair, but from
what I have read and seen they seem to be the antithesis
of standardization, that is if the standard was produced
elsewhere.


The winning statement is a private joke, ignore it.

Quote:

---

Originally posted by oktronic
when you design a program do you not think of its implementation?

---

You are missing the point. Does the following code mean that C++ is a bad language?

Code:

---

#include <iostream>

std::ostream llllll(std::cout.rdbuf());

template <typename lllll1, typename llll1l>
void llll11(lllll1 & lll1ll, llll1l const& lll1l1)
{
  lll1ll << lll1l1;
}

char lll11l [] = "\n!dfloUHraWeKoqS(lP$ )bzJ%l";

template <int lll111>
void ll1lll()
{
  llll11(llllll, lll11l[lll111]);
  ll1lll<!(lll111 % 2) ? (lll111 / 2) : ((3 * lll111 + 1) / 2)>();
}

template <>
void ll1lll<1>()
{
  llll11(llllll, lll11l[1]);
  llll11(llllll, lll11l[0]);
}

int main()
{
  ll1lll<7>();
}

---

That code is Galathaea's (hope you don't mind) from this post... (http://www.codeguru.com/forum/showth...603#post754603)

Someone can write:

Code:

---

typedef std::list<int> li;

---

or

Code:

---

typedef std::list<int> int_list;

---

One provides more information than the other. Just because one person is not clear does not mean the interface is bad. The same sort of thing could be done with any class you wrote. (If not, I'd really like to see how you make a compiler enforce some naming standards -- no, I'm not being sarcastic here -- really!!! If you have some way of enforcing clear naming standards, please share it. It would be really nice to use!)

He also said this:

Quote:

---

I find OOP technically unsound

---

It wasn't my intent to form an opinion for you, you didn't seem to know the history to STL so I pointed you in a direction.

And considering your statement was:

Quote:

---

I'd like to know where the designers of the STL and/or the C++ standards comittee say this! Anyone got a reference?

---

I think that answered it. Did you really think Stepanov would refer to 15 years of work as "quick and dirty"? lol
I know you are looking for anything to help you argue your opinion, but perhaps you should spend a little time looking into the mind of the creator of STL and into those who came long before him. Even Stroustrup wasn't eager to support STL and made Stepanov modify it before he would offer it up as a standard, maybe you should look at why?. A little research can go along way.

Quote:

---

Originally posted by oktronic
when you design a program do you not think of its implementation?
A what does microsoft have to do with STL? They were the first to offer it before it became a standard and the code provided was from HP, its not their fault that its unreadable. Not that I'm a microsoft fan or do I enjoy defending them, but this is a case where they tried to do the right thing and provide the latest technology to help stay on top.
And what do you feel you are winning?

---

I studied under Musser and did a lot of banging around with the HP implementation. It was a mess. That couldn't be helped. You really do need a lot of the language support added to the C++ spec to make an STL-like library usable. To classic examples are constructor semantics to built-in types [ie T(x) -> int(x)] and the 'explicit' keyword to implicit conversion logic from going haywire. But this is all ancient history (or it should be). If Microsoft really hasn't moved far beyond the old HP code - well then that should tell you something about them.

But the point is well taken. I've never come across a 'readable' STL implementation with STLPort being the closest. But this is nothing new, since what goes on behind the scenes of <vector> is all implementation-specific. The same 'readability' ***** is valid for malloc or any C library item. Its just normally you can't see what's going on there because you're only provided with a prototyping header and the standard lib functions in an obj. With STL, the vendors can't get away with that. The actual template code has to be there in source form. So really when you look at an STL implementation you're just glimpsing the 'uglyness' that permeates the whole standard library (C and C++ alike).

This really shouldn't be an issue since just like the C library - you shouldn't need to know what's going on in there - just the API. And if your code does depend on what's going on in there - then it is not ANSI comforming and will be very brittle. And there are plenty of 1 character parameter names in the C library. I have source licenses to several major OSes and a few compiler-vendor standard C libraries. And if you can believe it - I've actually climbed through a lot of this code. The uglyness of most STL implementations is par for the course for this type code. From the vendor perspective - your not supposed to read it, your not supposed to want to read it, and by God were not gonna help you read it. Just buy it and use it and pay us to support it if you actually have a problem.

you guys are posting a little to fast for me,

Kevin there is a difference between bad design and bad "language" as you put it.
If you are writing a program for just yourself, then you don't have to really care what it looks like, but when you are writing a program for a client then design is everything. It doesn't matter if its an entire program or just a SDK, your library wont be used it its difficult to understand or read. This is exactly what happened to STL. It surfaced in the early 90's to most of us "in the loop" programmers and mid 90's for the general public. It took several years for anybody to even pick a book up on it. Most programmers can read code better then english. So the usual first response when something new drops in their lap is to read the code, in STL this is the most common case since the code is practically all there. Second is to buy a book, most don't get this far, if they can't easily figure out what the code is doing, they can't trust it in their code so they drop it. If colleges didn't start to teach it as an example to templates, STL probably never would have been picked up.

mclark, the asm for the c library is readable. The actual code has plenty of comments too.
And yes, there were a lot of 1 letter variable names in the old days. It was due to having to deal with old style word processors and compilers, dealing with a long variable name took time, especially since you didn't have all the SDKs there are now and you had to write stuff yourself. A lot of the old coders stuck with it when they learnt new languages even with newer WPs coming out, but it is getting phased out.

edit:

Quote:

---

If you have some way of enforcing clear naming standards, please share it

---

There are plenty of books on standard conventions, most use Microsoft’s, but there are others. Hungarian, etc.
The easiest way to enforce it at work is to fire anybody who gets doesn't use the companies proposed standard, that’s a motivator, lol. Many companies and contracts have a required notation they want used.

Quote:

---

Originally posted by mclark
The only vector member function that I think might have a hard guarantee on reducing capacity (reserve obviously makes one on increasing it) is swap. But swap cannot be performed by iterator - and hence not with a normal array (where you control the size).

---

Just as an aside. swap also does not have a hard guarantee
on reducing size. According to Meyers the implementation is still
allowed to ignore the request to trim all the excess capacity.

Quote:

---

oktronic
Various bits of STL have been posted and if you feel that someone's dislike of one letter variables means that they "have yet to learn this", then I think you have yet to learn about good design.
No programmer worth anything would ever say that one line functions, and uninitialized variables, and one letter names are pretty coding. Any well written program should read as easy for another programmer as English. If another programmer has to walk around your code trying to figure out what is what, then you have written your code poorly and in most production environments you would be warned then fired for such poor produce.

---

I think STLPort is pretty readable. It does use variable names which are a bit ugly to the trained eye, but well, that's their choice. I have seen far worse in publicly available code. Plus, this doesn't prevent me from understanding the code.

The problem is that each programmer has her own approach to things. This is alleviated by having a standard notation style, but there is not one standard, nor is there a general consensus what is good and what is bad.

The essence of this point is, however, that it doesn't really provide an argument against using STL. If you want to look at MFC's code, you have to disassemble the MFC dll and step through assembler instructions. In my view, this is much worse than reading one-letter variable names. The source code for STL is there, if you want to use it fine, if you don't, just get a book or use the online documentation at www.sgi.com/tech/stlport.

Quote:

---

oktronic
Which is another misconception in this debate. There are no rules when it comes to containers. Nothing says that a linked list has to allocate memory at each insertion. You can do the work wherever you choose. You can allocate yourself, or let the system do it for you. The same goes for vector.

---

There are certain fundamental rules when it comes to ADTs (Abstract Data Types) and these are the naming conventions as used by people like Knuth. Of course, your own container can be a hybrid or an optimized version of one or two standard ADTs etc. If you call your container a linked list, then there are basic assumptions we can make:
- insertion of an element anywhere is O(1)
- deletion of an element anywhere is O(1).
Usually this goes hand-in-hand with the assumption:
- access to the Nth element is O(N).
Since you can't post the source code for your own implementation, you can at least say whether these hold or not.

A std::vector is a very different kind of beast:
- insertion at the end is amortised constant time.
- insertion anywhere else is O(N)
- deletion at the end is amortised constant time.
- deletion anywhere else is O(N)
- access to the Nth element is O(1).

Whether or not memory is physically, structurally, logically or OS-level contiguous doesn't matter in the discussion about algorithms. What matters is how we, as programmers, access the memory. If we do it in a single instruction (meaning assembler instruction), like a[10], then that is categorised as fast ( O (1) ). If we do
for (int i = 0; i < 10; ++i) a = a->next;
then this is slow access O(N). The reason the only valid measure is the complexity is because this is source code and can be:
- compiled on different compilers, each producing a different optimisation
- compiled on different computer types, like x86, motorola, etc.
- run on different types of CPUs
- run on different types of OSes

Each of these have very real influences on how fast the code runs in absolute terms. However, these distinctions are irrelevant when you come to distinguish between the complexities of algorithms and operations on containers (provided basic assumptions about the machine hold).

Quote:

---

oktronic
If you are writing a program for just yourself, then you don't have to really care what it looks like, but when you are writing a program for a client then design is everything. It doesn't matter if its an entire program or just a SDK, your library wont be used it its difficult to understand or read. This is exactly what happened to STL. It surfaced in the early 90's to most of us "in the loop" programmers and mid 90's for the general public. It took several years for anybody to even pick a book up on it.

---

Of course. It also took many years from the initial support of templates to their widespread use, as it is still taking time until exceptions and namespaces are used by mainstream programmers. STL is not just a bunch of functions to call since it comes with its own paradigm, unfamiliar to most people, when STL was released. If you don't understand the ideas behind code, trying to figure them out by reading the source is *extremely* hard in many cases. This is of course made worse by the fact that the producers of the code had to make do with very limited compiler support and probably didn't intend people to really read the source anyways.

Quote:

---

Originally posted by oktronic
I think that answered it. Did you really think Stepanov would refer to 15 years of work as "quick and dirty"? lol

I know you are looking for anything to help you argue your opinion, but perhaps you should spend a little time looking into the mind of the creator of STL and into those who came long before him. Even Stroustrup wasn't eager to support STL and made Stepanov modify it before he would offer it up as a standard, maybe you should look at why?. A little research can go along way.

---

Ok, let's see what Stroustrup had to say in an interview: (http://www.research.att.com/~bs/01chinese.html)

Quote:

---

INTERVIEWER: Would you please tell us the most unforgettable, the happiest and the most regrettable things you felt in the course of standardization?

STROUSTRUP: ...the final 1998 vote ratifying the ISO standard. In between those events, the vote to accept the STL as part of the standard library standard stands out as a most happy event.

... (and later) ...

STROUSTRUP: Note that one major reason that the STL succeeded was that it was a technical breakthrough. It wasn't simply "yet another container library", so it didn't have to compete directly against the many existing container libraries (several of which were of excellent quality).

---

Yes, Stroustrup had a few early arguments on details, but then he became one of the strongest supporters of the STL -- calling its acceptance as one of the happiest events in the C++ standardization. He even said it "wasn't simply 'yet another container library.'" So, oktronic, I don't know where you get the idea that the STL was added simply as a "quick and dirty container library." There is no support for this argument! (Or are you just trying to play devil's advocate and get on people's nerves?)

Quote:

---

Originally posted by KevinHall
You are missing the point. Does the following code mean that C++ is a bad language?

code posted...

That code is Galathaea's (hope you don't mind)...

---

I don't mind the post, but I feel a little awkward because I'm actually kind of proud of that piece of code. I think a more appropriate link might be found over here where we can see one of the first debates I entered coming into these boards. In particular, it shows me being wrong. Which I have been numerous times in the past and will be numerous times in the future. I don't know exactly why, but somehow I feel that reading through the psychologies displayed in that thread can provide an important compare / contrast for this thread. That was certainly the turning point for me in understanding that the quality of posts over at this site is quite top notch and that I still had a lot to learn. Sure I still front (this thread is a great example), because that is my nature, but I find it very informative to look over my failures every now and then as well, to see where I need to improve...

Quote:

---

Originally posted by galathaea
I don't mind the post, but I feel a little awkward because I'm actually kind of proud of that piece of code. I think a more appropriate link might be found over here where we can see one of the first debates I entered coming into these boards. In particular, it shows me being wrong. Which I have been numerous times in the past and will be numerous times in the future. I don't know exactly why, but somehow I feel that reading through the psychologies displayed in that thread can provide an important compare / contrast for this thread. That was certainly the turning point for me in understanding that the quality of posts over at this site is quite top notch and that I still had a lot to learn. Sure I still front (this thread is a great example), because that is my nature, but I find it very informative to look over my failures every now and then as well, to see where I need to improve...

---

Not the goto thread, I'll do anything you ask, but please not the goto thread.

Haven't we beaten this horse to death already??? Both hooves that is...

Quote:

---

Originally posted by galathaea
I don't mind the post, but I feel a little awkward because I'm actually kind of proud of that piece of code.

---

I posted it becase I think it is a beautiful piece of obfuscated code!!! :) That's all!

- Kevin

And I think you have every right to be proud of that code! Heck I admire it!

- Kevin

Quote:

---

Originally posted by Mick
Not the goto thread, I'll do anything you ask, but please not the goto thread.

Haven't we beaten this horse to death already??? Both hooves that is...

---

You Win Mick;)

A follow-up on the timing results I had with Dinkumware's STL on VC.NET 2003. The issue is not that Dinkumware is slow, but that *even in Release mode*, the IDE still debugs memory allocation and deallocation through new. This makes Dinkumware appear very slow. Once the program is run from the command-line, this artifact disappears and it is just as fast as the other STLs:

Code:

---

VC.NET 2003 with Dinkumware
std::vector with reserve        : 0.00999289
std::vector without reserve      : 0.044542
Custom allocator with std::list  : 0.624065
Standard allocator with std::list: 0.812536
Standard allocator (new_test)    : 0.797157
C-style array                    : 0.0101577

---

I found this information after a lengthy search:

http://support.microsoft.com/kb/278604

I used regsvr32 with the five dll's under the Jet 4.0 OLD DB provider and it worked for me.

I fail to see how that relates to an 8 year old thread about the STL...

Viggy

Quote:

---

Originally Posted by MrViggy

I fail to see how that relates to an 8 year old thread about the STL...

Viggy

---

Signature Spam fail.