Source files for buildt-in containers in std?

[desktop]

I have found the stl_tree.h for a red-black tree in:
/usr/include/c++/4.1.2/bits

But where is the .cpp source file located or are all the implementation
located in the .h file?

 

[James Kanze]

I have found the stl_tree.h for a red-black tree in:
/usr/include/c++/4.1.2/bits

But where is the .cpp source file located or are all the
implementation located in the .h file?

Who knows? It's up to the implementation. The path you give
suggests g++, in which case, there's probably a file .tcc
somewhere in the bits directory, with the actual implementation.
With a good compiler, however, one that implements export, it's
not even certain that the implementation is present on the
machine. And every implementation has its own strategy for
handling this when the compiler doesn't implement export. But
about the only time any of this is relevant is when you're
debugging the library yourself.

 

[Daniel Kraft]

I have found the stl_tree.h for a red-black tree in:
/usr/include/c++/4.1.2/bits

But where is the .cpp source file located or are all the implementation
located in the .h file?

I suppose all implementation is in the header, as this is a template
library. But even if there was some implementation, it would only be in
the source-folder (e.g., somewhere in /usr/src) if you installed it from
source.

Otherwise, most probably only the compiled sources (.a/.so) would be there.

Yours,
Daniel

 

[desktop]

Who knows? It's up to the implementation. The path you give
suggests g++, in which case, there's probably a file .tcc
somewhere in the bits directory, with the actual implementation.
With a good compiler, however, one that implements export, it's
not even certain that the implementation is present on the
machine. And every implementation has its own strategy for
handling this when the compiler doesn't implement export. But
about the only time any of this is relevant is when you're
debugging the library yourself.

--
James Kanze (GABI Software) email:[email protected]
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

In the file stl_tree.h the rotate functions are declared:


void
_Rb_tree_rotate_left(_Rb_tree_node_base* const __x,
_Rb_tree_node_base*& __root);

void
_Rb_tree_rotate_right(_Rb_tree_node_base* const __x,
_Rb_tree_node_base*& __root);

void
_Rb_tree_insert_and_rebalance(const bool __insert_left,
_Rb_tree_node_base* __x,
_Rb_tree_node_base* __p,
_Rb_tree_node_base& __header);

But they are not defined. If they are not defined on my machine where
are they defined? The reason I ask is because I have made my own
implementation of a red-black tree and would like to see the
"professional" version.

I have tried to find a folder called g++ but I only have some binaries
starting with g++.

 

[=?ISO-8859-1?Q?Erik_Wikstr=F6m?=]

In the file stl_tree.h the rotate functions are declared:


void
_Rb_tree_rotate_left(_Rb_tree_node_base* const __x,
_Rb_tree_node_base*& __root);

void
_Rb_tree_rotate_right(_Rb_tree_node_base* const __x,
_Rb_tree_node_base*& __root);

void
_Rb_tree_insert_and_rebalance(const bool __insert_left,
_Rb_tree_node_base* __x,
_Rb_tree_node_base* __p,
_Rb_tree_node_base& __header);

But they are not defined. If they are not defined on my machine where
are they defined?

The implementation might be available only in binary form.

> The reason I ask is because I have made my own
implementation of a red-black tree and would like to see the
"professional" version.

If you have access to a windows machine you can download and install
Visual C++ 2005 Express, there you can easily get to the implementation
by writing #include <map> in a project then right-click on <map> and

I have tried to find a folder called g++ but I only have some binaries
starting with g++.

The folder is probably called libstdc++.

 

[desktop]

The implementation might be available only in binary form.


If you have access to a windows machine you can download and install
Visual C++ 2005 Express, there you can easily get to the implementation
by writing #include <map> in a project then right-click on <map> and


The folder is probably called libstdc++.

Thanks found the implementation at:

http://www.sgi.com/tech/stl/download.html

what up with the

__x->_M_right = __y->_M_left;
if (__y->_M_left !=0)
__y->_M_left->_M_parent = __x;
__y->_M_parent = __x->_M_parent;

double underscore "__" syntax by the way, not the prettiest thing I have
seen.

 

[Marcus Kwok]

Thanks found the implementation at:

http://www.sgi.com/tech/stl/download.html

what up with the

__x->_M_right = __y->_M_left;
if (__y->_M_left !=0)
__y->_M_left->_M_parent = __x;
__y->_M_parent = __x->_M_parent;

double underscore "__" syntax by the way, not the prettiest thing I have
seen.

The double underscore in identifiers is reserved for use by the
"implementation", which usually includes the Standard Library. If you
follow the rule of not using double underscores in your own code, then
the chances of a name clash are drastically reduced.

There are other identifiers that are reserved to the implementation as
well (such as identifiers beginning with an underscore followed by a
capital letter (but this may only be in the global namespace)), and
recently I found out about some reserved identifiers inherited from the
C standard (such as ones beginning with 'str' or with a capital 'E').

This page (no longer maintained, so may be a little out of date)
attempts to document them:
http://web.archive.org/web/20040209031039/http://oakroadsystems.com/tech/c-predef.htm

In summary, don't use double underscores in your own code

 

[red floyd]

The double underscore in identifiers is reserved for use by the
"implementation", which usually includes the Standard Library. If you
follow the rule of not using double underscores in your own code, then
the chances of a name clash are drastically reduced.

There are other identifiers that are reserved to the implementation as
well (such as identifiers beginning with an underscore followed by a
capital letter (but this may only be in the global namespace)), and
recently I found out about some reserved identifiers inherited from the
C standard (such as ones beginning with 'str' or with a capital 'E').

No, per 17.4.3.1.2, identifiers with an underscore followed by an
uppercase letter are reserved to the implementation in all scopes.

Identifiers with an underscore, followed by a digit or a lowercase
letter are reserved in the global (and ::std, per foootnote 165)
namespaces.

 

[James Kanze]

In the file stl_tree.h the rotate functions are declared:

void
_Rb_tree_rotate_left(_Rb_tree_node_base* const __x,
_Rb_tree_node_base*& __root);

void
_Rb_tree_rotate_right(_Rb_tree_node_base* const __x,
_Rb_tree_node_base*& __root);

void
_Rb_tree_insert_and_rebalance(const bool __insert_left,
_Rb_tree_node_base* __x,
_Rb_tree_node_base* __p,
_Rb_tree_node_base& __header);

But they are not defined.

They're certainly defined somewhere. As they're not templates,
probably somewhere in the standard library (libstdc++.a or
libstdc++.so for g++ under Linux). The sources are somewhere in
the g++ source tree. (In the version I have, they're in
libstdc++-v3/src/tree.cc.)

If they are not defined on my machine where
are they defined? The reason I ask is because I have made my own
implementation of a red-black tree and would like to see the
"professional" version.

I have tried to find a folder called g++ but I only have some
binaries starting with g++.

I'm not sure what you mean by "folder". The sources should be
under the source tree for gcc, but I can't tell you where (or
even if) that's installed on your system. If worse comes to
worse, you can go to a gcc mirror and download the sources from
there, just as you would do if you were going to build the
compiler yourself. (I do build my own versions of g++, which is
why I have the source tree handy. Where that not the case,
however, I probably wouldn't bother installing it, although it
should be on the same CD as gcc was.)

 

[James Kanze]

Thanks found the implementation at:

what up with the

__x->_M_right = __y->_M_left;
if (__y->_M_left !=0)
__y->_M_left->_M_parent = __x;
__y->_M_parent = __x->_M_parent;

double underscore "__" syntax by the way, not the prettiest
thing I have seen.

It's prettier than what would happen if they dropped it, and
your program happened to start:

#define y 0
#define x 1
#include <map>

You're not allowed to define macros with a double underscore, or
which start with an underscore followed by a capital letter,
which accounts for the naming convention.

 

[Marcus Kwok]

No, per 17.4.3.1.2, identifiers with an underscore followed by an
uppercase letter are reserved to the implementation in all scopes.

Identifiers with an underscore, followed by a digit or a lowercase
letter are reserved in the global (and ::std, per foootnote 165)
namespaces.

Thanks. I can never remember this exception, so I find it easier just
to remember, "don't start identifiers with an underscore, ever".