Trying to identify a Binary-Search-Tree structure

Question

Let's say I make a std::map in C++, and ADDR is their address in memory. When I look at this place in memory I will find a pointer and in ADDR + 4 will be the amount of elements in the container. Now, when I go to [ADDR], I will find 3 more Pointers, the first points to the left most element of the Tree, the second to the Root of the Tree, and the third to the right most element of the Tree. Now here is my question:

When I make a std::map<int, int>, and and I go to a Node ( let's take the Root for example ),I will have the it->first in the Node+0x10 and it->second in Node+0x14, but I found a Tree in a software which has the it->first in the Node+0xC and it->second in Node+0x10, and I just can't discover which structure this is. Someone here has any idea what this can be?

Example if I make a std::map<std::string, int>:

Here it is the struct I want to identify:

PS: This software is developed in C++.

Answer 1

In the comment to your original question, I mentioned that it might be a boost::fusion::map, and asked whether there were two bool values at +0x14 and +0x15. You then updated your post with an image showing bool-looking values at those locations.

I think my original guess was correct. It seems to be a boost::fusion::container::map. For MSVC's STL implementation, the definition of _Tree_node<T> has been the same for decades:

// Simplified version of MSVC's xtree _Tree_node<T>
template <typename T>
struct _Tree_node {
  _Tree_node *_Left;   // Pointers to neighbors
  _Tree_node *_Parent;
  _Tree_node *_Right;
  bool _Color;         // Red-Black tree stuff
  bool _Isnil;
  T _Myval;            // Node value. For map<K,V>, this is a pair<K,V>. 
                       // For set<T>, this is just a T.
};

This is what I see 100% of the time when reverse engineering MSVC code with std::set or std::map, and you can see the real implementation for yourself on the Microsoft STL GitHub repository for xtree.

When I reverse engineer boost programs, I notice that the data structure is virtually identical to the MSVC STL, except that the T data comes before the two bool values. It looks like this instead:

// Replica of boost tree nodes
template <typename T>
struct _Tree_node {
  _Tree_node *_Left;   // Same as before
  _Tree_node *_Parent;
  _Tree_node *_Right;
  T _Myval;            // Data. In MSVC, is after booleans.
  bool _Color;         // Booleans. In MSVC, is before data.
  bool _Isnil;
};

I would link directly to the boost repository showing the comparable class definition, but I have actually never been able to locate it, despite having spent 30+ minutes trying to do so. (If you thought the MSVC STL code was hard to read, try reading boost.)