How is std::deque implemented ?

Deque is sometimes thought of as an dynamic array that is comprised of linked arrays.

typical deque layout

Such a structure could lead to extremely fast insert and remove operations.

Exactly what performance should one expect from a std::deque implementation though?

Generic C-Trees and C++ std::maps

How many lines of code do I need, to set up a typical tree structure? What are the pros and cons between a C-style generic tree and an std::map or an std::set ?