52

I'm on Linux; looking at the STL headers; they're really really complicated.

Is there, somewhere, a smaller version of STL that has the core features of the STL, but is actually readable?

Thanks!

anon
  • 41,035
  • 53
  • 197
  • 293
  • Why do you need it to be readable? You're not supposed to need to read the source code. It is documented so you can use the library without having to read the specific implementation – jalf Jan 24 '10 at 15:55
  • 7
    I'm writing some templates of my own. I want to understand how the STL is implemented to learn from their tradeoffs. – anon Jan 24 '10 at 15:57
  • 19
    @jalf » It's often worth it to peek under the covers for educational purposes. Not every look inside a black box is for sneaky encapsulation-breaking reasons. :) – John Feminella Jan 24 '10 at 15:58
  • 1
    @John: But most of them are. Anyway, there is little to learn from it. STL code is not designed to be 1) nice, or 2) portable. It is typically designed for specific compilers and platforms, which means it can get away with all the implementation-specific hacks that your own code should *not* rely on. There is plenty to learn from the STL, but you learn it from the interface and the documentation and the underlying design, *not* the implementation. – jalf Jan 24 '10 at 16:02
  • @jalf, I think that the MSVC version, for example, could be considered all but readable :> – Kornel Kisielewicz Jan 24 '10 at 16:09
  • @jalf: I disagree; as you gain understanding of the C++ language, the implementation of the STL is quite understandable. It just takes "a while" for that to happen. :o – Sam Harwell Jan 24 '10 at 17:16
  • 3
    @280Z28 There is no "the implementation of the STL". –  Jan 24 '10 at 17:24
  • @Neil: I'm not entirely sure how to reply that? – Sam Harwell Jan 24 '10 at 17:58
  • @280Z28 I meant there is no "the" implementation - there are lots, some more (or less) readable than others. –  Jan 24 '10 at 18:00
  • @280Z28: Just because it is possible to learn the language (and be patient enough) to understand a STL implementation, it doesn't automatically follow that you'd *learn* anything from the exercise. And just as relevantly, there's no guarantee that what you "learn" is actually good. Most people who go this path immediately start using underscore followed by capital letters for all their template parameters, because that's what the standard library does........ And of course, this isn't legal because those names are reserved for the implementation. – jalf Jan 24 '10 at 18:11
  • If you want to learn the nitty gritty details of C++, read the standard, *not* a STL implementation – jalf Jan 24 '10 at 18:11
  • Different rules apply for the standard library and for user code. Trying to emulate the standard library when writing user code is generally a Bad Idea. For portability reasons, for standards compliance reasons and for readability reasons. – jalf Jan 24 '10 at 18:12
  • @Neil, I know that. :o @jalf: I meant that understanding an STL implementation is a side effect of a deep understanding of the C++ language and how it's meant to be used. Understanding is not just the "how," but also the "why." As I mentioned in my post below, understanding follows only after knowing the goals, rationale, and benefits and limitations of the language (C++). – Sam Harwell Jan 24 '10 at 18:20
  • 1
    @280Z28: Let's not get sidetracked. The OP wants to read his STL implementation as a learning exercise. So for the purposes of *this* question, reading and understanding a STL implementation is *not* a side effect. Apart from that, you're not likely to learn the "why" by reading source code. Taking my above example again, reading the source only tells you the "how": (template types should start with underscore followed by capital letter), but it doesn't tell you the *why*: (because those names are reserved for the implementation so we don't risk collisions with user-defined names) – jalf Jan 24 '10 at 18:52
  • Boost. Though it is still rather complicated. – Han XIAO Aug 24 '18 at 05:28

9 Answers9

30

There is a book The C++ Standard Template Library, co-authored by the original STL designers Stepanov & Lee (together with P.J. Plauger and David Musser), which describes a possible implementation, complete with code - see http://www.amazon.co.uk/C-Standard-Template-Library/dp/0134376331.

15

Yes, there is original implementation of the STL by Alexander Stepanov and Meng Lee. It is the most readable STL implementation I have ever seen. You can download it from here.

Below is an implementation of pair. Note how readable the source code really was:

#include <bool.h>

template <class T1, class T2>
struct pair {
    T1 first;
    T2 second;
    pair() {}
    pair(const T1& a, const T2& b) : first(a), second(b) {}
};

template <class T1, class T2>
inline bool operator==(const pair<T1, T2>& x, const pair<T1, T2>& y) { 
    return x.first == y.first && x.second == y.second; 
}

template <class T1, class T2>
inline bool operator<(const pair<T1, T2>& x, const pair<T1, T2>& y) { 
    return x.first < y.first || (!(y.first < x.first) && x.second < y.second); 
}

template <class T1, class T2>
inline pair<T1, T2> make_pair(const T1& x, const T2& y) {
    return pair<T1, T2>(x, y);
}

Back to the roots!

josliber
  • 43,891
  • 12
  • 98
  • 133
ezpresso
  • 7,896
  • 13
  • 62
  • 94
  • Too bad this version doesn't care our `std::bad_alloc` and just lets memory leak. –  Mar 30 '19 at 18:01
  • @StaceyGirl Can you elaborate a little? – piepi Jul 04 '19 at 11:54
  • @piepi Iwas talking about STL implementation mentioned in this post. Look at how `vector::reserve` is implemented. There are elements being copied that can throw an exception in which case allocated memory chunk will not be freed. –  Jul 04 '19 at 12:55
7

Note that GCC's STL headers have the tab stop set to eight. Reconfigure your editor or replace tabs with eight spaces and it should be much more readable.

Potatoswatter
  • 134,909
  • 25
  • 265
  • 421
5

I use the The C++ Standard Library: A Tutorial and Reference and can highly recommend it. Of course it is not something you read cover-to-cover, but is an very handy reference. Check out the reviews on Amazon as well.

bahree
  • 586
  • 5
  • 13
  • 18
    A great book, but one that does not address the question. –  Jan 24 '10 at 17:16
  • yep, the book doesn't have the implementation of the STL; it only shows how to use it, so indeed this answer does not actually answer the question – xdavidliu Jul 21 '22 at 11:57
5

Two key points stand out:

  1. No implementation of the STL is readable without an understanding of the goals, rationale, benefits and limitations of the language itself, and general approach.
  2. Most implementations are readable once you have a deep understanding of (1) because the code is self-documenting on those premises. You might not like the formatting, but that really should be the least of your problems.

As a side note, you might have more success with the MSVC version because it's not trying to target multiple as many compilers. Compiler bugs and implementation-defined behavior result in various subtle workarounds. As those workarounds grow in number (as certainly happens when you add more compilers), the code can get gross fast.

Sam Harwell
  • 97,721
  • 20
  • 209
  • 280
4

RDESTL provides a 'small subset of STL functionality' (but also has some extras). I personally found the code quite instructive and easier to navigate than the big guys like STLPort or Dinkumware's implementation that ships with VC++.

Eugen Constantin Dinca
  • 8,994
  • 2
  • 34
  • 51
3

For a more recent and thorough explanation of the "rules" of STL (such as iterators), check out a new book co-authored by Stepanov: http://www.elementsofprogramming.com/

If you enjoy mathematics, this book will excite you, because what the authors describe is essentially an algebra of computation. The site includes a sample chapter.

Jon Reid
  • 20,545
  • 2
  • 64
  • 95
2

Well, the STL is pretty complicated, so I think there's a certain amount of essential complexity going on here. It's not surprising that it may seem a little bewildering at first glance.

That said, maybe you could check out Borland's STLport and see if you find that an easier read.

John Feminella
  • 303,634
  • 46
  • 339
  • 357
  • 2
    Note, STLport is not a product by Borland. STLport is implemenation based on original SGI STL version. Borland just switched to STLport with in BCB6, but it does not maintain or own STLport project. – mloskot Jan 24 '10 at 16:23
1

The STL is a highly optimized library that does most of what it does by cleverly exploiting advanced features of C++ and the underlying compiler. Additionally, many things are inlined so there is no real bunch of code to look at like in an application. I'd recommend following Neil's advice.

Thorsten79
  • 10,038
  • 6
  • 38
  • 54