Wednesday, November 28, 2018

Digest for comp.lang.c++@googlegroups.com - 18 updates in 3 topics

Ralf Goertz <me@myprovider.invalid>: Nov 28 11:44AM +0100

Hi,
 
is there a reason why there is no function "std::binary_find" which has
an interface like "std::find" but takes advantage of the fact that the
input is sorted? At least I have found no such function. Of course
std::set.find could be an option but I guess its performance is much
worse than that of a binary_find in a sorted vector.
leigh.v.johnston@googlemail.com: Nov 28 03:04AM -0800

On Wednesday, November 28, 2018 at 10:44:58 AM UTC, Ralf Goertz wrote:
> input is sorted? At least I have found no such function. Of course
> std::set.find could be an option but I guess its performance is much
> worse than that of a binary_find in a sorted vector.
 
std::lower_bound
 
/Leigh
Ralf Goertz <me@myprovider.invalid>: Nov 28 12:22PM +0100

Am Wed, 28 Nov 2018 03:04:48 -0800 (PST)
> > performance is much worse than that of a binary_find in a sorted
> > vector.
 
> std::lower_bound
 
"Returns an iterator pointing to the first element in the range [first,
last) that is not less than (i.e. greater or equal to) value, or last if
no such element is found."
 
So I still need to check that the element pointed to is actually the one
I was looking for. Given the redundancy in <algorithm> (e.g.
std::find_if and std::find_if_not) the existence of st::lower_bound is
not a good enough reason not to have std::binary_find.
leigh.v.johnston@googlemail.com: Nov 28 03:42AM -0800

On Wednesday, November 28, 2018 at 10:44:58 AM UTC, Ralf Goertz wrote:
> input is sorted? At least I have found no such function. Of course
> std::set.find could be an option but I guess its performance is much
> worse than that of a binary_find in a sorted vector.
 
std::lower_bound and std::upper_bound are perfectly adequate for doing the job of your "binary_find" which is not needed.
 
/Leigh
leigh.v.johnston@googlemail.com: Nov 28 04:29AM -0800

On Wednesday, November 28, 2018 at 10:44:58 AM UTC, Ralf Goertz wrote:
> input is sorted? At least I have found no such function. Of course
> std::set.find could be an option but I guess its performance is much
> worse than that of a binary_find in a sorted vector.
 
There is also std::equal_range
 
/Leigh
James Kuyper <jameskuyper@alumni.caltech.edu>: Nov 28 07:41AM -0500

On 11/28/18 05:44, Ralf Goertz wrote:
 
> is there a reason why there is no function "std::binary_find" which has
> an interface like "std::find" but takes advantage of the fact that the
> input is sorted? At least I have found no such function.
 
Just to confirm: you're looking for a standard function with behavior
equivalent to:
 
 
template<class ForwardIterator, class T>
ForwardIterator binary_find(
ForwardIterator first,
ForwardIterator last, const T& value)
{
ForwardIterator iter =
lower_bound(first, last, value);
if(*iter == value)
return iter;
return last;
}
 
 
> ... Of course
> std::set.find could be an option but I guess its performance is much
> worse than that of a binary_find in a sorted vector.
 
Both should be logarithmic, but I could imagine that std::set::find()
might be slower - but that only matters if you're free to choose your
data structure based solely upon this one operation. Whether you use
std::set or a sorted vector should also depend on how you'll be
initializing and modifying the contents of your container, and that's
often the determining issue, unless you will be searching the container
far more often than you modify its contents.
James Kuyper <jameskuyper@alumni.caltech.edu>: Nov 28 07:44AM -0500

On 11/28/18 05:44, Ralf Goertz wrote:
 
> is there a reason why there is no function "std::binary_find" which has
> an interface like "std::find" but takes advantage of the fact that the
> input is sorted? At least I have found no such function.
 
Just to confirm: you're looking for a standard function with behavior
equivalent to:
 
 
template<class ForwardIterator, class T>
ForwardIterator binary_find(
ForwardIterator first,
ForwardIterator last, const T& value)
{
ForwardIterator iter =
lower_bound(first, last, value);
if(iter !=last && *iter == value)
return iter;
return last;
}
 
 
> ... Of course
> std::set.find could be an option but I guess its performance is much
> worse than that of a binary_find in a sorted vector.
 
Both should be logarithmic, but I could imagine that std::set::find()
might be slower - but that only matters if you're free to choose your
data structure based solely upon this one operation. Whether you use
std::set or a sorted vector should also depend on how you'll be
initializing and modifying the contents of your container, and that's
often the determining issue, unless you will be searching the container
far more often than you modify its contents.
Juha Nieminen <nospam@thanks.invalid>: Nov 28 01:58PM

> I was looking for. Given the redundancy in <algorithm> (e.g.
> std::find_if and std::find_if_not) the existence of st::lower_bound is
> not a good enough reason not to have std::binary_find.
 
In principle the main idea behind std::lower_bound and std::upper_bound
is that you can insert the searched element at the place pointed by
the iterator they return, and the container will remain sorted.
(Their difference is that with std::lower_bound the new element will
be inserted before any possibly existing element that's equal to the
searched one, while with std::upper_bound it will be inserted after any
such element.) They don't really take a stance on whether an equal element
already exists in the container.
 
With std::lower_bound you can check the element pointed by the returned
iterator to see if it's equal to the searched one.
Ralf Goertz <me@myprovider.invalid>: Nov 28 03:10PM +0100

Am Wed, 28 Nov 2018 07:44:05 -0500
> return iter;
> return last;
> }
 
Yes, and that is exactly how I implemented it (after looking at
std::binary_search). And I am curious as to why I had to do that. The
fact that it is not so difficult to implement can hardly be the reason
not to provide it. std::binary_search is almost as easy as that but it
is provided by the standard. I guess the need for finding the actual
position of the element is not unreasonable, it is one of the reasons I
don't want to use std::set because std::distance(first, iter) is also
not that trivial.
 
> initializing and modifying the contents of your container, and that's
> often the determining issue, unless you will be searching the
> container far more often than you modify its contents.
 
Exactly. I love std::set but in my use case it is not appropriate.
"Öö Tiib" <ootiib@hot.ee>: Nov 28 08:00AM -0800

On Wednesday, 28 November 2018 12:44:58 UTC+2, Ralf Goertz wrote:
 
> is there a reason why there is no function "std::binary_find" which has
> an interface like "std::find" but takes advantage of the fact that the
> input is sorted? At least I have found no such function.
 
It sounds too close to std::lower_bound or std::equal range
to matter.
Positive side of std::lower_bound is that it gives the place
where to insert when an element was not found. That is
actually quite common need.
 
> Of course
> std::set.find could be an option but I guess its performance is much
> worse than that of a binary_find in a sorted vector.
 
That can't be sure until measured. Also the std::unordered_set::find
can be even better. Performance of concrete use-case is still
somewhat predictable but typically every container participates
in several use-cases and what is best for one use-case can be
worst for other.
"Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com>: Nov 28 05:34PM +0100

On 28.11.2018 11:44, Ralf Goertz wrote:
> input is sorted? At least I have found no such function. Of course
> std::set.find could be an option but I guess its performance is much
> worse than that of a binary_find in a sorted vector.
 
Don't know, but I regard as a design level defect that
¹`std::binary_search` discards the information about where it found the
specified value, and only returns a `bool`. Nonsensical design IMHO. :(
 
Cheers!,
 
- Alf
 
Notes:
¹ `https://en.cppreference.com/w/cpp/algorithm/binary_search
Juha Nieminen <nospam@thanks.invalid>: Nov 28 07:28PM

> Positive side of std::lower_bound is that it gives the place
> where to insert when an element was not found. That is
> actually quite common need.
 
Nothing stops you from inserting the element at the returned
position even if an equal element already exists. The container
will still be sorter afterwards.
wyniijj@gmail.com: Nov 27 04:09PM -0800

Öö Tiib於 2018年11月28日星期三 UTC+8上午12時28分20秒寫道：
> your file ...:
 
> constexpr Str Token::Pi;
 
> ... will make it to compilöe with -std=c++11 too.
 
It works, but hardly to say better than pre-C++11 style,
after having read https://en.cppreference.com/w/cpp/language/constant_expression
 
 
> The constexpr of C++17 on the other hand feels like a way to
> mark pure functions (in functional programming sense) with keyword
> constexpr.
 
c++11 solved many previous deficiencies but also introduced many fold
complexity of the language for really nothing worthy of, relatively.
So c++11 should be enough for me, I have no time to resolve those
newly invented use-cases and corner issues. Thanks anyway, for your
usage experiences.
 
> Preferring pureness is quite good programming idiom
> in general, about like preferring immutability is good programming
> idiom in general.
 
Let's say. my philosophy is reality. I feel Python is becoming much
more popular and requested from the job market, than c++.
(pureness? immutability?)
"Öö Tiib" <ootiib@hot.ee>: Nov 28 05:13AM -0800


> > ... will make it to compilöe with -std=c++11 too.
 
> It works, but hardly to say better than pre-C++11 style,
> after having read https://en.cppreference.com/w/cpp/language/constant_expression
 
I do not understand what is your point and what is "better".
Yes, to learn C++ one has to read quite a lot of manuals and
books.
 
> So c++11 should be enough for me, I have no time to resolve those
> newly invented use-cases and corner issues. Thanks anyway, for your
> usage experiences.
 
So ... C++11 added sub-bar constexpr and therefore C++11 is enough
for you?
 
 
> Let's say. my philosophy is reality. I feel Python is becoming much
> more popular and requested from the job market, than c++.
> (pureness? immutability?)
 
You compare different tools and philosophies.
Pureness and immutability help both people and compilers to
reason about code and to improve or to optimize it.
Python is scripting language that entirely ignores those
concerns. Where efficiency is needed there it calls
C or C++ programs or modules.
Jorgen Grahn <grahn+nntp@snipabacken.se>: Nov 28 06:47AM

On Mon, 2018-11-26, Paavo Helde wrote:
> std) encouraging a safe way to use these features correctly.
 
> I am meaning things like the condition_variable wait taking a reference
> to the lock, as well as the predicate to wait for. This is a huge step
[etc]
 
That's true, and it's a good thing. Hopefully people now write
clearer and more correct threaded code than in the past -- because of
the facilities available, and because threading is better understood.
 
BTW, I see little mention of the higher-level concurrency mechanisms
in C++11 here. Do people use std::future, std::promise and so on?
 
/Jorgen
 
--
// Jorgen Grahn <grahn@ Oo o. . .
\X/ snipabacken.se> O o .
"Chris M. Thomasson" <invalid_chris_thomasson@invalid.invalid>: Nov 27 11:08PM -0800

On 11/27/2018 10:47 PM, Jorgen Grahn wrote:
> the facilities available, and because threading is better understood.
 
> BTW, I see little mention of the higher-level concurrency mechanisms
> in C++11 here. Do people use std::future, std::promise and so on?
 
Yes: Here is an older discussion, before this was even standard:
 
https://groups.google.com/forum/#!original/comp.lang.c++/nKgbzzJ5nXU/Aqgcj1NOIHEJ
 
Here is the response I got from Scott:
 
https://groups.google.com/forum/#!original/comp.lang.c++/nKgbzzJ5nXU/ECyORKsMwygJ
"Chris M. Thomasson" <invalid_chris_thomasson@invalid.invalid>: Nov 28 12:48AM -0800

On 11/26/2018 12:50 PM, David Brown wrote:
> interactions (used appropriately, of course), and where
> implementation-specific code and features are fine.  And the OS'es in my
> world are often written in C90 - not even C99.
 
Fwiw, here is an old school x86 impl of a fast pathed read-write mutex I
invented a while back, before anything was standard, notice volatile? It
does use inline asm, but ahh shi% let it ride! ;^)
 
https://pastebin.com/raw/f3d6140eb
 
It should work with GCC and MSVC... Heck it even uses POSIX semaphores,
the right way. Every been bitten by failing to loop back around and wait
again on a sem_wait that returns EINTR?
 
Notice the following function:
_____________________
static void
sem_wait_safe(
sem_t* const self
) {
while (sem_wait(self)) {
if (errno != EINTR) abort();
}
}
_____________________
 
I just blast errors into abort in this old code.
Chris Vine <chris@cvine--nospam--.freeserve.co.uk>: Nov 28 12:19PM

On 28 Nov 2018 06:47:09 GMT
Jorgen Grahn <grahn+nntp@snipabacken.se> wrote:
[snip]
> BTW, I see little mention of the higher-level concurrency mechanisms
> in C++11 here. Do people use std::future, std::promise and so on?
 
I don't think std::future is super useful in many cases. It's purpose
is to synchronize by having one thread (the consumer) wait for another
(the producer) to complete where the promise has not been fulfilled. So
it doesn't really implement effective parallelism unless in the use
case in question the consumer rarely waits, or unless every relevant
computation runs in its own thread and you let the thread scheduler
deal with the situation (which can result in thread limits, as well as
performance, being hit).
 
Constructing a chain of continuations with std::future::then() is
sometimes put forward as a solution to unnecessary waiting. It isn't
really, because it is sequential and at the end of the chain of
continuations there is still a future which has to be waited on:
furthermore each std::future::then() continuation spawns a new thread
rather than reusing the old completed one - if that is what you want,
better is to wrap your chain of function calls in a single lambda
expression and execute that via std::async or whatever, so at least
they all execute in the same thread.
 
Most programs I have an interest in use an event loop, because they
have a GUI or employ asynchronous i/o. In the absence of work
stealing, that often solves the problem quite nicely - instead of
waiting on a std::future object, at the end of the computation (which
may be running on a standard thread pool) you can post the continuation
of the computation to the event loop to be dealt with in the main
thread asynchronously. This has been popularised by OS X's Grand
Central Dispatch. I suppose the problem from the standard C++ point of
view is that such event loops are GUI/implementation dependent and so
cannot readily be standardised. Furthermore it is difficult to compose
parallel tasks this way, unless the problem can be turned into
something like a functional map-reduce over a container (in C++, say a
parallel_transform() followed by a parallel_accumulate(), running on a
thread pool), and posting the continuation of that to the event loop.
 
Work stealing fork/join seems to be another popular solution, by
generalising that kind of composition.
You received this digest because you're subscribed to updates for this group. You can change your settings on the group membership page.
To unsubscribe from this group and stop receiving emails from it send an email to comp.lang.c+++unsubscribe@googlegroups.com.
Posted by at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)