chris jefferson wrote:

> Sort, nth_element -
>
> Sort should only require bidirectional iterators.
> Bidirectional iterators would be worst case O(n^2) as present.

You can write sort (and stable sort and friends) in terms of
inplace_merge, with the complete sort taking only O(n log(n)^2) time,
so why allow quadratic behavior?

> find, find_if -
>
> Instead of saying something like "n applications of the predicate", say
>   "if an iterator is found which satisfies the predicate, at most (last
> - first + i) applications of the predicate, otherwise last - first
> applications".

You probably meant "(i-first)" rather than "(last-first)"

Doesn't your implementation specialize
  std::find<set<int>::iterator, int>
to take O(log(N)) time ;-) ?

---
[ 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    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

"chris jefferson" <caj@cs.york.ac.uk> wrote in message
news:d84i9n$65s$1@pump1.york.ac.uk...
> This message is part of an experiment I hope will end up being useful. I
> intend to compose a list of minor fixes to the standard library, which I
> will bundle up and submit for the TR2 library proposal, to (hopefully)
> improve any small weaknesses which have been found after extensive usage
> of the C++ standard library. I'm very interested in any suggestions anyone
> has!
>
> As a vague guide, any suggestions should:
>
> A) Be  minor extensions to the existing library.
> B) Be expressable in a paragraph or two at most.
> C) Take a good C++ programmer no longer than a long afternoon to
> implement.
> D) Not break any existing code.
>

   I'd like the ordered associative containers' search functions (find,
lower_bound, upper_bound, and equal_range) to be templated so they can be
used with compatible orderings, as defined in the boost::multi_index class
(see http://www.boost.org/libs/multi_index/doc/reference/index.html).  For
example, suppose you have  a set<pair<string, double> >. Call it s. It
should be possible to do something like
    s.equal_range("foo")   or s.equal_range("foo", compatablePredicate());

to get the range of all elements x of the set such that x.first == "foo"
(Note that all the element such that x.first == "foo" must form a contiguous
range).

Joe Gottman

---
[ 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    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

caj@cs.york.ac.uk (chris jefferson) writes:

> This message is part of an experiment I hope will end up being
> useful. I intend to compose a list of minor fixes to the standard
> library, which I will bundle up and submit for the TR2 library
> proposal, to (hopefully) improve any small weaknesses which have been
> found after extensive usage of the C++ standard library. I'm very
> interested in any suggestions anyone has!
>
> As a vague guide, any suggestions should:
>
> A) Be  minor extensions to the existing library.
> B) Be expressable in a paragraph or two at most.
> C) Take a good C++ programmer no longer than a long afternoon to implement.
> D) Not break any existing code.
>
> Bad:
>
> - I want a tree container
>      Far too major an extension
[snip]

A tree container deserves a proposal of its own. It would be wonderful
    if someone wrote one, but it does not belong in a bundle of minor
    fixes.

---
[ 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    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

Hi,

> I'm very interested in any suggestions anyone has!

I would like to have a the following members added
to std::map and also to std::tr1::unordered_map:

reference at(
   const Key& _Key
);

const_reference at(
   const Key& _Key
) const;

They would throw a std::out_of_range exception, if
the key is not found in the container. Complexity
should be O(1) for std::tr1::unordered_set and
O(log(n)) for std::map.

Tilman


---
[ 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    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

"Tilman Kuepper" wrote:
> I would like to have a the following members added
> to std::map and also to std::tr1::unordered_map:
>
> reference at(
>    const Key& _Key
> );

Shouldn't the return type be mapped_type& ? Note that reference is
a typedef for Allocator::reference and the default Allocator for map
is allocator<pair<const Key,T> > which makes reference a typedef for
pair<const Key,T>&.

> const_reference at(
>    const Key& _Key
> ) const;

const mapped_type& ?

> They would throw a std::out_of_range exception, if
> the key is not found in the container. Complexity
> should be O(1) for std::tr1::unordered_set

Do you mean _amortized_ constant complexity?

> and
> O(log(n)) for std::map.

Vladimir Marko

---
[ 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    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

Hi Vladimir,

>> reference at(
>>    const Key& _Key
>> );
>
> Shouldn't the return type be mapped_type& ?

Yes, you are right. I just copied the declaration
from std::vector::at(), replaced the parameter and
overlooked the return value...

>> const_reference at(
>>    const Key& _Key
>> ) const;
>
> const mapped_type& ?

Yes, again.

>> Complexity should be O(1) for std::tr1::unordered_set
>
> Do you mean _amortized_ constant complexity?

And also: yes!

Thank you and best regards,
Tilman


---
[ 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    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

> Part of the reason is that inplace_merge without an extra buffer has quite
> a "large constant"...

There has been some algorithmic research in the past 15 years, some
improvements on this tough problem, the constant is not as large as you
think.

>..., and in most cases a quick-sort would replace it.

No it won't. inplace_merge() is stable. quick-sort is not.
Further inplace_merge is O(N) , better than quick sort which is never better
than O(log N * N).
And in terms of memory - you may not need as you think:
If the highest element of the 1st range is less than or equal to the lowest
element of the 2nd range - there is nothing to do.
Otherwise you can reduce the begin-end elements if the elements are in place
until  you find elements that need reordering.
And then the buffer you need to allocate is the minimum of what remains of
the 1st and 2nd range.

 We could of course add the "extra buffer" requirement, but my
> personal opinion is that the whole "If an extra buffer can be allocated
> then.." parts of the standard are a disaster, particularily because as far
> as I know, no-one actually implements them correctly, and it's probably
> not possible to do so.

All the implementations I know implement inplace_merge() correctly.
And stable_sort()
And stable_partition()

Cheers

Stephen Howe


---
[ 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    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

My real point (perhaps too subtle) for suggesting inplace_merge (and
noting that std::find could sometimes be log(N)) was that the standard
probably shouldn't try to get too tight on the complexity requirements.

Stephen Howe wrote:
> Further inplace_merge is O(N)

Can you do inplace_merge in O(N) time with bidirectional iterators?  I
know you can do it with random access iterators.  It looks to me as if
most of the linear-time, in-place merges I've seen seem to assume that
you can advance an iterator by sqrt(N) in constant time.

> , better than quick sort which is never better
> than O(log N * N).

Of course a single call to inplace_merge won't sort an unsorted
sequence.  You still end up doing log N levels of merges to do a
complete sort.

---
[ 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    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

caj@cs.york.ac.uk (chris jefferson) writes:

> The only time I've personally wanted the low-memory versions of these
> algorithms to be activated was stable_sorting a large
> vector<vector<int>>s and vector<list<int>>s, when the internal
> vectors/lists were of a large size (>1,000 elements).
>
> I expected the low-memory versions to be used, however instead what
> happened is that they checked they could allocate enough memory for
> sizeof(iterator_traits<iterator>::value_type) * (length of range),
> suceeded, started copying my vector<vector<int> > into their copy, and
> died horribly. Are there any implementations that don't do this? I'm not
> convinced if you can argue these implementations violate the standard,
> as I'm not sure how you could do it any other way (other than say they
> have to always swap in and out of these vectors, or always use the low
> memory algorithms for non-PODs, or always use a "build temporary vector
> of pointers, and stable_sort that" for non-PODs).

Were you on Linux?  More than likely you ran into the problem that the
system will "allocate" you as much memory as you want, but it only
really tries to _get_ your virtual memory when you step outside the
page cache... when it's too late even for throwing C++ exceptions.
If so, you have to look into how to disable this behavior.  It's not a
C++ issue.

--
Dave Abrahams
Boost Consulting
www.boost-consulting.com

---
[ 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    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]