In article <4nmnab$llt@msil.sps.mot.com> yairs@msil.sps.mot.com (Yair Shmuely) writes:

> STL's list container is a doubly-linked list that supports bidirectional iterators.
> Why doesn't STL define a singly-linked list as well ?

Fundamentally, the reason was simply that a standard can't include
everything.  There are lots of useful data structures and algorithms
that fit perfectly well into the STL framework, but that were left out
when the STL was adopted as part of the C++ standard.  Singly linked
lists are a good example; so are hash tables, and container-level
generic algorithms, and additional types of function object adaptors.
There's no technical reason why each of those components couldn't have
been included, but including everything just wasn't an option.

Given that the STL could only include one type of list, doubly linked
lists seemed more useful in most cases than singly linked lists.
--
Matt Austern
SGI: MTI Compilers Group
austern@isolde.mti.sgi.com
---
[ comp.std.c++ is moderated.  To submit articles: Try just posting with your
                newsreader.  If that fails, use mailto:std-c++@ncar.ucar.edu
  comp.std.c++ FAQ: http://reality.sgi.com/austern/std-c++/faq.html
  Moderation policy: http://reality.sgi.com/austern/std-c++/policy.html
  Comments? mailto:std-c++-request@ncar.ucar.edu
]

In <<4nmnab$llt@msil.sps.mot.com>>,
yairs@msil.sps.mot.com (Yair Shmuely) wrote:

>STL's list container is a doubly-linked list that supports bidirectional iterators.
>Why doesn't STL define a singly-linked list as well ?

 Also, it should be pointed out that the STL is not a black box.  The
components of it have very well documented entry points etc.  Hence,
it would be a fairly simple matter for you a write STL-compatible
singly-linked list (and list iterator) template,  and have all the
pre-defined STL algorithms and functions work with it.


       Truth,
       James



[ comp.std.c++ is moderated.  To submit articles: try just posting with      ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

STL's list container is a doubly-linked list that supports bidirectional iterators.
Why doesn't STL define a singly-linked list as well ?

The memory overhead of maintaining a 'prev' link that is not required
can be rather high for some applications.

Yair

 --------------------------------------------------------------
 Yair Shmuely                    phone: (972) 9-590205
 CAD Dept.                        fax  : (972) 9-562990
 Motorola Semiconductor Israel    email: yairs@msil.sps.mot.com
 1 Shenkar St, Herzelia, 46120, Israel
 --------------------------------------------------------------




[ comp.std.c++ is moderated.  To submit articles: try just posting with      ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

Yair Shmuely wrote:
>
> STL's list container is a doubly-linked list that supports bidirectional
> iterators. Why doesn't STL define a singly-linked list as well ?
>
> The memory overhead of maintaining a 'prev' link that is not required
> can be rather high for some applications.

Not supporting bidirectional iterators means you lose access to
a set of standard algorithms.  It makes sense to design a
container using the most powerful iterator possible, so the decision
was made to use a doubly-linked list.

When supporters of the STL see questions like this, they have a
canned response.  It goes something like this: "The STL isn't a
standard library, it is simply a framework that tells you how
to implement containers and algorithms in a standard way.  If you
want a singly linked list, by all means develop one! If you follow
the STL rules, it will work seamlessly with the C++ standard library."

Mark Nelson
http://web2.airmail.net/markn
---
[ comp.std.c++ is moderated.  To submit articles: try just posting with      ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]