Different treatment of the NodeType of LinkedList in C++ and Java

[yangsuli]

Hi, everybody;

I am a student who is taking the data structure course. When we are
learning the data structure LinkedList, I noticed that Java and C++
treated the type of the node of Linkedlist differently.

In STL, C++ actually publishes the typed of list_node:
class List{
protected:
typedef __list_node<T> list_node:
.....
}

But in Java, the class of LinkedListNode has package access, so the
user of LinkedList won't even see this node type.

Personally, I wound think the type of node is the implementation
detail, and the best practice is to hide it from the user.But I am
posting this message to see, is there any particular reason that C++
choose to publish the list_node type? Does this has something to do
with the difference in this two languages?

Any answer would be appreciated!

Thank you very much!

 

[peter koch]

Hi, everybody;

I am a student who is taking the data structure course. When we are
learning the data structure LinkedList, I noticed that Java and C++
treated  the type of the node of Linkedlist differently.

In STL, C++ actually publishes the typed of list_node:

Nit: I assume you mean the standard C++ library. STL is a nonstandard
library probably not used very much anymore.

class List{
protected:
typedef __list_node<T> list_node:
....

}

No it does not. I don't know where you got the above from, but it is
not part of the standard library. For one difference, the name is
(std:list, not List.

But in Java, the class of LinkedListNode has package access, so the
user of LinkedList won't even see this node type.

Personally, I wound think the type of node is the implementation
detail, and the best practice is to hide it from the user.But I am
posting this message to see, is there any particular reason that C++
choose to publish the list_node type? Does this has something to do
with the difference in this two languages?

std::list "publishes" the name of the template type so that you can
use it in case your own code is templated. I very much doubt that any
implementation would publish the internal nodetype.

/Peter

 

[Dave Searles]

Nit: I assume you mean the standard C++ library. STL is a nonstandard
library probably not used very much anymore.

STL isn't nonstandard according to the Word of God (Stroustrup's The C++
Programming Language).

 

[James Kanze]

I am a student who is taking the data structure course. When
we are learning the data structure LinkedList, I noticed that
Java and C++ treated the type of the node of Linkedlist
differently.

In STL, C++ actually publishes the typed of list_node:
class List{
protected:
typedef __list_node<T> list_node:
....
}

I suppose you miscopied something, since the name of the class
in the standard is list, not List. And the "exposition" of the
node type is probably due to some techical implementation issue;
it's not officially exposed, as part of the documented interface
in the standard.

But in Java, the class of LinkedListNode has package access,
so the user of LinkedList won't even see this node type.

Package access is less protective than protected access in C++
(or in Java). With protected access, the only way to access the
name is to derive from the class. With package access, you can
either derive from the class, or declare another class as a
member of the same package.

Personally, I wound think the type of node is the
implementation detail, and the best practice is to hide it
from the user.

Agreed. On the other hand, there can be technical reasons for
exposing it, partially or completely: in my pre-standard
DLListOf, it was fully private, but in my pre-standard
AssocArrayOf, the node base type was a protected member of the
(non-templated) base class.

But I am posting this message to see, is there any particular
reason that C++ choose to publish the list_node type?

C++ doesn't publish it, or even require it to exist (although I
don't see how you could implement std::list without it).

Does this has something to do with the difference in this two
languages?

I don't really think so. I don't really see why it isn't
private in both cases, but I suspect that there are some
technical issues involved. (In the case of Java, it might be
protected or package in order to facilitate the implementation
of some more strongly typed derived class. In the case of C++,
I don't see any real reason.)

 

[James Kanze]

STL isn't nonstandard according to the Word of God
(Stroustrup's The C++ Programming Language).

STL means different things to different people. The acronym
stands for "Standard Template Library"; Stepanov chose it before
there was a standard C++ library. In current use, it can mean
Stepanov's original library (without the changes introduced by
the standard, but with some parts not adopted by the standard),
the parts of the C++ standard library derived from Stepanov's
work, or simply the C++ standard library.

In this case, the fact that the "exposed" name begins with two
underscores is a strong indication that it is strictly part of
the implementation, or perhaps an extension, but is not part of
the standard.

 

[peter koch]

STL isn't nonstandard according to the Word of God (Stroustrup's The C++
Programming Language).

That book predates the C++ standard. A lot of the STL from those days
was incorporated into the standard library, but not all (rope, hashed
maps).
I know that most people call part of the C++ standard library STL, but
the term is not correct.

/Peter

 

[Lew]

Package access is less protective than protected access in C++
(or in Java). With protected access, the only way to access the
name is to derive from the class. With package access, you can
either derive from the class, or declare another class as a
member of the same package.

That is not correct for Java; in fact, it's exactly backwards.

In Java, "package-private", or default access means only accessible from
within the same package, as the word implies. 'protected' access is a
superset of that; members are available to subclasses even in different
packages, as well as to classes in the same package. A class cannot access
package-private members of one of its superclasses in a different package.

<http://java.sun.com/docs/books/tutorial/java/javaOO/accesscontrol.html>

That chart does not make clear that package-private members can be inherited
by a subclass in the same package, but it's so. (It's not so for private
members, not even for extending inner classes.)

 

[yangsuli]

I suppose you miscopied something, since the name of the class
in the standard is list, not List. And the "exposition" of the
node type is probably due to some techical implementation issue;
it's not officially exposed, as part of the documented interface
in the standard.


Package access is less protective than protected access in C++
(or in Java). With protected access, the only way to access the
name is to derive from the class. With package access, you can
either derive from the class, or declare another class as a
member of the same package.


Agreed. On the other hand, there can be technical reasons for
exposing it, partially or completely: in my pre-standard
DLListOf, it was fully private, but in my pre-standard
AssocArrayOf, the node base type was a protected member of the
(non-templated) base class.


C++ doesn't publish it, or even require it to exist (although I
don't see how you could implement std::list without it).


I don't really think so. I don't really see why it isn't
private in both cases, but I suspect that there are some
technical issues involved. (In the case of Java, it might be
protected or package in order to facilitate the implementation
of some more strongly typed derived class. In the case of C++,
I don't see any real reason.)

I think I should clearify somethings:

1. I copied the code from the book "the annotated STL source (using
SGI STL)". Now I realied that it may just be a particular
implementation of STL, but not a standard requirment in the STL
standard. But I am still curious about why it is so.

2. Yes, it could be a techinical issue. But I am asking this question
because I don't know a mechanism in C++ that can prevents the user
from using a particular type.(say, a user had a veriable of
__list_node type. It does not make too much sense, but he or she has
the ability to do this). On the other hand, by making listnode class
package access in Java, one can never do such a thing. The type
itsself has been hided. I am just wondering, can we do this in C++?

3. Sure it can not be private! Actually, what do you mean by making a
type(class) private?

Thank you all by answering my question.

Yang Suli

 

[James Kanze]

On 10ÔÂ29ÈÕ, ÉÏÎç5ʱ18·Ö, James Kanze <[email protected]> wrote:

[...]

I think I should clearify somethings:

[...]

2. Yes, it could be a techinical issue. But I am asking this
question because I don't know a mechanism in C++ that can
prevents the user from using a particular type.(say, a user
had a veriable of __list_node type. It does not make too much
sense, but he or she has the ability to do this). On the other
hand, by making listnode class package access in Java, one can
never do such a thing. The type itsself has been hided. I am
just wondering, can we do this in C++?

In both Java and C++, you can very easily make the type private,
so that it cannot be seen (Java) or accessed (C++) from any
other class.

3. Sure it can not be private! Actually, what do you mean by making a
type(class) private?

Exactly what you mean by making anything else private. If
something is declared private: in Java, it is invisible outside
of the class; in C++, it's name cannot be used outside of the
class. For something like a double linked list of int, for
example:

class IntList
{
private:
struct Node
{
Node* next;
Node* prev;
int value;
};

Node* root;

public:
// ...
};

The type Node cannot be accessed outside of IntList.

 

[Mike Schilling]

STL means different things to different people. The acronym
stands for "Standard Template Library"; Stepanov chose it before
there was a standard C++ library. In current use, it can mean
Stepanov's original library (without the changes introduced by
the standard, but with some parts not adopted by the standard),
the parts of the C++ standard library derived from Stepanov's
work, or simply the C++ standard library.

That is "STL" may means the standard, part of the standard, or
something non-standard. And people think C++ is complicated!