Downsides to the C++ STL? 1046
craybob queries: "I'm a developer for a small software group that will soon migrate from using Rouge Wave to using the C++ STL. I just left the week-long Software Developers 2002 conference, where I heard the great minds in software tell us all of the best ways to take full advantage of the STL. (I just wanted to give a quick thanks to Stephen Dewhurst and Scott Meyers) From this I came away with the feeling that this is the Holy Grail of C++. I'm sure these guys are right and that it is great, but the truth is that I'm a skeptic, so what are the downsides to the STL?"
So many standards to choose from (Score:4, Insightful)
Pitfall 1 : Lousy implementations/compilers (Score:4, Insightful)
Re:Lots of overhead. (Score:2, Insightful)
It really helps to pre-plan what you're going to do with the STL (I guess that goes with everything else in software dev). It can get really ugly if you use them on-the-spot as you hack away at an implementation. But if you think it through, you can control the costs of using the STL. Pre-plan and take advantage of C++'s "pay only if you use it" philosophy.
the STL is imporperly named (Score:4, Insightful)
As with OOP itself, generic programming is a Really Good Idea but its implementation in C++ leave something to be desired for simplicity and accessability. Due to C++'s dominance in the marketplace, the STL will likely be with us for many years, but this is far from a desirable circumstance.
Re:Lots of overhead. (Score:4, Insightful)
Re:Templates can get really, really, really ugly. (Score:1, Insightful)
Enterprise issues with STL (Score:5, Insightful)
Advantages of STL:
- Standardized, comes with every C++ compiler
- Fast
- Generalized (excellent use of templates)
- Many different implementations freely and commercially available.
- Source code available.
Disadvantages of STL:
- Large executable file sizes
- Incompatibilities between implementations
- Complex to debug
STL is a very fast and powerful library. Ignore those who say "it uses virtuals, and is in C++, therfore it is slow" because none of them have ever used it. (C++ is in fact faster than C if coded properly, and STL is coded properly) Often, a good structure is much faster than using arrays, even if they have less overhead.
Unfortunately, STL's use of templates and inlines can inflate the size of your code in exchange for raw speed. This can vary very much depending on your compiler. MSVC adds 200k or more just for the priveledge of using strings! Using STLport still requires that you link in the old 200k libraries ON TOP of STLPort!
I do not recommend using STL on small projects where compiled file size is an issue. For anything else, go for it.
Re:What virtual functions? (Score:1, Insightful)
Re:Not many (Score:3, Insightful)
One think to watch out for is that the string class isn't thread-safe under linux.
http://www.sgi.com/tech/stl/ [sgi.com]
I also recommend Scot Meyers' "Effective STL".
Embedded Platform Issues (Score:4, Insightful)
this is wrong (Score:3, Insightful)
however, that doesn't mean that there aren't any "cons" to the STL. if you don't catch exceptions thrown back from a contain, your bound (no pun intended) for trouble. expect performance hits if you insert into a vector, or you don't allocate sufficient memory ahead of time. the STL only wraps common data structure and their operations - the idea being that you don't have to write a list for Class A and Class B and Class C; you can just create a template of a list that holds a Class A or Class B or Class C. the behavior of a list is similar, the only difference between lists is what they hold.
perhaps what bill was really try to say was "there is a lot of overhead with using C++" for embedded and realtime platforms. that, i would agree with - to an extent. i would have to say that the big performance hit on a RTS w/ C++ would be vlookups against the vtable - but how would that compare to a large switch-case block? the vtable itself may consume a bit more memory, but it might cost much less in manhours and frustration to work with derived classes than to maintain switch case logic. remember, every time someone adds some new functionality, someone has to go through a full compilation/regression test w/ a switch-case. by adding a derived class, you only need to compile/test the class itself.
Re:Check out "Effective STL" by Myers (Score:3, Insightful)
vector is the most useful container in the STL, and is the basis for the STL string class.
Why do a wholesale switch? (Score:3, Insightful)
In our development team, we have people who prefer RW, others who prefer the STL and others who are agnostic. In general, we've had a very good experience getting them to work together. Sure, it tends to lead to larger executables, but that's not a particularly big issue for us.
One thing that I haven't seen others talk about is that the two do not necessarily perform equivilent functions. The STL provides a bunch of templates, and RogueWave provides a bunch of useful classes, some of which are templates. RWTime, for example, has no equivilent in the STL.
Also, if you want to use other RW libraries (such as their threading stuff), then you're going to need to use some of the base RW stuff anyway.
It is hard to learn well (Score:5, Insightful)
The STL is really as good as could be expected. Better even. There are problems. Some problems stem from the fact that it had to be approved by the standards committee. There was a lot of opposition to adding something that big to C++, so the size was cut down. Certain things are missing. (Heaps, general binders, good smart pointers) but versions are provided by many implementations. Check out CGI for one. They will also be added to the next version of the standard, along with a few other nifty things (As always check out boost.org for much of that stuff). The allocators are broken in my opinion. Using (different) customized allocators prevents interactions between your containers.
The biggest problem is its complexity. Like any C++ feature, understanding the STL is not enough. You need to understand how it interacts with other parts of C++. When you use the STL, you are using a rocket launcher instead of a BB-gun, shooting yourself in the foot can be much worse.
All in all the STL is god's gift to programmers. It really is. I can't imagine not having it to program anything serious with. I work everyday with AI and Image Processing algorithms -- stuff where performance really counts, mind you -- and I couldn't live without the STL. I barely use pointers anymore.
To sum it up, C++ with the STL is the only language that meshes (not always prettily) performance computing with high level concepts. It is a truly beautiful technology.
Only a few downsides (Score:2, Insightful)
The most important downside is that some people think that STL is the holy grail. Not so. There is no silver bullet.
The abstraction level can also be a problem sometimes allthough this is not a problem only with STL. For instance a colleage of mine had to spend much time tracking down why 1 million elements of 48bytes each consumed 144MB. I have also seen the usual problem with someone testing if a list was empty by using size()
Another downside is that the STL is a forced standard meaning that the standard was set before the compilers were able to fullfill it. It has gotten a lot better but you can still encounter limitations in all compilers.
Non-obvious limitations is also a downside. The STL has a very clean design which (unintededly) leads to a few strange limitations, such as const_interators not having a != operator
Sometimes programs using STL is harder to debug. It is not exactly pleasant to have a core dump deep inside template-template-template.....RBtree, spending some time figuring out what that is and after a few hours discover that the problem was not the container at all but something that had scribbled on a reference-copied string :-(
The STl is subject to the usual problems with "Quality of implementation". The standard is set but the implementation has been left (third-party) vendors. Why didn't the Standard Committee provide a public-domain reference implementation which vendors could optimize?
Finally, the STL some places show signs of "Design by committe". This can lead to overly complex designs or no design at all (if the committee cannot agree). Do we really need generic character support in basic_string? Which kind of bastard is auto_ptr? Where is the hash_map?
This is not a rant. I use STL frequently. STL has a lot of advantages but the poster only asked for downsides. You just have to keep in mind that there is no silver bullet.
Re:the STL is imporperly named (Score:5, Insightful)
Be careful. It's generalizations like this that end up in the hands of managers and can lead to Really Bad Software(TM). There are plenty of cases where a small generalized solution is more apropriate. THere is no golden paradigm for software development.
Traps for the Unwary (Score:4, Insightful)
Folks complain about code bloat due to template usage but I think it's a reasonable trade-off for type safety. Especially if you were going to create all those classes one way or another anyway. By the by, for some really sick template usage, check out Andre Alexandrescu's "Modern C++ Design."
Debugging is the downside (Score:5, Insightful)
If something's not compiling that you think should, you end up wading through the mile-long error messages. If it does compile but doesn't work right, you're going to find yourself in the debugger trying to step through some of that crazy obscure STL C++ code to try to figure out what the heck is going wrong. Neither is much fun.
But when it does compile and run correctly STL is pretty nice!
I'm looking forward to somebody starting over some day and coming up with a language that supports generic programming as well as C++, but which doesn't have the terrible syntax of C++ templates. It must be possible.
Basically people have realized that templates can can be used to create programs that run at compile time to do some very clever optimizations (template meta-programming is what they call it see http://www.boost.org for one implementation. Blitz++ is the big example use of the stuff that everyone points too). But the code to make this stuff happen is ATROCIOUS!
Yeh, you can make a template meta-program to calculate factorials at compile-time. Great! That sort of thing can come in handy. You can even write template meta-code that basically generates code at compile time. That's cool too! But the code to do it looks NOTHING at all like the equivalent run-time code. Why does it have to be that way? Why does compile-time code have to look SO different from run-time code, at at the same time look SO horrific?
I think what is needed is a new language that will put compile-time and run-time code on equal footing. It would be great if they had the same syntax. Then you could just, say, change one line to turn some run-time code into compile-time code (only when there's no dependence on run-time data, naturally). But it doesn't necessarily make sense to put all the run-time efficiency restrictions on the compile-time language. Dynamic function lookup by strings is a pretty big run-time hit, for example, but you wouldn't care as much if it were used for compile-time function lookup.
In general, the meta-programs seem work a lot more like functional languages -- so fine, I'd be willing to settle for at least a clean syntax for the compile-time language, say something Lisp-like, even if it looks different from the run time language. ANYTHING, as long as the syntax is clean and readable, would be better than the current situation of trying to do meta-programming in C++.
I think the situation C++ is in today with respect to generic programming and meta-programming is a lot like where C was when OOP started to become big. People realized that, yeh, C can do OOP, but it doesn't really support it. C allows OOP, but it offers nothing really to facilitate its use. I think Stroustrup makes that argument in his C++ book. So Stroustrup created C++ as a language that would support OOP, not just allow it.
Well folks, now we've got this handy meta-programming stuff, and yeh you can do it in C++, but it is not pretty. It's downright painful. Writing it is hard. Debugging it is hard. Testing it is hard. Reading it a week after you write it is even hard. Sounds to me like it's time for some new language stud to come and save us.
Re:heh... (Score:2, Insightful)
The other issue is that you must plan ahead and think about what you are doing before you start coding. If you are going to code by the seat of your pants then OOP is a very bad idea. You are far too likely to program yourself into a corner. To be in a situation where something that is burried under five layers of classes needs something that is burried under five entirely different classes is a very frustrating situation. You can back yourself into that situaion with most any OO language.
If you are going to code by the seat of your pants then you should write really ugly Perl. =)
Re:STL Downsides? (Score:3, Insightful)
Sorry, no. If you're working with multiple DLL's and you access a std::list declared in some header from both of them, functions that you call in both DLL's will be located in both DLL's Thus code bloat. For a monolithic application, you are correct.
YOU SHOULD NEVER INHERENT FROM AN STL CONTAINER. Period. There is no good reason to do this. If your design calls for it, then you have a bad design. Besides, STL containers do not have to have virtual destructors so you are introducing potential memory leaks if you inherent from them (this was made part of the standard on purpose).
That's a pretty broad statement, and again I disagree. Suposing you want to create a string class with a subset of the functionality in std::string? Do you re-implement it? Supposing you want to create a structure that is best expressed as a list, but has just a little more functionality? Granted, you have to keep a pointer to the derived class, because of the virtual dtor issue, but its not completely unheard of.
Re:Embedded Platform Issues (Score:4, Insightful)
That's the stupidest thing I've heard all day. You switched from std::string to the MFC CString and you say that STL isn't portable? You don't need MFC's handholding. You go out and find one of the many copies of the STL that's freely available out there and you compile it yourself. You don't switch to something thats even LESS portable.
Re:Not many drawbacks (Score:2, Insightful)
verbose type syntax: When you use the containers,
like (say) std::vector, you have to declare your iterators as:
std::vector<int>::iterator i;
If you change to a std::list container, you'll have to change your declarations. Of course, you can mitigate that by using typedefs, and then you only have to change the typedef, but it can still get a bit wordy.
No !
Never ever directly declare your iterator like that. Instead, use
class A
{
public:
typedef vector<int> IntContainer;
IntContainer mContainer;
void f();
};
then, use
A::f()
{
IntContainer::iterator it;
}
instead of
A::f()
{
vector<int>::iterator it;
}
Magically, now you can go from a vector to a list, without chaning all your iterators declarations.
Re:STL Downsides? (Score:2, Insightful)
C++ templates are one of the best features of the language. Yes, they are a different concept, but embrace it, change is good.
They are no different than a majority of languages out there. Remember that C++ got it's roots from elsewhere.. C++ is anything but different and original. Change is not always good.. especially when the implementation is bad, IMO.
I have no idea what you are talking about regarding templates being created at compile-time as being a bad thing. That's what generic programming is all about!!!
No sir. Generics should be resolved at run-time as much as possible (that is why they added RTTI to C++). With templates being done at compile-time it removes my ability to extend my Linked List to use basic_string and ints without adding yet more code. Templates suck at being generic, especially when you want it at runtime.
Its the compiler generating classes so that you don't have to. It has to be done at compile time. I'd love to hear an example of a language that implements some kind of generic stuff at runtime.
Smalltalk, Python, Dynace, Objective-C and even C... all nice languages
It makes absolutely no difference at runtime.=
I beg to differ. *every* template you instantiate adds to the binary size because of the need to use them. If I create a vector<string> and vector<int> I get *two* vector class and it will increase the binary size accordingly. Another downfall is that you can't mix and match types, so you have to encapsulate your nodes in yet *another* class... adding even more to the binary.
C++ is a young language with a young standard.
Even more reason not to use it!! the STL is *not* standardized, check your implementations.
YOU SHOULD NEVER INHERENT FROM AN STL CONTAINER. Period.
I disagree. You want to extend an STL containter to create better ones.
Remember, STL is standardized so there is no need to worry about stuff like that.
STL is *not* standardized...
For instance??? You are doing yourself an extreme disservice by avoiding STL.
hmm.. wxWindows, QT, Gtk+, Plib, and any other library that wishes to be *portable*. IMO, you do yourself a great disservice for using the STL.
--seaIs it just me.. (Score:2, Insightful)
Cheers,
Backov
Re:One Downside (Score:4, Insightful)
However, I suggest using a real high-level language if you want one (Perl, Python, Smalltalk, Ruby, etc) or going low-level if you want that and programming in C.
C++ and it's less abhorent, bastard child, Java are the ultimate examples of what C isn't good at.
I'm not trolling here. C++ simply isn't a good language design. It has all the power of C and twice the rope for hanging yourself. The complexity, contradictions and requirement that users understand every aspect of the language in order to program are high on my "why you shouldn't" list.
Java has only some of C's problems while being totally platform-antisocial (platform neutral would imply that it plays nicely with all platforms which is patently untrue). I will say that Java has one of the best object models of any language out there, but 1) that will change when Perl6 hits the streets and 2) it's somewhat overshadowed by the failure of the Java libraries to live up to the promise.
* is faster than C (??) (Score:5, Insightful)
I'm calling your bluff. Give me some stats for example programs.
The STL is not OO (Score:4, Insightful)
Just wanted to point out that the STL is not, in any way, an OO system. It uses classes, but that's as close as it gets. There's no use of inheritance, polymorphism (in the usual OO sense) or any other "typical OO" features.
Debugging (Score:2, Insightful)
know about it yet, for the most part, and show
you the implementation of the STL objects instead
of their semantic values.
Re:One Downside (Score:2, Insightful)
Q: How many legs does a dog have if you call a tail a leg?
A: Four. Calling a tail a leg doesn't make it a leg.
You are trolling here. C++ is good language design, for reasonable different definitions of good.
Re:hey! lay off Java (Score:3, Insightful)
Perl has never been such. It is a general purpose programming language used for such varied tasks as image manipulation, scientific computing, database management, and an army of other tasks. Its "standard library" is perhaps the largest such in the industry. Have a look at the official module list [cpan.org] on CPAN [cpan.org].
Perl may be used as a "toy language" by many, but do not assume that that makes it a toy.
Perl6 is a re-design from the ground up, which is in many respects to Perl5 what Perl was to scripting languages. It introduces a real object model that takes the lessons learned and best practices from Perl5's very loose "roll your own" object model. It also retains all of Perl's power while focusing on the problem of creating a back-end that can be efficiently compiled or executed as byte code in Perl's own virtual machine ("Parrot", as it's known).
If you've ignored Perl because it looks scary, go back and try it again. You will be suprised. Very.Go look at that module list. Think about what it means to be able to think "hey, i'd like to..." and find that it's in the standard library! Now imagine how those of us who program in truly high-level languages like Python, Perl, Ruby, etc must feel when we have to "step down" to commercial languages whose standard libraries are controled by committe.
Re:STL Downsides? (Score:2, Insightful)
Call the wrong function name in java or python and you get a runtime exception; call the wrong function in C++ you get a compile-time error. The difference in these two methodologies translates to raw execution speed. RTTI is underutilized in C++ because it's largely unnecessary and facilitates breaking the strong-data-type model. This model is what makes C and C++ so fast; it provides immediate function linkage with no time-consuming function lookup or indirection.
As with all languages- show me the code -- the final assembly code. I am very impressed with how well templated code is inlined, optimized, and scheduled on multiple-pipeline processors. After stripping the symbols from the executable, I don't detect any appreciable code bloat inconsistent with the increase in speed I received by inlining my collection classes. Even MSVC6 can do this.
With the exception of C (and possibly ObjC), all the languages listed use runtime function-name/prototype to function-code binding which is nowhere near as efficient as C or C++'s compile-time function linking. Your mention of C is either erroneous, or you are referring simply to collection classes of opaque data. This is hardly an improvement over the existing options- particularly since it completely circumvents the strong-type model already available with C and C++.
This is a serious stretch of the truth. Every template you instantiate will increase the size of the code- by the size of the vector constructor code- which is usually a dozen or so bytes at most. Only the functions actually used are included in the code- not every function in the template. Most functions are inlined so you can fully expect those to increase the size of the code while providing an increase in execution speed. The typical functions like begin, end, and iterator increment while typically resolve to a single assembly instruction- less than the equivalent function call to a general collection class!
If you create a vector<string> and a vector<int> you will get two completely different sets of code. The vector<int> will not attempt to call constructors for your int's and can ultimately use an assembly-level memcpy to transfer the contents. The vector<string> will call the constructor and/or copy-constructor of every string you add, which is fine since that's what you want. Two completely different implementations for two completely different types- both optimized for their respective characteristics. No runtime vector implementation is going to provide that, period. You will always get worst-case implementation for both int's and string's because strings necessitate special handling for construction, copying, and deconstruction. At runtime, you get the same poor performance for your int's that you do for your strings.
As for mixing strings and int's in a vector... why? Performance considerations must be weighed against implementation. If mixing int's with strings substantially increases the cost of using the vector, there had better be a really good reason. The first reason might be that execution time is less critical than coding time, in which case, you're probably not using the correct language anyway. Java or python might be more appropriate. Again, use the right tool for the job. As far as I'm concerned, mixing types as you described is a recipe for distaster as it substantially increases the complexity of auditing the code in the future. If I'm enumerating this vector, how can I guarantee that I'm not going to find some other data type in there? Do I throw an exception or try to convert to an int? Or should I convert to a string instead?
It's being used, standard or no standard, because the utility of the language exceeds the cost of failing to compile properly on all target platforms. Implementations which fail to compile properly can be remedied, as necessary, on the build target. Field fixes are common in cross-compilation, nothing to see here, move along.
I couldn't care less if someone derives from an STL container or not. The risks are clearly stated, possibly even overrated. I've found that inheriting directly from a container without declaring the new class as a template itself usually leads to confusion later. A private member variable tends to be more effective. Once you leave the realm of "general template" and enter the realm of "implementation", it makes sense to hide the collection class. Who knows, you may decide to dump the STL class for another class later. If the code which relies on your class breaks when this happens, you've done a poor job at object-oriented programming. Plus, this solves the multiple inheritance problem mentioned by another poster since your new aggregating object can have any baseclass it wants.
Assuming you are compiling with gcc, which covers a considerable number of platforms, just how less portable are you realistically going to be? MSVC does a fair job- ATL COM is built entirely on templates (for better or worse, although their primary objective was reduced code size for ActiveX components- templates where largely responsible for this).
I was a skeptic of templates for a long time until I examined the compilation process at an assembly-language level. Sold! Now I use them daily. The time savings is simply beyond belief. I'll never implement a red-black binary tree again. What a template does for general programming is nothing short of exciting- try looking at difference between the assembly generated by vector<string> and vector<int> sometime- it's inspirational!
-Hope
Downside (Score:2, Insightful)
But your mileage may vary.....
Speed over safety w/STL example code (Score:2, Insightful)
typedef map map;
typedef map::iterator map_itr;
map m_example;
.
.
.
for(map_itr itr = m_example.begin(); itr != m_example.end(); )
{
m_example.erase(itr++);
}
Re:One Downside (Score:3, Insightful)
That being said, nowadays my favourite thing to use a c++ compiler for is to implement a library of optimized code and connect it to a scripting language interpreter. Then write the main program logic flow in a nice simple small dynamic language!
www.lua.org
--jeff++
Brings out the worst in compilers... (Score:2, Insightful)
Debugging isn't too easy either.
That said, I do use the STL in many programs because it provides things I need (strings and containers, mostly).
Wishing Ourselves to Death (Score:3, Insightful)
In 2001, Bjarne Stroustrup [att.com] started a dialogue about the future of C++. As primary inventor of C++, Bjarne is giving interviews, visiting user's groups, and posting in forums, all with the intent of stimulating discussion about where C++ should "go." It's an important topic for software engineers, and everyone has a laundry list of features they'd like to see added in the next revision of C++.
I'll buck the laundry-list trend and suggest some things I don't want to put in the next C++.
In my experience, C++ iterators, algorithms, and containers are inefficient and unnecessarily complex. The actual source code doesn't look terribly confusing — it's the underlying mechanisms that obscure function with too much form. We heap template upon template, giving the compiler nightmares while obscuring what is really happening "under the hood."
Is container abstraction akin to the hiding a car's pistons from its driver? No, because I'm not driving the car, I'm building it. And as any good engineer can tell you, hidden complexity and obfuscated parts have been the bane of many software (and hardware) projects. I have no problem with containers being part of the language — what bothers me is that the current set of containers is complicated and inconsistent. We need to refine the current standard before we begin adding new material; otherwise, we build new code on uncertain foundations.
An official template library also leads to another question: Just what is a "standard" container? Some people argue that, for the sake of completeness, we should add hash-based containers to the standard library. But "completeness" means different things to different people; someone might want balanced binary tree containers, while others would prefer B-Tree or r-tree implementations. And then we get into the whole issue of graphical development — and you end up with Java, that tries to be everything to everyone but does few things particularly well.
The current template library is much too heavy, prone to the "feature creep" inherent in a committee-based standards process. And when the standard includes an inconsistency, (list<>.sort() comes to mind), we're stuck with it. Should a list be sorted via its member method or the sort algorithm? And what constitutes a "required" container feature? I use about 20% of the vector<> template 80% of the time; it seems to me that C++ needs a functional hierarchy that stems from a set of concise "base" containers.
We also have the entire realm of garbage collection and "smart" pointers, which is a nasty tangle of divergent opinions. The auto_ptr<> type has numerous logical and practical problems, as does the Boost smart_ptr<>. I don't believe one type of smart pointer makes sense for all applications — and C++'s experience with auto_ptr<> should teach us to avoid providing specific solutions to general problems. I'm still not convinced that automatic garbage collection is a good idea in most applications; it tends to make programmers lazy about controlling their resources.
I've always preached that code should be no more complicated than necessary — and that includes the code I obtain from language libraries. The C++ container types are heavy and detailed, when what we need is a simple set of light, fast containers, with hooks for adding algorithms that fit individual application needs.
Anything else is trying to be Java. ;)
Re:er... "horseshit" (Score:3, Insightful)
C does not attempt to prevent the problem that you cite above. C++ doesn't either, it just gives you a way, assuming you understand the language completely to ask the compiler to make it harder. This adds many layers of complexity and provides you with the situation where the vast majority of C++ programmers continue to use the C-style cast.
Shouldn't your language be simple enough that those books aren't necessary, just to explain a core feature? Shouldn't your compiler either do the work of resolving your complex relationships or get the heck out of your way?I look at any large-scale C++ project and I see something that Perl has classically suffered from too: there's more than one way to do it, and no one agrees on which way that is. In Perl, it's considered a strength because the language is so forgiving that it resolves many of the problems created this way (Python by contrast allows you to do things exactly the way Guido wants you to, and that too can work well). C++ however, does not give you any sort of assistance in resolving these problems, and differing views on which language is being used can be catastrophic.
This is, in fact, one of the reasons that Effective C++ and More Effective C++ should be required reading for every member of any C++ project. It's not that you'll get good ideas, but the fact that those books teach a certain dialect of C++, and gently bludgen the reader into accepting that that dialect *is* C++. The STL also does this by formalizing a dialect of C++ into a library that insinuates itself into your code (I never saw people using functors until STL became wide-spread, and then people felt they had to use them).
C also requires that you adopt some common usage, but the advantage there is that C is so painfully simple that it is hard to adopt a dialect that is wildly out of step with other programmers (I've seen people use cpp to prove me wrong here, and all I can say is cpp is perhaps the worst idea to ever grace a language).
C++ is a very good accedemic exploration of the value of C as a high-level language. It's ultimately a poor choice for real-world programming, but that may not have been an obvious conclusion if Mr. Stroustrup had not been so bold. I don't question the genius of the ideas behind the language, just the danger of using it on a daily basis.
Re:About maps... (Score:3, Insightful)
Hash tables have *amortized* constant time lookup, but worst case behaviour is linear. There are two basic approaches to hash table construction, and they degrade in slightly different ways.
Open coded hash tables use (something like) a vector of cells indexed by the hash value. If there is a collision, you rehash (compute a new and different hash) or scan for an open cell and use that. In either case, you keep going till you find something. This leads to linear scan on a nearly full table. Maintaining these requires the rehashing process you describe.
Bucket hash tables used a list in each cell. You hash to the cell, then scan the list. In this case, an over-full hash-table has long lists to scan. Again, linear in the worst case.
In both cases, we're assuming a good hash function. One easy way to get poor performance out of a hash table is to have a poorly performing hash function.
Now, with respect to the STL, the issue for the designers was, in fact, worst case performance; not expected case performance. Call it a design guideline if you will, but that is what they used as a criterion.
So, as I said in my earlier post, Hash tables were not in the standard because they have poor *WORST CASE* performance. Never-the-less, the good folks at SGI have produced several high-quality hash table implementations that are STL compatable (so have I, for that matter). At some future time, I expect that those hash tables will be added to the STL because they are quite useful, when used properly.
There are several good works on the topic. Knuth's "Art..." being the seminal work on complexity. He covers both types of hash tables in detail in volume 3. I also recall a paper by Stepanov discussing both the ideas behind the STL and the tradeoffs. It's fairly old -- circa 1990 or so IIRC.