🚀 go-pugleaf

In article <DED5p2.I2I@online.tmx.com.au>,
Tony Cook <tony@online.tmx.com.au> wrote:
>I've been using the STL a little recently and can't really call
>myself an expert - but I've found that always typing in the
>container's name up to three times for a find or twice for other
>actions is getting a little error-prone, for example:

 [ Example and suggested alternative ellided ]


Join the club(: You will find many who will agree that STL is
error prone to use. I am sure it's a cool and efficient design,
but IMHO not enough attention has been paid to make it easy to use.


>One argument against this is 'the programmer can write their own' -
>but this is true for most things - the libraries are there to
>provide a useful (and hopefully less error-prone) implementation so
>the programmer doesn't have to write their own.

I couldn't agree more.

Even before the ink is dry on the DWP, commercial vendors of STL
implementations are already extending STL in incompatible ways to fix
these STL usage problems. For example the extensions of two of the STL
vendors, ObjectSpace and RogueWave, are sufficiently different from each
other to prevent code written using one library to be easily ported to
the other. Each approach to extending STL to make it more user friendly
has merit to it and none of them is clearly the only correct way.

If incompatible commercial extensions rather than STL out-of-the-box is
what the programming community is going to largely use, then many of the
advantages of standardizing on STL would be compromised.

-- 
Ajay Kamdar        |    Email: ajay@lehman.com    |    Standard Disclaimer 
Lehman Brothers    |    Phone: (201) 524-5048     |
---
[ comp.std.c++ is moderated.  Submission address: std-c++@ncar.ucar.edu.
  Contact address: std-c++-request@ncar.ucar.edu.  The moderation policy
  is summarized in http://dogbert.lbl.gov/~matt/std-c++/policy.html. ]

tony@online.tmx.com.au (Tony Cook) wrote:

>I've been using the STL a little recently and can't really call
>myself an expert - but I've found that always typing in the
>container's name up to three times for a find or twice for other
>actions is getting a little error-prone, for example:

>	// check if already there
>	vector<int> myVector; // this is a _short_ name
>	if (find(myVector.begin(), myVector.end(), someInt)
>		 == myVector.end())
>	{
>	  // not there
>	}

>I find this more than a little error-prone, why isn't there
>something like:

>	template <class Container, class Item>
>	bool find(Container &c, Item const &v, Container::iterator &i)
>	{
>	    i = find(c.begin(), c.end(), v);
>	    return i != c.end();
>	}

>So the above becomes:
>	Container::iterator i;
>	if (!find(myVector, someInt, i)) 
>	{
>	  // not there
>	}

>One argument against this is 'the programmer can write their own' -
>but this is true for most things - the libraries are there to
>provide a useful (and hopefully less error-prone) implementation so
>the programmer doesn't have to write their own.

One reason is that you may not want to search the entire container but rather a
small portion between two iterators.  The find() algorithm allows for such
flexibility.

                                                         -Jason-

[ comp.std.c++ is moderated.  Submission address: std-c++@ncar.ucar.edu.
  Contact address: std-c++-request@ncar.ucar.edu.  The moderation policy
  is summarized in http://dogbert.lbl.gov/~matt/std-c++/policy.html. ]

I would say in your example:

        template <class Container, class Item>
        Container::iterator find(Container &c, Item const &v)
        {
            return find(c.begin(), c.end(), v);
        }

So the above becomes:
        Container::iterator i = find(myVector, someInt);
        if (!i)
        {
          // not there
        }


Generally: all global functions from algobase, which takes two pointers 
(start and finish iterators) should have overloaded 'brother'-function
without these arguments to make operation on all elements of the 
container (most usefull case).



[ comp.std.c++ is moderated.  Submission address: std-c++@ncar.ucar.edu.
  Contact address: std-c++-request@ncar.ucar.edu.  The moderation policy
  is summarized in http://dogbert.lbl.gov/~matt/std-c++/policy.html. ]

ajay@lehman.com (Ajay Kamdar) wrote:
>In article <DED5p2.I2I@online.tmx.com.au>,
>Tony Cook <tony@online.tmx.com.au> wrote:
>>I've been using the STL a little recently and can't really call
>>myself an expert - but I've found that always typing in the
>>container's name up to three times for a find or twice for other
>>actions is getting a little error-prone, for example:
>
> [ Example and suggested alternative ellided ]
>
>
>Join the club(: You will find many who will agree that STL is
>error prone to use. I am sure it's a cool and efficient design,
>but IMHO not enough attention has been paid to make it easy to use.

>
>>One argument against this is 'the programmer can write their own' -
>>but this is true for most things - the libraries are there to
>>provide a useful (and hopefully less error-prone) implementation so
>>the programmer doesn't have to write their own.
>
>I couldn't agree more.
>
>Even before the ink is dry on the DWP, commercial vendors of STL
>implementations are already extending STL in incompatible ways to fix
>these STL usage problems. 


   Unfortunately, there are some misconceptions about STL.
One is that is OUGHT to be "user friendly".

  Nope. STL is a LOW LEVEL TOOLKIT, akin to the ISO C Standard
Library. For example "copy()" is equivalent to "memcpy()".
Now, you wouldn't recommend using "memcpy()" in the middle of
an applications program, would you???

  To make STL into a "user friendly" library is a silly idea.
Instead, the idea is to use STL to implement a completely separate
application library.

  For example, consider the type "SET OF T". Would you use 
the STL set container for this?? You have to be kidding!

  template<class T> class MathSet {
    set<T, less<T> > data;  // USE STL to implement robust point set
   public:
     MathSet() {}
     ...
     friend bool operator < .... // note: NOT STL compare!
     Mathset operator | ..... // Union
     Mathset operator & ..... // Intersection
     ...
     .. getFirst()const { if(data.empty()) throw EMPTYSET().. }
   }

This is what I want from a set ADT. Implementing it is EASY
using STL -- and THAT is the purpose of STL.


If you're getting bored writing

   find(longContainerName.begin(), longContainerName.end() ...... )

.. you're probably using STL the wrong way.
     
BTW: Continue to do so! The only way to discover how to use
something well probably entails learning how to use it badly too.

I've had exactly the same kinds of problems -- but I have to
attribute them to my own level of comprehension, not STL.

-- 
John Max Skaller               voice: 61-2-566-2189
81 Glebe Point Rd              fax:   61-2-660-0850
GLEBE NSW 2037                 email: maxtal@suphys.physics.oz.au
AUSTRALIA                      email: skaller@maxtal.com.au



---
[ comp.std.c++ is moderated.  Submission address: std-c++@ncar.ucar.edu.
  Contact address: std-c++-request@ncar.ucar.edu.  The moderation policy
  is summarized in http://dogbert.lbl.gov/~matt/std-c++/policy.html. ]

John Max Skaller (maxtal@suphys.physics.su.oz.au) wrote:

:    Unfortunately, there are some misconceptions about STL.
: One is that is OUGHT to be "user friendly".

:   Nope. STL is a LOW LEVEL TOOLKIT, akin to the ISO C Standard
: Library.

:   To make STL into a "user friendly" library is a silly idea.
: Instead, the idea is to use STL to implement a completely separate
: application library.

Indeed. STL is a low-level toolkit. 

However, IMHO it is NOT a silly idea to expect that there be a STANDARD
for a high-level container library that people actually use in their code.
A standard for a low-level toolkit is pretty uninteresting. What we have
with STL is a low-level standard that everyone needs to make useable, in
incompatible ways. Now THAT is silly. 

Could you imagine if the draft standard just gave us the basic_string<T> 
template and invited each of us to derive our own user-friendly string class?

Cay
---
[ comp.std.c++ is moderated.  Submission address: std-c++@ncar.ucar.edu.
  Contact address: std-c++-request@ncar.ucar.edu.  The moderation policy
  is summarized in http://dogbert.lbl.gov/~matt/std-c++/policy.html. ]

In article <MATT.95Sep9110458@physics10.Berkeley.EDU>,
John Max Skaller  <maxtal@suphys.physics.su.oz.au> wrote:
>
>   Unfortunately, there are some misconceptions about STL.
>One is that is OUGHT to be "user friendly".
>
>  Nope. STL is a LOW LEVEL TOOLKIT, akin to the ISO C Standard
>Library. For example "copy()" is equivalent to "memcpy()".
>Now, you wouldn't recommend using "memcpy()" in the middle of
>an applications program, would you???
>
>  To make STL into a "user friendly" library is a silly idea.

Nope. The notion that STL should NOT be user friendly is a silly idea.
IMHO, there is never an excuse for a poor interface. Even if STL
is a low level toolkit, there is *nothing* that precludes
it from being easier to use. Look at what ObjectSpace is doing with
some of their extensions. It doesn't require all that much thought
and effort to make STL significantly easier to use in many ways.


>Instead, the idea is to use STL to implement a completely separate
>application library.
>
>  For example, consider the type "SET OF T". Would you use 
>the STL set container for this?? You have to be kidding!
>
>  template<class T> class MathSet {
>    set<T, less<T> > data;  // USE STL to implement robust point set
>   public:
>     MathSet() {}
>     ...
>     friend bool operator < .... // note: NOT STL compare!
>     Mathset operator | ..... // Union
>     Mathset operator & ..... // Intersection
>     ...
>     .. getFirst()const { if(data.empty()) throw EMPTYSET().. }
>   }
>
>This is what I want from a set ADT. Implementing it is EASY
>using STL -- and THAT is the purpose of STL.
>

Implementing it is still ERROR PRONE using STL. That's a major complaint
against STL, and the above example does nothing to answer that complaint.
And the above wrapper code still needs to be implemented; and more errors
will creep into the implementation than otherwise just because STL is
so hard to use.

Moreover, you have got to be kidding if you are saying that all uses of
STL containers should be wrapped up within other ADTs! Things are never
so black and white in practice. But if such wrappers were being written
for each and every use of the STL containers, it would become even more
imperative to make STL less error prone; there would be simply no
justification for making the job of implementing those wrappers harder
than it should be.

[Note: Check out the "C++ Tradeoffs" article by Ellis and Carroll in
  the September '95 issue of the C++ Report for a good discussion of
  a topic some what related to whether to use a STL container directly.]

Container classes are needed both in the interface and implementation
of C++ programs at all levels. If STL is being positioned to NOT fill
the need for a standard general purpose container library that can be
used at all levels of C++ programming, then IMHO STL shouldn't even be
in the standard.


>If you're getting bored writing
>
>   find(longContainerName.begin(), longContainerName.end() ...... )
>
>.. you're probably using STL the wrong way.
>     
>BTW: Continue to do so! The only way to discover how to use
>something well probably entails learning how to use it badly too.
>
>I've had exactly the same kinds of problems -- but I have to
>attribute them to my own level of comprehension, not STL.

Unfortunately, I suspect STL's usability problems transcend the degree
of comprehension. IMHO, if it is not improved, the difficulty of using
STL will lead to more errors than otherwise even after a certain
proficiency is achieved. [Similar to a programmer experienced in both
assembly language and C++  making more errors programming in assembly
than in C++ (some may actually dispute that) just because programming in
assembly language is inherently more error prone.]

-- 
Ajay Kamdar        |    Email: ajay@lehman.com    |    Standard Disclaimer 
Lehman Brothers    |    Phone: (201) 524-5048     |

---
[ comp.std.c++ is moderated.  Submission address: std-c++@ncar.ucar.edu.
  Contact address: std-c++-request@ncar.ucar.edu.  The moderation policy
  is summarized in http://dogbert.lbl.gov/~matt/std-c++/policy.html. ]

This is a rather interesting thread started by Tony Cook in c.std.c++
on whether STL is error-prone or not. Ajay Kamdar seems to agree, and
he also points out something that is quite troublesome to me as well --
commercial vendors adding extensions "before the ink is dry on DWP".
John Max Skaller, on the other hand, claims that STL is designed to be
a low-level toolkit that app programmers would build on and it does not
necessarily have to be "user-friendly". Since I have a vested interest
in the welfare of STL, I'd like to take this discussion further and
find out what people really want out of STL and possibly come up with a
feasible solution that builds on STL (I personally include stl includes
via "stl/include", where the include file wraps the appropriate stl
include file and adds my own simplified algorithms -- such as deleting
a sequence/map and such).

1. What are the various things that you have find to be error-prone?

2. What kind of changes would you like to see in the interface to the
   STL algorithms? The thread started with Tony Cook using the begin/
   end iterator in find algorithm (which I consider essential since I 
   do partial searches all the time) as an example if I remember
   correctly. Cook suggests find() return a bool and modify the iterator 
   argument ... 

3. Container member functions -- any new members that you think "ought"
   to be added? When it comes to STL, I tend to favor not touching the
   container classes and rather favor adding global fcts ala algo.h.

4. Member functions that are also available as algorithms: eg., list<T>
   provides a sort member (uses '<' relation), but STL also provides
   a generalized sort() algorithm where you provide your custom 
   comparator. Is the list<T>::sort() necessary? If so, why?

5. Verbosity: There was a thread few months ago about verbosity in using
   STL containers and iterators. I have cases where each iterator type
   has to be typedef'd just so I can fit the decl in a reasonable width
   line. I remember someone** proposing some typeof() member to return 
   the correct type of iterator so we don't have to do the following:

   map<string, map<string, list<list<point> > >::const_iterator =
       polygon_map.begin();
    
   And this is one of the short ones in my CAD library.
    
   ** I wish I'd saved the article or remembered who it was.

6. Understanding how STL manages storage: In the past 6 months or so, 
   I've received (and answered quite a few!) about 150 mail messages 
   asking about STL storage management. Is it really that hard to
   understand? What kind of examples would make it clear?

7. What kind of documentation would make using STL easy (easier?)? 

8. your turn ...


Ajay Kamdar <ajay@lehman.com> wrote:
>[Note: Check out the "C++ Tradeoffs" article by Ellis and Carroll in
>  the September '95 issue of the C++ Report for a good discussion of
>  a topic some what related to whether to use a STL container directly.]
>

OK article, but I didn't see a whole lot beyond common sense :-)

>Container classes are needed both in the interface and implementation
>of C++ programs at all levels. If STL is being positioned to NOT fill
>the need for a standard general purpose container library that can be
>used at all levels of C++ programming, then IMHO STL shouldn't even be
>in the standard.

No high level toolkit designed by a committee is going to make everybody
(or even a reasonable population) happy! I would much rather have the
higher level toolkit built on top of STL as a separate package, and if
there is enough interest (and input), I might actually do one of these
(it'll be free of course).

regards
mumit -- khan@xraylith.wisc.edu
http://www.xraylith.wisc.edu/~khan/
http://www.xraylith.wisc.edu/~khan/software/stl/STL.newbie.html

ps: Apologies to moderators about botched attempts in posting this, esp
about the misattribution. At least now I know that you guys actually read 
these :-)
---
[ comp.std.c++ is moderated.  Submission address: std-c++@ncar.ucar.edu.
  Contact address: std-c++-request@ncar.ucar.edu.  The moderation policy
  is summarized in http://dogbert.lbl.gov/~matt/std-c++/policy.html. ]

Mumit Khan (khan@xraylith.wisc.edu) wrote:

[ ... ]

>  1. What are the various things that you have find to be error-prone?

My main concern is runtime checking. As iterators don't hold any information
about the respective container, it is impossible to check whether 
an iterator is dereferencable or whether two iterators point to the same 
container. 

Of course you can write wrappers which bind iterator and container together,
but this will result in rewriting quite a portion of STL, and again
several different and incompatible solutions will emerge, which is exactly
what a standard should prevent.

And there are other nasty traps. Recently I fell into this one:

class str
{
  public:
	str(const string &s): st(s), i(0)	{	}
	int	operator<(const str &x) const	{	return i < x.i; }
	// ...

  private:
	string		st;
	int			i;
};

main()
{
	typedef	set<string, less<str> > strset; // Oops, should be less<string>

	strset	a;

	a.insert(string("one"));
	a.insert(string("two"));
	// ...
}

This program compiles and runs well, but gives wrong results. Errors like
this (I suspect there are a lot more of them lurking around) are difficult 
to catch. Although STL is not to blame for it - it's a general problem with 
templates - I'd prefer an interface which prevents the user from providing
inconsistent parameters.

--
+----------------------------------+
|          Bernd Eggink            |
|    Rechenzentrum Uni Hamburg     |
| admin@rzaix13.rrz.uni-hamburg.de |
+----------------------------------+

---
[ comp.std.c++ is moderated.  Submission address: std-c++@ncar.ucar.edu.
  Contact address: std-c++-request@ncar.ucar.edu.  The moderation policy
  is summarized in http://dogbert.lbl.gov/~matt/std-c++/policy.html. ]

In article <4378m2$1n86@news.doit.wisc.edu>, khan@xraylith.wisc.edu (Mumit Khan) writes:
|> This is a rather interesting thread started by Tony Cook in c.std.c++
[...]
|> 
|> 
|> 3. Container member functions -- any new members that you think "ought"
|>    to be added? When it comes to STL, I tend to favor not touching the
|>    container classes and rather favor adding global fcts ala algo.h.
|>

template <class Container>
void clear(Container& c) {

  c.erase(c.begin(),c.end());
}

|> 
|> 8. your turn ...
|>

maybe make containers of pointers a bit easier to use:

o allow "standard" comparison functions to be used with
  containers of pointers:

  set<int*,indirect_apply<less<int> > > spi;

  (boy, that sure is synctatic sugar :-)

o also, I have found

  template <class Iterator>
  void delete_range(Iterator first,Iterator last) {

    while (first!=last) {
      delete *first++;
    }
  }

  useful.


Fabrice
---
Fabrice Clerc
clerc@gla.ecoledoc.ibp.fr




[ comp.std.c++ is moderated.  Submission address: std-c++@ncar.ucar.edu.
  Contact address: std-c++-request@ncar.ucar.edu.  The moderation policy
  is summarized in http://dogbert.lbl.gov/~matt/std-c++/policy.html. ]

I've received a few notes already in response to my recent post on a
survey regarding STL's (so-called) user-unfriendly-ness and asking
suggestions on what we can do about it. I'm sure more's on the way, 
and I'd like to ask people to post it to the forum as well send me a 
copy via email if possible; this way more people get to read it right 
away and react to it. Also, if you send me email replies to these 
questions posted in an open forum, I would assume by default that you 
do *not* mind if I repost these on the newsgroup for the sake of 
openness; if you would rather that I not mention your post and/or
name, please do let me know in your note -- MK

In article <4378m2$1n86@news.doit.wisc.edu>,
I <khan@xraylith.wisc.edu> had written:
>
>2. What kind of changes would you like to see in the interface to the
>   STL algorithms? The thread started with Tony Cook using the begin/
>   end iterator in find algorithm (which I consider essential since I 
>   do partial searches all the time) as an example if I remember
>   correctly. Cook suggests find() return a bool and modify the iterator 
>   argument ... 
>
>4. Member functions that are also available as algorithms: eg., list<T>
>   provides a sort member (uses '<' relation), but STL also provides
>   a generalized sort() algorithm where you provide your custom 
>   comparator. Is the list<T>::sort() necessary? If so, why?
>


2 people have already mentioned that they're dismayed by the fact
that some algorithms explicitly exclude certain containers; eg., Cay
Hosrtmann asks why the sort algorithm does not work with lists. My
first reaction to this is that I think of STL algorithms to work on
specific type of iterators as opposed to work on specific types of
containers. Hence the sort algorithm, which, as implemented, needs 
random access to the elements in the container, requires random access 
iterators to work with and list<T> gets left in the dust. Do others 
feel strongly about it? Also, there is a simple way out. The following 
code will make sort algorithm work on ALL types of containers, include 
list<T> albeit not as efficiently as it would on a container that 
supports random access iterators.

Would the following (or some more efficient rendition of thereof) be 
something that is a candidate for an "extended" STL library?

===
//
// slightly modified STL standard sort() algorithm to not exclude 
// containers that do not support Random Access Iterators. Uses the 
// same interface as HP reference sort(first, last) interface.
//
// This code used with libg++ STL tweaks the infamous "template 
// unification failed" problem in all version of, so caveat emptore. 
// OS STL<ToolKit> works around this gcc problem.
//
// Mumit Khan <khan@xraylith.wisc.edu>
// 
//
#include <algo.h>
#include <deque.h>

template <class RandomAccessIterator, class T>
inline void __generalized_sort (
    RandomAccessIterator first, 
    RandomAccessIterator last,
    random_access_iterator_tag,
    T*
) {
    sort(first, last);
}

//
// highly inefficient, but proves the point.
//
template <class BidirectionalIterator, class T>
inline void __generalized_sort (
    BidirectionalIterator first, 
    BidirectionalIterator last,
    bidirectional_iterator_tag,
    T*
) {
    deque<T> deque1;
    copy(first, last, back_inserter(deque1));
    sort(deque1.begin(), deque1.end());
    copy(deque1.begin(), deque1.end(), first);
}

template <class BidirectionalIterator>
inline void generalized_sort (
    BidirectionalIterator first, 
    BidirectionalIterator last
) {
    __generalized_sort(
	first, last, iterator_category(first), value_type(first)
    );
}

==

regards,
mumit -- khan@xraylith.wisc.edu
http://www.xraylith.wisc.edu/~khan/
---
[ comp.std.c++ is moderated.  Submission address: std-c++@ncar.ucar.edu.
  Contact address: std-c++-request@ncar.ucar.edu.  The moderation policy
  is summarized in http://dogbert.lbl.gov/~matt/std-c++/policy.html. ]

In article <MATT.95Sep14103019@physics10.berkeley.edu>,
Bernd Eggink <admin@rzaix53.uni-hamburg.de> wrote:
>
>Mumit Khan (khan@xraylith.wisc.edu) wrote:
>
>[ ... ]
>
>>  1. What are the various things that you have find to be error-prone?
>
>My main concern is runtime checking. As iterators don't hold any information
>about the respective container, it is impossible to check whether 
>an iterator is dereferencable or whether two iterators point to the same 
>container. 

This is a sticky point, and just about *everybody* I've corresponded
with has brought up this point. I at one point had added some code to
some of the iterators in ObjectSpace STL<ToolKit> to throw an exception
when you dereference an invalid iterator, but I haven't had the
"opportunity" to use it yet (so the code isn't really even tested).
What I don't like about my hack, and that's what you mention as well,
is that I've had to couple the iterator and container and I rather like
the (current) decoupled view of the two.

I'll see if I can easily retrofit the changes to the free implementation
(either HP reference or libg++) and then I'll post it. It's pretty simple
minded, basically built like the Fallible<T> in "Scientific and Engr C++"
by Barton and Nackman. I can't remember exactly how much I had actually
completed, but believe I only implemented the checked iterators for the 
sequential containers (list<T>, vector<T> and deque<T>), not for the 
associative ones.

the easiest implementation of a checked-iterator is of course is that
for the vector<T> class ...

As for a test if two iterators point to the same iterators, the coupling
would provide that as well.

Has anybody implemented this in a clean way??

>
>And there are other nasty traps. Recently I fell into this one:
>
>class str
>{
>  public:
>	str(const string &s): st(s), i(0)	{	}
>	int	operator<(const str &x) const	{	return i < x.i; }
>	// ...
>
>  private:
>	string		st;
>	int			i;
>};
>
>main()
>{
>	typedef	set<string, less<str> > strset; // Oops, should be less<string>
>
>	strset	a;
>
>	a.insert(string("one"));
>	a.insert(string("two"));
>	// ...
>}
>


But what would you like the compiler/implementations to do in these
cases? This is of course a design feature that you can pass custom
comparator function. Now if the compilers supported the draft, then
at least your problem will go away;

    template <class Key, class Compare = less<Key> > class set; 

so you'd never have to write code like you have to now unless you *want*
to supply a custom comparator (eg., when the key is a pointer to some
object). Your problem is solved.

Of course, if C++ provided constraints checking (see the D&E for a
discussion on this), you could do much more ...

Complain to compiler vendors to catch up to the standard. But wait, there
is no C++ standard. Aaargghhhh!

regards
mumit -- khan@xraylith.wisc.edu
http://www.xraylith.wisc.edu/~khan/

Cc: comp.std.c++, Bernd Eggink <admin@rzaix53.uni-hamburg.de> 


---
[ comp.std.c++ is moderated.  Submission address: std-c++@ncar.ucar.edu.
  Contact address: std-c++-request@ncar.ucar.edu.  The moderation policy
  is summarized in http://dogbert.lbl.gov/~matt/std-c++/policy.html. ]

khan@xraylith.wisc.edu (Mumit Khan) wrote:
>
>2 people have already mentioned that they're dismayed by the fact
>that some algorithms explicitly exclude certain containers; eg., Cay
>Hosrtmann asks why the sort algorithm does not work with lists. 

    The reasons is that the performance guarrantees would not
be met. I personally find that a bit weak: often performance
is less an issue than utility. However, there is no point
at all having separate iteratotr categories for forward, bidirectional
and random iterators otherwise, since mathematically
they're entirely equivalent.

    There is a simple and general way to fix the problem .....

>Would the following (or some more efficient rendition of thereof) be 
>something that is a candidate for an "extended" STL library?
>template <class BidirectionalIterator, class T>
>inline void __generalized_sort (
>    BidirectionalIterator first, 
>    BidirectionalIterator last,
>    bidirectional_iterator_tag,
>    T*

   but while it may be more efficient, this technique isn't
general.

   A general way is to use a bidirectional to random access
iterator range adaptor. Basically, some simple delegation
can be used to convert any iterator kind into any other.
The most useful case is converting input iterators into
forward iterators. [It took me about a day to get that
working]

   Note that such adapted iterators can be very slow:
however random acess on a singly linked list container (for example)
is possible by simply running down the whole list every time.



-- 
John Max Skaller               voice: 61-2-566-2189
81 Glebe Point Rd              fax:   61-2-660-0850
GLEBE NSW 2037                 email: maxtal@suphys.physics.oz.au
AUSTRALIA                      email: skaller@maxtal.com.au




---
[ comp.std.c++ is moderated.  Submission address: std-c++@ncar.ucar.edu.
  Contact address: std-c++-request@ncar.ucar.edu.  The moderation policy
  is summarized in http://dogbert.lbl.gov/~matt/std-c++/policy.html. ]

Fabrice Clerc <clerc@gla.ecoledoc.ibp.fr> wrote in comp.std.c++:
> maybe make containers of pointers a bit easier to use:
> 
> o allow "standard" comparison functions to be used with
>   containers of pointers:
> 
>   set<int*,indirect_apply<less<int> > > spi;
> 
>   (boy, that sure is synctatic sugar :-)
> 

I always have and still do contend that if you have pointers in your
containers, you should revisit the design: if you're storing pointers
to basic/built-in types, why bother; if you're storing pointers to
classes either for efficiency/space or for polymorphism, use a wrapper.
See http://www.xraylith.wisc.edu/~khan/software/stl/STL.newbie.html for
some rationale and examples of this.

With that out of the way, how about the following: (off the top of my 
head, so not tested yet)


    #include <stl.h>

    template <class BinaryFunction>
    class binary_dereference : binary_function<
	BinaryFunction::first_argument_type,
	BinaryFunction::second_argument_type, 
	BinaryFunction::result_type> 
    {
    public:
	binary_dereference(const BinaryFunction& func) : func_(func) { }
	BinaryFunction::result_type operator() (
	    const BinaryFunction::first_argument_type*& x,
	    const BinaryFunction::second_argument_type*& y
	) const {
	    return func_(*x, *y);
	}
    protected:
	BinaryFunction func_;
    };

    //
    // useful adapter for binary_dereference function object
    //
    template <class BinaryFunction>
    inline binary_dereference<BinaryFunction>
    dereference2 (const BinaryFunction& func) 
    {
	return binary_dereference<BinaryFunction>(func);
    }

    //
    // define and populate deque<int*> ...
    //

    deque<int*> deque1;


    //
    // now you can do either of the following...
    //

    sort(
	deque1.begin(), deque1.end(), 
	binary_dereference<less<int> > (less<int>())
    );

    //
    // or better off using the adapter, dereference2
    //
    sort(
	deque1.begin(), deque1.end(), 
	dereference2 (less<int> ())
    );


or you could always do what ObjectSpace does -- define new global fcts
(eg., less_p which deferences the args before using them).


> 
> 
> o also, I have found
> 
>   template <class Iterator>
>   void delete_range(Iterator first,Iterator last) {
> 
>     while (first!=last) {
>       delete *first++;
>     }
>   }
> 
>   useful.
> 

Yup very much so. Again see my STL page for more of these.

The real question is whether these "convenience" functions/algos should
actually be (have been) part of the standard? My personal belief is that
these are way too specific to programming style and the particular 
application, and should be left to the user to add to the STL base,
preferably in a different namespace.

> ---
> Fabrice Clerc
> clerc@gla.ecoledoc.ibp.fr
>

regards,
mumit -- khan@xraylith.wisc.edu
http://www.xraylith.wisc.edu/~khan/


Cc: comp.std.c++, clerc@gla.ecoledoc.ibp.fr

[ comp.std.c++ is moderated.  Submission address: std-c++@ncar.ucar.edu.
  Contact address: std-c++-request@ncar.ucar.edu.  The moderation policy
  is summarized in http://dogbert.lbl.gov/~matt/std-c++/policy.html. ]

dick@silicon.csci.csusb.edu (Dr. Richard Botting) wrote:
>John Max Skaller (maxtal@suphys.physics.su.oz.au) wrote:
>
>: khan@xraylith.wisc.edu (Mumit Khan) wrote:
>: >
>: >2 people have already mentioned that they're dismayed by the fact
>: >that some algorithms explicitly exclude certain containers; eg., Cay
>: >Hosrtmann asks why the sort algorithm does not work with lists. 
>
>:     The reasons is that the performance guarrantees would not
>: be met. I personally find that a bit weak: often performance
>: is less an issue than utility. 
>
>The old argument that a programmer costs more per minute than
>the CPU come in here I guess.

     Yes. In fact, it is possible the requirements will be
weakened, or a version that works with lists supplied.
In any case, work-arounds are easy: lists support 
bidirectional iterators which are functionally equivalent to
random ones, and one can convert bidirectional iterators
to random ones with trivial adaptors.

     There is a serious threat that supplying too much
"convenience" will break the fundamentals of STL.
It has properties such as performance guarrantees,
operations doing just one thing, etc which make it 
predicatble and reliable as a _basis_ for a full
blown library.

     A half hearted attempted to extend that basis 
_in_ the C++ Standard could be worse than leaving all
these problems to programmers (all of whome have
different requirements). [I.e. I'm arguing
that some minimalism is a good thing here]


-- 
John Max Skaller               voice: 61-2-566-2189
81 Glebe Point Rd              fax:   61-2-660-0850
GLEBE NSW 2037                 email: maxtal@suphys.physics.oz.au
AUSTRALIA                      email: skaller@maxtal.com.au



[ comp.std.c++ is moderated.  Submission address: std-c++@ncar.ucar.edu.
  Contact address: std-c++-request@ncar.ucar.edu.  The moderation policy
  is summarized in http://dogbert.lbl.gov/~matt/std-c++/policy.html. ]

John Max Skaller (maxtal@suphys.physics.su.oz.au) wrote:
: dick@silicon.csci.csusb.edu (Dr. Richard Botting) wrote:
: >John Max Skaller (maxtal@suphys.physics.su.oz.au) wrote:
: >
: >: khan@xraylith.wisc.edu (Mumit Khan) wrote:
: >: >
: >: >2 people have already mentioned that they're dismayed by the fact
: >: >that some algorithms explicitly exclude certain containers; eg., Cay
: >: >Hosrtmann asks why the sort algorithm does not work with lists. 
: >
: >:     The reasons is that the performance guarrantees would not
: >: be met. I personally find that a bit weak: often performance
: >: is less an issue than utility. 
: >
: >The old argument that a programmer costs more per minute than
: >the CPU come in here I guess.

:      Yes. In fact, it is possible the requirements will be
: weakened, or a version that works with lists supplied.
[snip]
:      There is a serious threat that supplying too much
: "convenience" will break the fundamentals of STL.
: It has properties such as performance guarrantees,
: operations doing just one thing, etc which make it 
: predicatble and reliable as a _basis_ for a full
: blown library.

:      A half hearted attempted to extend that basis 
: _in_ the C++ Standard could be worse than leaving all
: these problems to programmers (all of whome have
: different requirements). [I.e. I'm arguing
: that some minimalism is a good thing here]

I've been thinking
that different needs demand different implementations.
	(sorting being Knuth's 1971 example)
I've been wondering whether a multilevel library might resolve
some of the conflicts between requirements.  
So perhaps, there might be common headers but multiple
implementations of the standard libraries.  
	For example: high speed vs low RAM vs safe'n'sure vs...

However this does not handle those cases where the
non-functional requirements force a change in the interface/header.

This makes me wonder whether standard libraries may need
to be, kind of, multiple level.  At the top a pure virtual
interface of common functionallity.  In the middle the more
specific (and "better for special needs") classes.  And at
the third level, the implementation.

Similar ideas have appeared in several research papers in software
engineeering recently.

--
	dick@csci.csusb.edu=rbotting@wiley.csusb.edu.
Find out what's new at http://www.csci.csusb.edu/doc/www.sites.html
Disclaimer:`CSUSB may or may not agree with this message`.
Copyright(1995):Copy this freely but include the following link to the
<a href="http://www.csci.csusb.edu/dick/signature.html">author's signature</a>

[ comp.std.c++ is moderated.  Submission address: std-c++@ncar.ucar.edu.
  Contact address: std-c++-request@ncar.ucar.edu.  The moderation policy
  is summarized in http://dogbert.lbl.gov/~matt/std-c++/policy.html. ]

dick@silicon.csci.csusb.edu (Dr. Richard Botting) wrote:
>This makes me wonder whether standard libraries may need
>to be, kind of, multiple level.  

This kind of thing could be good, but it is hard to
agree on the details (i.e. hard to standardise) at this
time.

However, with namespaces, one can have both the 
standard STL as well as using the MAXTAL implementation
(because my implementation lives in its own namespace).

This isn't quite what you want, but is probably the
closest C++ can come to it.

In the case of the inheritance structure of the
exception classes I argued strongly that the standard
should specify ABSTRACT classes derived using
virtual inheritance -- but the committee thought
otherwise.

So .. if you prefer my implementation, you just use
namespace MAXTAL and you have the full object oriented
exceptions, and if you use the namespace 'std' you get
the fixed value oriented exceptions.


Not ideal, but namespaces are the best we've got
for supporting multiple libraries -- and they do a fairly
good job considering the specs were produced by
a committee :-)


-- 
John Max Skaller               voice: 61-2-566-2189
81 Glebe Point Rd              fax:   61-2-660-0850
GLEBE NSW 2037                 email: maxtal@suphys.physics.oz.au
AUSTRALIA                      email: skaller@maxtal.com.au



---
[ comp.std.c++ is moderated.  Submission address: std-c++@ncar.ucar.edu.
  Contact address: std-c++-request@ncar.ucar.edu.  The moderation policy
  is summarized in http://dogbert.lbl.gov/~matt/std-c++/policy.html. ]