| Topic: |
DEVELOP > c-Plus-Plus |
| User: |
"Yin Zhu" |
| Date: |
17 Oct 2006 08:00:06 AM |
| Object: |
What I feel about STL. |
Hello all,
I haved used STL in writing some arithmetic programs for a while now.
There are some very convenient to use, such as
map(use it as a mapping array), set(use it as a dictionary for Insert,
Delete, Exist query ..), vector(a varying length array, O(1) push under
amortization)
but STL didn't support other function , such as
*)findKth in set, althought rb-tree can easily be augmented to support
this
function.
*)sort strings(we often use a radix sort method or ternary searching
tree to
do the string sorting efficently)
now My question comes to
1) Does STL encourge people to augment them? (it seems to me that STL
codes
are so integrated that modifying it will be more difficult to write a
new one)
2) Or STL is just a set of solid examples to show how you write your
own library
from scratch.
thanks in advance.
.
|
|
| User: "Bernd Strieder" |
|
| Title: Re: What I feel about STL. |
17 Oct 2006 09:26:54 AM |
|
|
Hello,
Yin Zhu wrote:
but STL didn't support other function , such as
*)findKth in set, althought rb-tree can easily be augmented to support
this
function.
There is nth_element, but it works on RandomAccessIterators, i.e.
std::vector. An rb-tree augmented with information to support findKth
would no more be a rb-tree, perhaps some hybrid rb-weight-balanced
tree. I think weight balanced binary trees have bad worst case
behaviour on erase, so rb-trees have been chosen by all implementors.
*)sort strings(we often use a radix sort method or ternary searching
tree to
do the string sorting efficently)
STL cannot offer all existing data structures, especially those which
might be not optimal in the general case (e.g. radix sort has bad
worst-case behaviour)
now My question comes to
1) Does STL encourge people to augment them? (it seems to me that STL
codes
are so integrated that modifying it will be more difficult to write a
new one)
There are rules to follow to create your own templates integrating with
the STL, howto define iterators, and tons of examples howto roll
algorithms of your own. Look at boost, they have tons of extensions of
all kinds.
2) Or STL is just a set of solid examples to show how you write your
own library
from scratch.
I think this is some important thought. STL has not been designed to be
inherited and patched, but to be easily usable, and to serve as an
example.
Bernd Strieder
.
|
|
|
|
| User: "Daniel T." |
|
| Title: Re: What I feel about STL. |
17 Oct 2006 09:27:59 AM |
|
|
In article <1161090006.027132.32640@k70g2000cwa.googlegroups.com>,
"Yin Zhu" <zhuyin.nju@gmail.com> wrote:
Hello all,
I haved used STL in writing some arithmetic programs for a while now.
There are some very convenient to use, such as
map(use it as a mapping array), set(use it as a dictionary for Insert,
Delete, Exist query ..), vector(a varying length array, O(1) push under
amortization)
but STL didn't support other function , such as
*)findKth in set, althought rb-tree can easily be augmented to support
this function.
std::advance will do that.
*)sort strings(we often use a radix sort method or ternary searching
tree to
do the string sorting efficently)
As I understand it, only quicksort is in the library. If you want to
implement other sort algorithms, you would have to do that yourself. I'd
suggest you use the same basic interface as std::sort just with a
different function name.
--
There are two things that simply cannot be doubted, logic and perception.
Doubt those, and you no longer have anyone to discuss your doubts with,
nor any ability to discuss them.
.
|
|
|
| User: "Kai-Uwe Bux" |
|
| Title: Re: What I feel about STL. |
17 Oct 2006 09:52:37 AM |
|
|
Daniel T. wrote:
In article <1161090006.027132.32640@k70g2000cwa.googlegroups.com>,
"Yin Zhu" <zhuyin.nju@gmail.com> wrote:
Hello all,
I haved used STL in writing some arithmetic programs for a while now.
There are some very convenient to use, such as
map(use it as a mapping array), set(use it as a dictionary for Insert,
Delete, Exist query ..), vector(a varying length array, O(1) push under
amortization)
but STL didn't support other function , such as
*)findKth in set, althought rb-tree can easily be augmented to support
this function.
std::advance will do that.
Yes, but not necessarily with the complexity that the OP is thinking of.
*)sort strings(we often use a radix sort method or ternary searching
tree to
do the string sorting efficently)
As I understand it, only quicksort is in the library.
[snip]
The sorting algorithm from the standard library is not necessarily
quicksort, although the complexity specifications for std::sort are
designed to allow quicksort as an implementation. However, the HP/SGI based
implementation of the standard library are likely to use introsort, which
is an improvement of quicksort that preserves the average run-time and
still has n log(n) worst case complexity.
Best
Kai-Uwe Bux
.
|
|
|
| User: "=?ISO-8859-1?Q?Jens_M=FCller?=" |
|
| Title: Re: What I feel about STL. |
18 Oct 2006 05:43:58 AM |
|
|
Kai-Uwe Bux wrote:
but STL didn't support other function , such as
*)findKth in set, althought rb-tree can easily be augmented to support
this function.
std::advance will do that.
Yes, but not necessarily with the complexity that the OP is thinking of.
But IF the underlying data structure is a red-black-tree, and
std::advance can be done cheaper than the standard requires, it SHOULD
be done so.
That is of course an issue with the stdlib _implementation_, so the OP
should contact his compiler vendor.
.
|
|
|
|
|
|
| User: "Victor Bazarov" |
|
| Title: Re: What I feel about STL. |
17 Oct 2006 08:35:36 AM |
|
|
Yin Zhu wrote:
Hello all,
I haved used STL in writing some arithmetic programs for a while now.
There are some very convenient to use, such as
map(use it as a mapping array), set(use it as a dictionary for Insert,
Delete, Exist query ..), vector(a varying length array, O(1) push
under amortization)
but STL didn't support other function , such as
*)findKth in set, althought rb-tree can easily be augmented to support
this
function.
*)sort strings(we often use a radix sort method or ternary searching
tree to
do the string sorting efficently)
now My question comes to
1) Does STL encourge people to augment them? (it seems to me that STL
codes
are so integrated that modifying it will be more difficult to write a
new one)
2) Or STL is just a set of solid examples to show how you write your
own library
from scratch.
The Standard library is neigher for making changes to it, nor a set of
examples. It's a small but significant stepping stone to the next part
of your programming. It has many things most people need all the time.
It has some things some people need some of the time. At no point was
it conceived to be an example or a sandbox. It's definitely extensible
and definitely generic enough so your own mechanisms adhering to the
Standard rules (like iterators, for example) will work nicely with the
algorithms in the Standard Library. Or, vice versa, if you write your
algorithm to accept standard iterators, it should just as nicely work
with iterators provided by the Standard containers as well as any other
iterators or even plain pointers.
V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask
.
|
|
|
|
| User: "IndyStef" |
|
| Title: Re: What I feel about STL. |
17 Oct 2006 08:52:24 AM |
|
|
Yin Zhu wrote:
Hello all,
I haved used STL in writing some arithmetic programs for a while now.
There are some very convenient to use, such as
map(use it as a mapping array), set(use it as a dictionary for Insert,
Delete, Exist query ..), vector(a varying length array, O(1) push under
amortization)
but STL didn't support other function , such as
*)findKth in set, althought rb-tree can easily be augmented to support
this
function.
*)sort strings(we often use a radix sort method or ternary searching
tree to
do the string sorting efficently)
now My question comes to
1) Does STL encourge people to augment them? (it seems to me that STL
codes
are so integrated that modifying it will be more difficult to write a
new one)
2) Or STL is just a set of solid examples to show how you write your
own library
from scratch.
thanks in advance.
If you need to get behavior like findKth then you can use the STL
algorithms with user defined functors to act on you data. However, STL
does not really encourage direct access to its internal workings. If
that is required, then you have to come up with your own solutions.
STL was designed to satisfy 90% of the people that needed it, and it
does. The remaining 10% may have to come up with their own solutions.
Stefan
.
|
|
|
|
|
Related Articles |
|
|
