7

Recently I am working on a c++ project that I am not allowed to use standard template library or any other templates.

I am kinds of confused after I did some research. What are the containers belongs to standard library while others belongs to standard template library ? Or we don't say container for standard library, do we?

Is vector a container or not? Is vector a class for standard library or it belongs to STL?

I am hoping to implement a list of some structure in standard library, can I use list or vector?

Emil Laine
  • 41,598
  • 9
  • 101
  • 157
leon
  • 73
  • 2
  • 2
    As far as I know, what used to be know as the STL is part of the C++ standard library. There is no STL container any more. They are just part of the C++ standard library. – R Sahu Jul 29 '15 at 05:22
  • Thank you R sahu. I am thinking the reason sometimes we don't use STL is that it costs more memory. Like we use map, the memory of each item is continuous. So I am wondering when people say don't use STL, it means use some class/structure/container that would save memory. – leon Jul 29 '15 at 05:38
  • 1
    Of course, it depends on the project whether it makes sense to use certain parts of the standard library or not and there really are a few cases where you do not want to use them. But I have a feeling that sometimes this is one of the worst forms of premature optimization. – Markus Mayr Jul 29 '15 at 06:18
  • 1
    Ouch, it sucks not being allowed to use `string`. Or `cout`, for that matter. I suspect whoever set the rules you mention didn't really think them through; you should push back and ask what the rules are meant to achieve, rather than just blindly accepting them as dogma. –  Jul 29 '15 at 06:37
  • 1
    Thanks. I faced this issue during interview. I am thinking they want that candidates could implement their own data structure using pointer and class instead using containers in STL. – leon Jul 31 '15 at 20:45

4 Answers4

9

Nothing in the C++ Standard Library "belongs" to the STL. STL is a different library that only influenced many parts in the C++ Standard Library. From the tag wiki:

[STL] is a C++ library of generic containers, iterators, algorithms, and function objects. When C++ was standardised, large parts of the STL were adopted into the Standard Library, […]

However, many people refer to the C++ Standard Library as the Standard Template Library, which is not entirely correct. I'm guessing that if you're not allowed to use the STL, they actually mean that you're not allowed to use the C++ Standard Library. But you'd have to ask them to know what they really mean.

For more information, see What's the difference between "STL" and "C++ Standard Library"?

Community
  • 1
  • 1
Emil Laine
  • 41,598
  • 9
  • 101
  • 157
3

In my opinion, the distinction between STL and the c++ standard library is somewhat similar to the relation between Linux and GNU/Linux:

Historically, STL was the core (including the containers, algorithms and iterators etc.) and the standard library is, metaphorically, a complete operating system built around the core furnishing everything else. The standard library made modifications on top of STL, but that part of the standard library has roots in STL. (Remember how hard the GNU people tried to remind us that Linux is just a kernel, and insist on calling the OS GNU/Linux?)

If the standard committee were writing a paper instead of a c++ standard, they would probably need to acknowledge STL everywhere in the overlapping domain, instead of claiming the differences.

As pointed out in the comments in this answer, Bjarne Stroustrup, the inventor of C++, described STL as

the STL (the "Standard Template Library"; that is, the containers and algorithm framework of the ISO C++ standard library)

What's more, a core feature of the STL that was introduced into the standard library is the concept that every STL algorithm must have a pre-specified worst case algorithmic complexity, making it an unimportant matter who implements the STL. One only has to pay attention to the specification of a STL container or algorithm, historically hosted on the SGI website among other sources. This was fairly important in the prehistoric times when everybody can come up with their own containers with different computational complexities.

Other important STL features introduced into the standard library include the new paradigm of functional programming as embodied in the present <algorithm> and everywhere else, which in my opinion, revitalized C++ as a language by complementing the traditional Object Oriented Programming paradigm.

In that sense and back to your question, I think it's only fair to say that the containers like vector belong to STL (originally) and the standard library.

Community
  • 1
  • 1
thor
  • 21,418
  • 31
  • 87
  • 173
  • Nope - the STL was anything but the core. It was a late addition, pushing the first standard back approximately 2 years (1996->1998). Also, the Standard had to precisely document how the STL components **should** work, to allow alternative implementations. – MSalters Jul 29 '15 at 09:30
  • STL pushing back the standard? That's a strange way of looking at it. If the STL containers, algorithms and the associated specification for algorithmic complexity wasn't core material, why did the standardization spend approx. two years to incorporate it? Also, was the two year spent more towards improving STL or on the negotiation whether the then-new features in STL was too much for c++? – thor Jul 29 '15 at 16:55
  • STL came with the specifications of complexity and had alternative implementations prior to being incorporated into the standard. – thor Jul 29 '15 at 16:57
2

In the early 90's there were no collection libraries in C++. People either used RogueWave, Booch components or something else I forget the name of. That's why you see classes like QList in QT, because they needed something.

At that time, SGI had a collection library that many on the standards committee saw and really liked. They based the collection library that many people many were requesting and called that STL.

As of today I would say a library component where the user has explicitly instantiate it is part of the STL. To clarify, you as the user of std::vector have to specify what it contains ie std::vector (1) this means that it is part of the STL. OTOH you do not have to instantiate fstream even though it is a typedef of something like basic_fstream.

As for efficiency, the STL is very lean and mean, thanks to the writers who are experts at things like specialization and TMP. Could I write something that better suits my purpose. I could take a month write something that works 1% better for my needs, but is it worth it?

BTW except for OS calls and C calls, the whole C++ library is templated, though ( like fstream ) you may never see it. So they are banning most of the C++ library.

(1) BTW I think the STL approach was the best one. Other collections required you to do things like derive from a base class Collectible or something like that.

TLOlczyk
  • 443
  • 3
  • 11
  • Stepanov and Lee were at HP when they developed the STL. [Source](https://www.sgi.com/tech/stl/drdobbs-interview.html) – MSalters Jul 29 '15 at 09:34
0

Thank you for all replies to my question. Some of own understanding on this problem: 1. When you are required to develop without STL or any other template library, you can only use library like ,,. You can only use pointer, string(maybe only char) and class in your program, which means you need to define your own data structure. 2. The purpose of not using STL is to test your understanding on basic c++ operation like new/delete, pointer, and class. Also another purpose I am thinking is to save memory. I faced this problem during an interview. I hope it would help you if you are facing the same case I faced before.

leon
  • 73
  • 2