STL: few exceptions #no virtual

side note — virtual function is also very rare in STL classes. I don’t know any.


STL functions seldom throw exception. See P 248 [[c++standard library]]

  1. at() method of vector/string/map… throws, since it’s the “checked” version of the subscript operator
  2. reserve() method throws

Besides these two unusual functions, STL would only throw the standard low-level exceptions like memory allocation failures. All other error conditions are undefined-behavior, such as

  • top()/pop() on priority queue
  • std::string operator[index] with invalid index

However, Payload data types going into STL container can create exceptions:

  • If a payload class ctor/assignment throws, then it would propagate.
  • Payload destructors should never throw. [[c++coding standard]] says it’s forbidden by STL standard.

Containers are what people want; algo/adapters/functors are "accessories"

Most developers come to the “STL supermarket” looking for containers to complement the basic array container. They like a container and use it, and soon realize they must return to the supermarket and pick the associated algo/iterator etc. Many developers find it hard to avoid the STL algorithms. Many feel in their project STL algorithms are avoidable if they write their own home-grown functions access the containers. Iterators, however, are more necessary.

Functors are somewhat arcane to those from C or non-STL environments, but functors were created out of practical necessity.
Adapters (container adapter, iterator adapters, functor adapters.) are also fairly necessary. See http://bigblog.tanbin.com/2009/11/adapters-for-stl-1-container-2-iterator.html
So you entered the supermarket looking for containers, but to work with containers you came back to supermarket for supplementary tools, which are not “free” — all require a bit of learning.

select2perform/brain-bench c++ Q&A

Q: vector1.erase(remove(vector1.rbegin(),vector.rend(),someValue).base())

Q: To put 5 identical values into a vector,
std::fill_n() ?
std::fill() ?
Q: If class E virtually extends C and extends D, where C/D both virtually extend B, what’s the construction sequence?
AA: P1000 [[primer]]

Q: find intersection of 2 compatible vectors?
%%A: std::find_first_of()
Q: can you pass a float into a func(int) or func(char)?
AA: yes but if you cout in func(), it interprets and prints the object differently.
Q: can a non-static reference field be initialized upon declaration?
%%A: i don’t think so, reference field or nonref. The java-style quick initi is illegal for non-static.
AA: gcc allows java-style init only for a static AND const field.

Q: can you “extern” a prototype and then declare the same prototype again?
AA: legal

Q[u]:difference between “new Account” and “new Account()” with the parentheses?
A: subtle difference. See other posts on this blog such as http://bigblog.tanbin.com/2012/07/default-initializevalue-initialize-new.html

Q[u]: declare a pointer to a method accepting an int and returning void. Need to memorize the exact syntax
AA: void (Dog::*ptr2method) (int);

Q: my ex spec mentions std::runtime_error. Can I throw a range_error, or an std::exception, or std::invalid_argument?
AA:

 exception
runtime_error
range_error
exception
logic_error
invalid_argument

Q: reverse print a string using copy to cout
AA: copy(str.rbegin(), str.rend(), ostream_iterator< char >(cout, ” “));
* The ” ” 2nd argument is not necessary, but I’d suggest we memorize just a single form of the ostream_iterator ctor, the 2-arg form.
* The type is char not  ptr-to-char

Q: using N1::f; f(); using N2::f; f();
AA: GCC complains 2nd all to f() is ambiguous. http://www.cplusplus.com/doc/tutorial/namespaces/ explains 

Q[u]: multiple inheritance dreaded diamond – what if one of the 2 “virtual” keywords is omitted? How many times will you call the base constructor?
AA: http://bigblog.tanbin.com/2010/07/virtual-inheritance-diamond-malformed.html

Q[u]: anything wrong with
Base & var = static_cast(*(new Derived));
AA: legal in gcc.

[u = unimportant/trivial/unlikely to be issue in practice. Often compiler will inform you clearly.]

STL is C-developer friendly

P235 [[STL Tutorial and reference guide]] points out that STL uses no polymorphism and almost no inheritance. Apparently, STL is OO-lite. As stated elsewhere on this blog, STL achieves its flexibility, extensibility, power and coherence via templates.

I feel C developers would find STL easy to use.

They would find STL easy to Understand if they learn templates.

STL algo – iterators always; containers never

ObjectSpace STL manual said “stl algorithms only access data via
iterators”. I don't know if this is 100% true today, but STL creators
indeed designed their algorithms to be container-agnostic.

STL was designed as, first and foremost, building-block data structures
known as containers. Essential operations on containers are provided in
2 forms

– methods of the container classes (class templates actually). These are
“trusted” members and therefore can modify container content.
– container-agnostic free-functions known as STL algorithms

The link between the algorithms and containers is the iterator.

some Design questions at my interviews

Q: when you start a green field project and multi-threading is required, what are the key points you keep in mind about multi-threading.
A (my Answer): keep things really simple. For example, immutables; fewer locks; less granular locks;
A (now i think): have an idea where MT can really help and where it has marginal impact. In many cases ST works better, without any data races or locks.
A: It’s also possible to go for multi-processing instead of MT — lower risk (fewer MT hazards); simpler; better-understood
A: sometimes it makes sense to leverage on existing MT features in a database such as running code in the DB

Q: in your sybase/java/perl system at GS, what are the performance bottlenecks? How did you address them?
A: DB query.

Q (MS): how do you define scalability, in your specific contexts?
%%A: generically, it means nearly linear throughput improvement without code change.

Q: what strengths/complaints do you know about C++ STL?
A (my Answer): STL is more powerful than anything before or after it, but too complex. For example, I can have a vector of reference to pointer to pointer to int. No such thing allowed in java.
A(my Answer): STL debugging is harder
A (now i think): not much OO, but heavy usage of templates. Some people like/dislike it
A (now i think): thread-safety is minimal
A (now I think): storing pointers in containers is widely required but not well-supported without smart pointers.
A (now I think): storying interface or base types is widely required in Java but similar situation as above
A: performance very good.

Q(BGC): key differences between Perl and c++?

allocator,less,vptr — (template|class|insance)-level

Case 1) First, let’s look at a similar situation — the vtbl is at the CLASS-level, not the instance-level. Each CLASS in the inheritance hierarchy has a vtbl, and each INSTANCE’s real-estate has 32-bit for a vptr seated to this vtbl.

Case 2) Let’s turn to allocators. Look at template declaration of vector.

Q: Why is allocator a template parameter and not a constructor parameter?
A:
* each concretized vector *class* probably has a pointer to an allocator — your custom allocator.
* each vector *instance* probably has fields for the size, the capacity etc. However, the allocator is shared by all the instances of the concrete class.

Q2: Can we make the allocator a static field?
A2: No. I feel allocator is “one allocator per template specialization”, but for a static field it’s “one object across ALL template specializationSSS”.

In this story we see various utility objects belonging to 3 levels of abstraction
* feature common for a generic, unconcretized template, across all concretized classes.
* feature unique to a particular concretized class
* feature unique to an instance of the class

The per-concretized-class level is the most abstract, so here’s another concrete example —
Case 3) The element comparison function is another “thing” at the class level. For a sorted map, each “concrete type-argument” (that you plug into the template) has its own comparator. (Java has a clean solution, but) In STL, a concrete comparator is supplied at the class level, and can’t be at the generic template level as a static field. When I concretize the map for Account objects, i choose a concrete comparator for my concretized class.

bind2nd/bind1st is used like a cvctor


find_if ( &array[0], &array[2],
bind2nd(greater(), 55)

If you have trouble making out the objects in such a call to bind2nd,
here’s a simple rule

bind2nd always takes objects and instantiate another object, not a type

It’s like a converter constructor, but bind2nd is actually a function template.

In our example,

* greater() is an Object, not a type, not a function
* find_if needs an Object (not a type) as argument

adapters for STL 1) container 2) iterator and 3) functor

You know the STL planet has (at least) 3 continents — containers + iterators + algorithm. Now, most of these have adapters.
1) Container adapter? Obvious!
2) iterator adapter? simplest example is back_inserter.
(How about reverse_iterator? I think so.)

3) functor adapter? simplest example is bind1st() and bind2nd()
The adapter not2() is actually quite simple but understand not1() first.

4) algorithms? I don’t think algorithms have adapters because
…algorithms aren’t objects!

5) allocators? I don’t think so.

STL allocators – good book

Never quizzed….

The ebook [[c++ in a nutshell]] sections on header files and on Allocator. Many simple Allocator implementations and usage scenarios. Looking at the code, i realize the allocator idea started as a way to “abstract out” the allocation/deallocation job duty traditional performed by new/delete.

So there are 2 standard, approved techniques to “mess with” new/delete —
1) customize them for your class and, by the way, have them inherited by subclasses
2) allocators
(In some cases like some items of the original [[EffC++]], these techniques are kind of combined. But It’s good to have a mental divide between the 2 techniques.)

STL containers do NOT directly call new/delete. They all use allocators, which often calls new/delete internally.

The ebook also says allocators can implement debugging or validity checks to detect programmer errors such as memory leaks or double frees. That’s because allocators, like customized op-new, intercept every memory allocation request from /host-application/.

ptr_fun – use a 2-arg template function in std::for_each

//Real code in my project

typedef hash_map HM; // reduces complexity of bind2nd(ptr_fun(update_map)…

int const ar[10] = { 1, 2, 3, 4, 55, 55, 4 };

template
void update_map(int aInt, M map) {
  map[aInt]++; //compiler can’t check if operator[] is defined for the type M until template instantiation
}

template
void build_map(M const & arg_map) {

  //for_each needs single-arg function. To convert our 2-arg function, we use bind2nd + ptr_fun
  for_each(ar, ar + 10, bind2nd(ptr_fun(update_map), map));
}

pair^unary functor^Property pattern..all use2dummy-types

STL’s pair template has 2 “dummy types” — K/V. Pair template is useful by itself, without the map.

By comparison, the STL unary (no comments on “binary”) func template also has 2 dummy types A/R, standing for Argument/Result.

The popular Property pattern (D Duffy) also features 2 dummy types K and V. Many features are added — very adaptable.

The name/value pairs are very natural on a spreadsheet.

Warning — some programmers give longer names to these dummy types — “key/value”. They want to add clarity, but actually add confusion. These dummy type names look like class names or typedef names esp. in a long source listing. Unfortunately c++ class names and typedefs don’t start with Capital Letters.

Boost Tuple generalizes the pair concept.

This “pair” concept is very simple, practical and adaptable.

STL creators’ design priority

Simplicity and ease of use was a low priority for the STL creators. Efficiency is perhaps #1 design priority. Both time cost and space cost. I guess STL was designed to be usable in telecom and other real time small equipment with limited memory and CPU resources.

Whenever people optimize for efficiency, they *specialize* their components for various scenarios. I think that explains the proliferation of iterators. Also, many algorithms overlap, as methods and as free functions.

Template itself was invented for efficiency, at the cost of simplicity. STL exemplifies template usage. Efficiency in terms of code reuse and algorithm abstraction.

The father of STL doesn’t believe in OO. Any OO design in STL? STL was designed just like C (without classes) — for maximum algorithm efficiency and maximum abstraction. Classes and templates were employed as a means to that end.

operator-overload used to the max in STL

I feel STL uses op overloading whenever it makes sense. When a container has a bunch of operators and a bunch of methods, the former is always more important than the latter. Iterators have operators only.

[] // vectors, deque, map yes map, but not list or queue due to random-access
++ // forward iterators
— // bidirection iterators
== != // iterator,
>= // map+set (sorted), list, queue, stack, vector
q( * ) deference // iterator. Note that we don’t use ->. It’s not overloaded in the Iterator class.

Note q( >= ) is overloaded “provided” we have already overloaded > < != == etc.

custom allocator usage

Some container classes have custom allocators, because the default allocator (allocator) leads to memory fragmentation. — tip from Wang, c++ veteran in Nomura.

Custom allocators can also increase “locality of reference”, to allow hardware to exploit locality of reference.

Overall, custom allocators are an optimization technique.

[[STL tutorial]] has a small example