Talk:Standard Template Library

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject C/C++ (Rated Start-class, High-importance)
WikiProject icon This article is within the scope of WikiProject C/C++, a collaborative effort to improve the coverage of C/C++ on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Start-Class article Start  This article has been rated as Start-Class on the quality scale.
 High  This article has been rated as High-importance on the importance scale.
This article falls within the scope of C++.
 

STL port[edit]

Mention STL Port?

71.241.55.247 02:21, 1 December 2005 (UTC)Anon

I changed the second paragraph to emphasize modern compiler practice rather than problems resolved years ago.

71.241.55.247 02:21, 1 December 2005 (UTC)Beman Dawes (past chair of the C++ Standard Committee Library Working Group, founder of Boost)

it should be mentioned that what people today refer (imho errenously) to is *not* the HP/SGI STL and that the SGI STL contains additional stuff like slist, rope, hash_map etc. and that it never contained streams etc. and that it is confusing when people talk, since old c++ programmers really mean the sgi stl when talking about stl, and newbies mean the c++ standard library

the quote on deriving from stl containers is somehow misleading, it is not a problem, if the stl container is not treated as polymorphic class. --84.161.172.28 14:25, 11 July 2006 (UTC)

i agree with previous comment, there's no problem with derivation from stl containers (even if you are a novice...). 62.57.176.181 20:32, 31 December 2006 (UTC)

Overview[edit]

I absolutely do not understand what the STL concept has to do with the von Neumann computation model. And what is "value semantics" and what is its relation to the STL concept? -- 139.19.10.235 08:41, 7 September 2007 (UTC)

"This approach provides compile-time polymorphism that is often more efficient than traditional run-time polymorphism"

Says who? 72.236.149.135 15:48, 8 October 2007 (UTC) Steve

Says the fact that virtual functions are slower than regular functions, and slower yet than inline functions. The difference is significant on the scale of high-performance inner loops. Xerxesnine 18:50, 8 October 2007 (UTC)

So when it says more efficient it means faster? How often is often? Has there been a performance test which we could quote? In what situations is it faster or not? ~~Steve

As far as I can tell, faster == more efficient in this context.
Compile-time polymorphism is always faster than run-time polymorphism when the two are isolated and compared side-by-side. The "performance test" is to simply look at the meaning of virtual function, regular function, and inline function. The overhead of a virtual function is that of a regular function plus a pointer dereference, and an inline function has no overhead at all.
The mention of "often" looks like a weasel word to account for contrived cases. For example, a program which creates 1 million different instantiations of std::vector<> and makes minimal use of each one may be slower than a dynamic-common-base-vector equivalent, merely due to missed cache hits. There may well be no program ever written which demonstrates a performance loss due to compile-time polymorphism. Xerxesnine 18:35, 9 October 2007 (UTC)

"value semantics". I can't believe that has its own wikipedia page. This means compare by value not by reference? Does that qualify as semantics? Useless confusing. 120.151.148.158 (talk) 04:13, 31 January 2013 (UTC)

container adaptors[edit]

Why are the container adaptors (queue, priority_queue, and stack) not mentioned? They're in the specification. Herorev 06:00, 24 December 2006 (UTC)

Added: http://en.wikipedia.org/w/index.php?title=Standard_Template_Library&diff=315855166&oldid=314347616 Enerjazzer (talk) 04:52, 24 September 2009 (UTC)

Strange criticism section[edit]

I am struck by how nonsensical the criticism section is. I support the existence of a criticism section, but of course the criticism has to make sense first.

  • Initialization of STL containers with constants within the source code is not as easy as data structures inherited from C.
But that's not a "design flaw" of STL. Is the criticism that the C++ grammar was not modified to accommodate initialization of STL containers?
Whatever the source, it is something to be aware of when using STL containers. It is easier to initialise a C array than a std::vector. I'll agree it's more a caveat than a criticism, though. 81.145.130.231 (talk) 11:07, 28 June 2011 (UTC)
  • STL containers are not intended to be used as base classes (their destructors are deliberately non-virtual). Deriving from a container is a common mistake made by novices.
But that's not a criticism of STL. It's a criticism of C++'s general preference of efficiency over novice-friendliness. Destructors should be non-virtual for good reasons.
Again, this is a caveat/usage note. If you want to create your own vector (one which, for example, implements 'exists') you have to wrap the stl one, you can't inherit from it. There are good reasons to make the destructors virtual, but this is one of the notable consequences of doing this. 81.145.130.231 (talk) 11:07, 28 June 2011 (UTC)
You can inherit from STL container. If you worry about virtual destructor then inherit privatly and use using declaration. http://ideone.com/8CvWW7. In particular Stroustrup uses inheritance from stl container in "Programming -- Principles and Practice Using C++" book http://www.stroustrup.com/Programming/std_lib_facilities.h - fact that you are not allowed to delete via pointer to base doesn't make it un-usefull. — Preceding unsigned comment added by Evgeny.Panasyuk (talkcontribs) 14:52, 31 July 2013 (UTC)
  • The concept of iterators as implemented by STL can be difficult to understand at first: for example, if a value pointed to by the iterator is deleted, the iterator itself is then no longer valid. This is a common source of errors. Most implementations of the STL provide a debug mode which is slower but can locate such errors if used. However, at present no better replacement for iterators has been suggested and a similar problem exists in other languages, for example Java and C#.
OK, when I delete an element through an iterator, the iterator is invalidated. How is this a criticism of STL? Also, I was not aware that the world was waiting for someone to suggest a "better replacement" for iterators.
In Java, the Iterator interface allows to delete the current value. If this is done, the iterator stays valid
  • The design of STL allocator (used by the containers) is widely seen as flawed.[citation needed]
How so? I've not encountered this opinion before.
Allocators are static interfaces, not objects. Due to this you can't have several allocator objects of the same type managing different pools: you'll have to create special classes for each pool. I believe this was discussed in books of Herb Sutter or Scott Meyers, not sure where exactly. Enerjazzer (talk) 01:40, 9 April 2010 (UTC)
  • The set of algorithms is not seen as sufficiently complete (for example, the copy_if algorithm was left out by oversight).[citation needed]

A standard is a standard, and every standard is revised. Just because something is not in the standard, does not make it incomplete. Bjarne admits it was his intention to include this in the standard, but that is just an interesting irreverent fact which does not affect usability. The fact of the matter is that the STL has ended the most C style pointers and pointers to pointers, or worse, pointers to pointers to pointers. I know, I used them in my old C code.

Yes, copy_if was left out. However the fact that copy_if is easily implemented is evidence that STL sufficient. Remember, sufficient does not mean "covers every possible case". Here is the first google hit for copy_if:
template <typename InputIterator, typename OutputIterator, typename Predicate>
OutputIterator copy_if(InputIterator begin, InputIterator end,
                       OutputIterator destBegin,
                       Predicate p)
{
   while (begin != end)
   {
     if (p(*begin)) *destBegin++ = *begin;
     ++begin;
   }
   return destBegin;
}
Actually, the existing STL algorithm "remove_copy_if" already accomplishes the same thing as the hypothetical "copy_if", except with the predicate negated. So it is not "left out". --Spoon! (talk) 03:27, 15 May 2008 (UTC)
So? "Copy" without the "if" is even easier to implement, but it's still in there. In fact, "vector" or "list" are kinda easy to implement. Not a valid argument. Spoon! is right about using "remove_copy_if", but why require that extra twist of mind? Seems like an arbitrary decision and serves as an example for other arbitrary inclusions/exclusions. 217.111.33.2 (talk) 10:35, 17 February 2011 (UTC)
"The set of algorithms is not complete" - set of algorithms can NOT be ever completed. — Preceding unsigned comment added by Evgeny.Panasyuk (talkcontribs) 15:02, 31 July 2013 (UTC)
  • The interface of some containers (in particular string) is bloated; others are considered insufficient.
<string> is not part of the STL. Who considers the "others" insufficient, and why? Insufficient compared to what?
SGI's STL reference lists the String package as part of the STL. I am not sure if this is definitive or not. --Spoon! (talk) 03:27, 15 May 2008 (UTC)

Spoon: Roguewave also included string in their lib when they released their stl rendition. The nightmare started when stl, and string were then added to new compiler revisions, because you should not have two implementations of string, because they behave slightly differently, and make reading the code a bugger. (But this is a tangent, string is not part of the STL.).

FWIW, Alexander Stepanov himself considers std::string's interface excessive, as described in his [www.stepanovpapers.com/notes.pdf Notes on Programming]. —Ben FrantzDale (talk) 00:27, 16 May 2008 (UTC)
The fact that Stepanov considers it bloated does not mean it is part of the STL. He also considers OOP to be a hoax. According to the C++ Primer Plus by Prata, string is *not* part of the STL. It's on page 933: "The string class, although not part of the STL, is designed with the STL in mind." This criticism is *not* of the STL and is not valid. --202.93.162.3 (talk) 01:00, 12 July 2011 (UTC)
  • Hashing containers were left out of the original standard, but have been added in Technical Report 1, a recent extension to C++.
But that's not a criticism of STL. That's historical information about the formation of the STL standard. Hashes were not included for several reasons. You can disagree with those reasons, but you'll have to explain why.
The implementation of TEMPLATES, which is how the STL is implemented, is clumsy with some compilers and linkers. The problem is that they define the function in each generated object code, thus, they later have to deal with the fact that a function is defined more then once.

Xerxesnine 03:16, 24 April 2007 (UTC)

More criticism - bind[edit]

The parameter binding constructs for function objects don't work with references (&), although they work with values and pointers. That once sent me debugging for days, until I discovered what it was and that it was a known issue. If I remember right, that is being adressed in the new standard, not sure though. It does work in boost, however. 217.111.33.2 (talk) 10:16, 17 February 2011 (UTC)

Yes, it is being addressed by deprecating bind1st and bind2nd in favor of std::bind (boost::bind). decltype (talk) 11:42, 17 February 2011 (UTC)

External Links section[edit]

  • Any reason for not adding MSDN's STL reference? —Preceding unsigned comment added by Zvirack (talkcontribs) 08:25, 3 September 2007 (UTC)


You're free to modify the section as you see fit. — Frecklefoot | Talk 13:22, 24 April 2007 (UTC)

STL vs Standard Library[edit]

It is my understanding that bitset, valarray, and string are not part of STL, but separate parts of the C++ standard library. They were adjusted to be more STL compatible. So the "Other Types of Containers" section and discussion of strings in the criticisms section should be removed.

Perhaps we need a small comment about the separation and delineation between STL and the rest of the C++ standard library, as this seems to be a source of confusion. It is alluded to in the History section ("It also influenced other parts of the C++ Standard Library, such as the string facilities...") but not explicitly stated. —Preceding unsigned comment added by 203.110.131.5 (talk) 08:03, 8 October 2007 (UTC)

I agree this article, or the C++ standard library article, or both, should clarify and make WP:OBVIOUS exactly what is the difference between the "Standard Template Library" and the "C++ standard library".
Is valarray, string, and bitset part of the STL?
The book "Using the STL" by Robert Robson p. 3 implies that valarray was once not part of the STL, but is now part of the STL, when it says:
"The original version of the STL was produced by Stepanov and Lee at Hewlett-Packard and released in October 1995. The standardization committee ... added important classes such as the string and the valarray. The version of the STL used in this book corresponds to International Standard ISO/IEC 14882, Programming Languages -- C++, of September 1998."
The SGI "Standard Template Library Programmer's Guide" index seems to imply that bitset is now part of the STL, and the basic_string chapter of that guide seems to imply that string is now part of the STL. So is the current version of the STL (not the 1995 version) the same as "The parts of the current C++ Standard Library that are not included in the C standard library"? If not, what exactly is the difference? --68.0.124.33 (talk) 22:43, 12 March 2009 (UTC)
Not quite. The current SGI STL seems to differ from the C++ Standard Library in many ways. Most notably, it lacks locales, iostreams and the numerics library. Apart from that, it provides extra containers not present in the Standard Library, like slist, rope and hash-based containers. The behaviour and requirements of the components may also be subtly different from their standard counterparts, because the wording is different. decltype (talk) 07:05, 13 March 2009 (UTC)
Completely agreed. This article seems to imply in many cases that the STL is part of the C++ Standard, which is simply not true. We could have an article on the STL and an article on the C++ Standard Library (with a note in both that parts of one are based on parts of the other), or we could make it clear here. Tomalak Geret'kal (talk) 15:47, 19 August 2010 (UTC)

Criticism: Efficiency of vectors[edit]

Probably the most useful and most used part of STL is the vector container. I think it is a significant criticism that vector has speed inefficiencies when compared to use of C arrays and memmove. There has been quite a bit of discussion of this in various forums which has generated more heat than light. This would be the ideal place to clarify this.

Note that this criticism is often dismissed as poor use of vector. Indeed in many cases judicious use of vector::reserve() would resolve it. However, there are still many situations where vector is less than ideal. For example, it is the reason that vector itself is never used in the implementation of deque.

BTW I agree with the above discussion under "Strange Criticism section". —Preceding unsigned comment added by 203.110.131.5 (talk) 08:31, 8 October 2007 (UTC)

lol.....Ok, C++ is slower then C. And C is slower then assembler. Perhaps you should program in assembler if you consider this a flaw. lol. C and C++ are the fastest executables compiled today. STL does not change that fact. I've never worked somewhere where they decided that the code needed to run 20% faster, it's always been multiple times faster that they want. The diffrence between C++ and C is quite honestly, a percentage difference. The difference between C and C++ compiled code, is not something the employer has ever worried about (except for Shannon Labs at AT&T, and Credit Suisse Asset Management, etc.). As long as we are on this tangent, then fyi, fopen and open do not invoke locale like the c++ stream file opens. Now, there is an important thing to know about C vs C++, and how to program for the fastest hard drives of today. But, that means nothing for anyone programming for a PC, since no customer is going to have a rack mounted shark hard drive on their laptop. 95% (i'm guessing) of all C++ programming still can use ifstream, and ofstream, and enjoy the benefits of streams, and not fret about being up to 20% slower then using straight C. — Preceding unsigned comment added by 162.72.225.8 (talk) 14:14, 16 July 2013 (UTC)

I think the speed and efficiency gripes are mostly imaginary. Much of it depends on style anyway. There are numerous demonstrable cases where C++ produces better machine code than C simply because the optimizer can reason better about C++ than it can about C. It is true that this used to be a problem in the 1990s, but if you are using old compiler technology and old programming practices in C++, then you are asking for bad performance.2003:69:CD04:2601:2E81:58FF:FEFF:8F4B (talk) 12:56, 15 September 2013 (UTC)

Background questions[edit]

"The STL was created as the first library of generic algorithms and data structures for C++, with four ideas in mind: generic programming, abstractness without loss of efficiency, the Von Neumann computation model, and value semantics."
  • What does the Von Neumann computation model have to do with STL?
  • What is meant with value semantics?

Thanks, --Abdull (talk) 13:54, 23 January 2010 (UTC)

value semantics means that the STL containers physically hold their elements and manage their lifetime, e.g. an object can't exist longer than the container that contains it. It also means that an object can't be element of several containers at once. Opposite is reference semantics, when containers hold references/pointers to objects that are managed (created/destroyed) externally. Note that if you have a copyable reference type (examples are pointers (both plain and smart like boost::shared_ptr) or structures like boost::ref) you can store them as objects in value-based containers while the referenced objects are managed outside, as well as having several reference objects (maybe in different containers) referencing the same actual object - so in presence of copyable reference types value-based containers can serve as reference-based containers as well. Enerjazzer (talk) 01:02, 14 September 2010 (UTC)
See Von Neumann architecture. —Ben FrantzDale (talk) 11:38, 14 September 2010 (UTC)
What prevents STL on running on hypothetical non-Von-Neumann computer, for example the one with separate memory for instructions and data? Interesting though that it doesn't really matter for Wikipedia, what matters is an appropriate citation. Ipsign (talk) 13:12, 15 September 2010 (UTC)

Thread safety[edit]

Article claims that first implementations werent thread safe, but AFAIK current ones aren also. Only thread safety guarantee is that multiple readers can read without problems, but multiple writes are undefined behavior. — Preceding unsigned comment added by 92.251.82.38 (talk) 13:44, 2 August 2011 (UTC)

It is up to the programmer to write thread safe code. This is why we have mutexes and "critical sections". Generally, speaking, most multithreaded code is unnecessary and could have been done with multiprocesses each running in a single thread. — Preceding unsigned comment added by 162.72.225.8 (talk) 15:09, 16 July 2013 (UTC)

Standard Template Library: proper noun or not?[edit]

There's an ongoing discussion about whether Standard Template Library is a proper noun or not. Please express your opinion. 1exec1 (talk) 17:40, 3 December 2011 (UTC)

What is this page supposed to be about?[edit]

Is this about the elements of the C++ standard library that were originally inspired by and modeled after parts of STL, or is it about STL and its legacy? It seems like that page can't decide: it opens talking about STL in present tense, but describes the long-abandoned library, then it lists some of the C++ containers, many of which were once modeled after the interfaces defined in STL, then it vaguely mentions iterators, algorithms, and functors (vague enough to fit either focus), and then talks about the history of the actual STL until the first C++ standard. Then there's the low-quality 'criticisms' section, and then there's a list that mixes STL implementations with C++ libraries, some of which aren't STL implementations (missing things like rope, compose2, select1st, 3-way compare, random_sample, bit_vector, Monoid, not to mention all the changes and extensions of the STL-based content in the C++ library that occurred in the last 15 years). --Cubbi (talk) 17:28, 24 September 2013 (UTC)