C Balanced Binary Tree vs C++ std::map perfomance

Question

Having a discussion with some experienced developers about containers in C++, they told me that for better performance, instead of using std::map, they just use a classic C binary tree. Since an std::map is implemented as a binary tree, is there a reason why a user implemented C style binary tree, can be faster than an std::map?

Did they back up their claims by actual performance measurements? — user7860670, Jun 24 '18 at 07:19
*Since an std::map is implemented as a binary tree* -- It is implemented *usually* as a [red-black tree](https://stackoverflow.com/questions/5288320/why-is-stdmap-implemented-as-a-red-black-tree) — PaulMcKenzie, Jun 24 '18 at 07:19
Related video: [CppCon 2016: Dan Saks “extern c: Talking to C Programmers about C++”](https://youtu.be/D7Sd8A6_fYU). — user7860670, Jun 24 '18 at 07:25
Also "premature optimization is the root of all evil". I would never, ever trade a C++ class (especially a std class) for a C library without doing intensive performance measurements first. The answer "Use this, because it's faster." is a pretty dangerous claim. You want to use what's best for your use-case. If your 'map' usage takes up only 0.5% of your CPU cycles at runtime, why bother replacing it with something else, especially if you throw away all the benefits you get from C++ and a std lib. (Also I don't think a classic C binary tree really is faster). — Hajo Kirchhoff, Jun 24 '18 at 07:38
@Hajo Kirchhoff. They team is making a fully professional code and after tests, they end using for some purposes C trees instead of std::map, for a part of the code the really matters about the speed of the whole procedure. — dkmg, Jun 24 '18 at 08:59
@dkmg -- So what your programmers are doing is writing a "pure" binary tree class, and *not* a `std::map` clone, i.e. you're comparing apples to oranges. In C++, there are *no* binary tree classes that are standard, thus even a C++ programmer would have to write their own binary tree implementation, as none exists in STL. — PaulMcKenzie, Jun 24 '18 at 17:54

John Zwinck · Answer 1 · 2018-06-24T07:58:48.850

One reason why std::map can be less efficient than some tree implementations in C is that it is not "intrusive."

An intrusive container is where bookkeeping information is stored directly in the values. For example, a binary tree in C might be based on this type:

struct node {
    node *left, *right;
    int key;
    int value;
};

Whereas in C++ it would be:

std::map<int, int>

The difference is that when you insert a key/value pair into the C++ map, the map allocates memory to hold the node then copies the key/value pair into it. In C, a node can be allocated once and then inserted into a tree without further allocation or copying.

Boost Intrusive implements several intrusive containers in C++, with a main goal being performance parity with the "C style" data structures. There is no map, but there is boost::intrusive::set, which can be used instead (by making the value_type hold both the key and the value from the map).

C++17 added std::map::insert(node_type&&) which allows inserting a node without copying the key and value. But the only way to obtain a node_type value is by using std::map::extract(key). You can't allocate a node outside of a container (with C or Boost Intrusive, you can).

C Balanced Binary Tree vs C++ std::map perfomance

1 Answers1