By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
445,797 Members | 1,794 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 445,797 IT Pros & Developers. It's quick & easy.

Source files for buildt-in containers in std?

P: n/a
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?
Jun 8 '07 #1
Share this Question
Share on Google+
10 Replies


P: n/a
desktop wrote:
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

--
Got two Dear-Daniel-Instant Messages
by MSN, associate ICQ with stress --
so please use good, old E-MAIL!
Jun 8 '07 #2

P: n/a
On Jun 8, 11:10 am, desktop <f...@sss.comwrote:
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.

--
James Kanze (GABI Software) email:ja*********@gmail.com
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

Jun 8 '07 #3

P: n/a
James Kanze wrote:
On Jun 8, 11:10 am, desktop <f...@sss.comwrote:
>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.

--
James Kanze (GABI Software) email:ja*********@gmail.com
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++.
Jun 8 '07 #4

P: n/a
On 2007-06-08 16:36, desktop wrote:
James Kanze wrote:
>On Jun 8, 11:10 am, desktop <f...@sss.comwrote:
>>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.

--
James Kanze (GABI Software) email:ja*********@gmail.com
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 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 <mapin a project then right-click on <mapand
select Open Document <map>, then repeat for <xtree>.

Or you can probably find the SGI implementation with some googling.
I have tried to find a folder called g++ but I only have some binaries
starting with g++.
The folder is probably called libstdc++.

--
Erik Wikström
Jun 8 '07 #5

P: n/a
Erik Wikström wrote:
On 2007-06-08 16:36, desktop wrote:
>James Kanze wrote:
>>On Jun 8, 11:10 am, desktop <f...@sss.comwrote:
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.

--
James Kanze (GABI Software) email:ja*********@gmail.com
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 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 <mapin a project then right-click on <mapand
select Open Document <map>, then repeat for <xtree>.

Or you can probably find the SGI implementation with some googling.
>I have tried to find a folder called g++ but I only have some binaries
starting with g++.

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.
Jun 8 '07 #6

P: n/a
desktop <ff*@sss.comwrote:
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/200402090...h/c-predef.htm

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

--
Marcus Kwok
Replace 'invalid' with 'net' to reply
Jun 8 '07 #7

P: n/a
Marcus Kwok wrote:
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.
Jun 8 '07 #8

P: n/a
On Jun 8, 4:36 pm, desktop <f...@sss.comwrote:
James Kanze wrote:
On Jun 8, 11:10 am, desktop <f...@sss.comwrote:
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.
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 (Gabi Software) email: ja*********@gmail.com
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

Jun 8 '07 #9

P: n/a
On Jun 8, 6:58 pm, desktop <f...@sss.comwrote:
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.
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.

--
James Kanze (Gabi Software) email: ja*********@gmail.com
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
Jun 8 '07 #10

P: n/a
red floyd <no*****@here.dudewrote:
Marcus Kwok wrote:
>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))

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".

--
Marcus Kwok
Replace 'invalid' with 'net' to reply
Jun 11 '07 #11

This discussion thread is closed

Replies have been disabled for this discussion.