Linked lists in C/C++

[red floyd]

Hello guys,
I just have a quick question about C++. I am moving from Java to C++. And as
many of Java users know, all linked list and trees are already implemented
and you just have to instantiate them. Is tehre a simiar thing in c++, or I
have to write my own Linked list class?

Thank you very much
Cheers

The Standard Library has many containers, including vectors, deques,
lists, sets, and maps. I'm not sure if there's a stock "tree" class
(though sets and maps tend to be implemented as a red/black tree).

Get a copy of Josuttis' "The C++ Standard Library". Also, get
Koenig&Moo's "Accelerated C++".

 

[Gianni Mariani]

Hello guys,
I just have a quick question about C++. I am moving from Java to C++. And as
many of Java users know, all linked list and trees are already implemented
and you just have to instantiate them. Is tehre a simiar thing in c++, or I
have to write my own Linked list class?

Just to add to Red's note, there are a number of web sites that have
documentation.

Even though it's a little out of date, I still find it the most useful
on-line reference:
http://www.sgi.com/tech/stl/

There are plenty of others :
http://www.codeproject.com/vcpp/stl/stlintroduction.asp

Many on-line examples have a ".h" in the include file. These are wrong.

 

[hana1]

Hello guys,
I just have a quick question about C++. I am moving from Java to C++. And as
many of Java users know, all linked list and trees are already implemented
and you just have to instantiate them. Is tehre a simiar thing in c++, or I
have to write my own Linked list class?

Thank you very much
Cheers

 

[Jonathan Bartlett]

I just have a quick question about C++. I am moving from Java to C++. And as

many of Java users know, all linked list and trees are already implemented
and you just have to instantiate them. Is tehre a simiar thing in c++, or I
have to write my own Linked list class?

In C++ the STL defines list (a doubly-linked list) and slist (a
singly-linked list). See here:

http://www.sgi.com/tech/stl/List.html
http://www.sgi.com/tech/stl/Slist.html

One thing, though, is that C/C++ only support homogenous lists -- i.e.
only one data type in each list, unless you are storing pointers instead
of values.

However, you can do more advanced type of stuff if you write your own,
like sharing list nodes and other fun stuff. See my article on linked
lists here:

http://www.ibm.com/developerworks/linux/library/l-listproc/

Also, coming from Java, if you decide that you miss garbage collection,
you can always add it back using the Boehm garbage collector.

http://www.hpl.hp.com/personal/Hans_Boehm/gc/

Jon

 

[Mike Wahler]

In C++ the STL defines list (a doubly-linked list) and slist (a
singly-linked list).

'slist' is not a standard container.

See here:

http://www.sgi.com/tech/stl/List.html
http://www.sgi.com/tech/stl/Slist.html

One thing, though, is that C/C++ only support homogenous lists -- i.e.
only one data type in each list, unless you are storing pointers instead
of values.

And those pointers all have the same type -- still homogenous.

-Mike

 

[Gernot Frisch]

Hello guys,
I just have a quick question about C++. I am moving from Java to
C++. And as many of Java users know, all linked list and trees are
already implemented and you just have to instantiate them. Is tehre
a simiar thing in c++, or I have to write my own Linked list class?

Thank you very much
Cheers

If you need trees, you can use something like:

namespace std
{
template <class Alloc> class tree : public Alloc
{
public:
Alloc& childs() {return m_Childs;}
const Alloc& childs() const {return m_Childs;}
private:
Alloc m_Childs;
};
}

std::tree< std::map<std::string, std::string> > MyTree;

 

[Alf P. Steinbach]

* Gernot Frisch:

If you need trees, you can use something like:

namespace std
{
template <class Alloc> class tree : public Alloc

The standard forbids placing anything new in namespace 'std'.

It's only used as a non-portable hack for tweaking certain compilers
into standard-conformance.

 

[Gernot Frisch]

* Gernot Frisch:

The standard forbids placing anything new in namespace 'std'.

It's only used as a non-portable hack for tweaking certain compilers
into standard-conformance.

Sorry, didn't know that.
-Gernot

 

[Jerry Coffin]

[ ... ]

The standard forbids placing anything new in namespace 'std'.

This is is simply not true at all. See $17.4.3.1 of the standard for
the details, but the bottom line is that while there are restrictions,
it's entirely legitimate to add some things to namespace std.

It's only used as a non-portable hack for tweaking certain compilers
into standard-conformance.

That's not true either -- the permissions are there in the standard
because some things really can't be done any other way.

 

[Alf P. Steinbach]

* Jerry Coffin:

[ ... ]

The standard forbids placing anything new in namespace 'std'.

This is is simply not true at all. See $17.4.3.1 of the standard for
the details, but the bottom line is that while there are restrictions,
it's entirely legitimate to add some things to namespace std.

The some things can not be new things, only specializations of existing
standard templates. std::tree, the class under discussion, is an
entirely new thing, and the effect of adding it to namespace std is
Undefined Behavior. In other words, you're wrong; what you write is
simply not true at all (under any sensible interpretation). ;-)

That's not true either -- the permissions are there in the standard
because some things really can't be done any other way.

It is not permitted to place anything new in namespace std. At most
you can place specializations of existing standard template classes.
So what you write here is not true either, sorry.

Cheers,

- Alf

 

[Jerry Coffin]

[ ... ]

The some things can not be new things, only specializations of existing
standard templates. std::tree, the class under discussion, is an
entirely new thing, and the effect of adding it to namespace std is
Undefined Behavior. In other words, you're wrong; what you write is
simply not true at all (under any sensible interpretation). ;-)

So by your interpretation, it's sensible to call a new specialization,
"not new"?

 

[Alf P. Steinbach]

* Jerry Coffin:

[ ... ]

The some things can not be new things, only specializations of existing
standard templates. std::tree, the class under discussion, is an
entirely new thing, and the effect of adding it to namespace std is
Undefined Behavior. In other words, you're wrong; what you write is
simply not true at all (under any sensible interpretation). ;-)

So by your interpretation, it's sensible to call a new specialization,
"not new"?

What we have here is not a specialization, it's a derived class.

I don't think it's sensible to call a specialization "new" except in the
time sense perhaps.

And of course the rules of the language are not concerned with when
something was made (classes derived from std::youghurt must have been
originally created no earlier than january 2005) -- so in this context
the pure time sense of "new" seems to be ruled out.


Cheers, again,

- Alf