Tuesday, December 11, 2018

Digest for comp.lang.c++@googlegroups.com - 25 updates in 5 topics

"Shobe, Martin" <martin.shobe@yahoo.com>: Dec 10 10:30PM -0600

On 12/7/2018 7:46 PM, Alf P. Steinbach wrote:
>>> productivity.
 
>> Since the ISO was a re-organization of the ISA and the ISA begin in 1926,
 
> That's irrelevant to anything.
 
Since 1926 is before WW2, the ideas underlying ISO predate WW2 and
couldn't have come from bomb quality during WW2.
 
 
> Did you latch on to the word "female" and fail to apply any rational
> thinking, or was this a more purely random choice of derogatory
> adjective, a shot in the dark hoping to maybe hit something?
 
It's a result of you blaming the quality of the output on the gender.
That's what rational thinking makes of what you said.
 
>> is fake.
 
> That conclusion doesn't follow from any premise or logic of yours.
 
It most certainly does because it would require the effect to come
before the cause.
 
>> Please don't continue to spread it.
 
> You could have looked it up, you know.
 
I did.
 
> problem was that there was much diversity in the requirements for
> different organizations
> [/quote]
 
There's nothing there about your supposed cause. It's also about a
particular standard, ISO 9000, published in 1987.
 
Martin Shobe
"Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com>: Dec 11 12:26PM +0100

On 11.12.2018 05:30, Shobe, Martin wrote:
 
>> That's irrelevant to anything.
 
> Since 1926 is before WW2, the ideas underlying ISO predate WW2 and
> couldn't have come from bomb quality during WW2.
 
You're still irrelevant to anything.
 
With the number of irrelevancies piling up now, it begins to sound not
sound of mind.
 
 
>> thinking, or was this a more purely random choice of derogatory
>> adjective, a shot in the dark hoping to maybe hit something?
 
> It's a result of you blaming the quality of the output on the gender.
 
That would be a lie for someone with a good grasp of reality right in
front of the nose, namely the quoted material.
 
 
 
>> That conclusion doesn't follow from any premise or logic of yours.
 
> It most certainly does because it would require the effect to come
> before the cause.
 
Jeez.
 
 
>>> Please don't continue to spread it.
 
>> You could have looked it up, you know.
 
> I did.
 
No, you failed:
 
 
>> different organizations
>> [/quote]
 
> There's nothing there about your supposed cause.
 
Again, it seems you're unable to relate to what you read, and instead
prefer to relate to idiotic ideas in your mind.
 
 
> It's also about a
> particular standard, ISO 9000, published in 1987.
 
Yes it is.
 
 
Cheers & quite a bit annoyed having to respond to idiocy,
 
- Alf
"Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com>: Dec 11 02:20AM +0100

On 11.12.2018 00:02, Paul wrote:
> return *iter;
 
> return noMajority;
> }
 
I'd sort the vector and just count run lengths.
 
 
Cheers & hth.,
 
- Alf
Jorgen Grahn <grahn+nntp@snipabacken.se>: Dec 11 06:44AM

On Mon, 2018-12-10, Paul wrote:
 
>> If it's important to you, write your own at_least() algorithm.
 
>> /Jorgen
 
> I'm not sure how to proceed in that case.
 
I didn't read the rest, but are you saying you don't know how to
implement this?
 
/**
* Return true if std::count(first, last, val) >= n.
* Will not iterate all the way to last unless necessary.
*/
template <class It, class T>
bool at_least(It first, It last, T val, unsigned n);
 
/Jorgen
 
--
// Jorgen Grahn <grahn@ Oo o. . .
\X/ snipabacken.se> O o .
Paul <pepstein5@gmail.com>: Dec 10 10:50PM -0800

On Tuesday, December 11, 2018 at 1:20:23 AM UTC, Alf P. Steinbach wrote:
 
> I'd sort the vector and just count run lengths.
 
> Cheers & hth.,
 
> - Alf
Thanks, Alf
I'm not sure about practical considerations but I'm doing this
as part of learning about data structures and algorithms where
the "big O" of an algorithm is of primary importance.
 
Sorting the vector would be regarded as terrible because it
uses an O(n log n) algorithm where linear time is available.
 
I know vectors are faster so your idea might work in practice.
 
But how about my original question of efficiently verifying
a condition like m.count(3) > 4; where m is an unordered_multiset<int>?
I suppose an approach might be to research how count() works and then
modify it.
 
Paul
Paul <pepstein5@gmail.com>: Dec 10 10:53PM -0800

On Tuesday, December 11, 2018 at 6:45:06 AM UTC, Jorgen Grahn wrote:
> */
> template <class It, class T>
> bool at_least(It first, It last, T val, unsigned n);
 
No, but you're saying that you don't understand my code.
For a multiset, using std::count rather than multiset::count()
is a really bad idea.
 
Thanks for not reading my post, and then complaining about what you
didn't read.
 
Paul
Jorgen Grahn <grahn+nntp@snipabacken.se>: Dec 11 08:02AM

On Tue, 2018-12-11, Paul wrote:
 
> No, but you're saying that you don't understand my code.
> For a multiset, using std::count rather than multiset::count()
> is a really bad idea.
 
I was referring to your first example problem. If the second one with
unordered_multiset was more important to you, I missed that fact.
 
> Thanks for not reading my post, and then complaining about what you
> didn't read.
 
Where am I complaining or saying I don't understand your code?
I was trying to be helpful.
 
/Jorgen
 
--
// Jorgen Grahn <grahn@ Oo o. . .
\X/ snipabacken.se> O o .
Stuart Redmann <DerTopper@web.de>: Dec 11 09:04AM +0100


> Thanks for not reading my post, and then complaining about what you
> didn't read.
 
> Paul
 
I don't think that Jorgen did not get your point or did not understand your
problem, even though he wrote that he didn't read your posting to the very
end. I find Jorgen's answer quite informative, and BTW Jorgen does not
propose to use std::count on the implementation of at_least, he just left
the implementation empty as an (rather simple) exercise.
 
Jorgen probably misunderstood you in that regard that he thinks you, Paul,
were not able to roll your own version of at_least, but I'm pretty sure
that you are able to do so. You statement "I'm not sure how to proceed in
this case" is very likely meant as "I'm not sure how I can find out whether
the compiler will abort the loop prematurely or not."
 
So this is more or less a classic misunderstanding. However, I think that
your answer to Jorgen is a bit to disrespectful, with regard to Jorgen
being one of the top posters of this group. I'm just afraid that two
competent participants, Jorgen and you, might start to dislike one another
over a simple misunderstanding, which would be a pity.
 
Regards,
Stuart
"Öö Tiib" <ootiib@hot.ee>: Dec 11 01:45AM -0800

On Tuesday, 11 December 2018 01:02:43 UTC+2, Paul wrote:
 
> I'm not sure how to proceed in that case. I'm doing the Boyer-Moore majority
> problem as follows. If a vector of ints has an element that occurs
> more than half the time, output that number, otherwise output 0.5.
 
You return int as double and use 0.5 as indicator of "not found"?
That is obscure. Return something that makes sense like
std::optional<vote> or std::pair<bool,vote>.
 
> There's a standard algorithm to do this by incrementing and decrementing
> a counter. But I'm pretending I don't know that, and trying to do
> the problem time-efficiently via data structures instead.
 
The standard algorithm does it with two passes on unsorted
sequence so O(2*N). Sorting the sequence and then one-pass
counting is O(N*log(N)+N). Copying to another, sorted or hashed
container and then one-pass counting is about as time-complex
as with sorting plus it takes double memory too. Your algorithm
below loses to all of those.
 
> return *iter;
 
> return noMajority;
> }
 
That is mixing up iterators of unordered_multiset and unordered_set.
Does it compile? Also you seemingly call count for every element in
equal range so it looks something like O(N*log(N) + N*N). Sad.
"Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com>: Dec 11 11:05AM +0100

On 11.12.2018 07:50, Paul wrote:
 
>>> return noMajority;
>>> }
 
>> I'd sort the vector and just count run lengths.
 
<> Thanks, Alf
> the "big O" of an algorithm is of primary importance.
 
> Sorting the vector would be regarded as terrible because it
> uses an O(n log n) algorithm where linear time is available.
 
Well, in a situation of paid work, if whoever commissioned the work has
that opinion and e.g. refuses to pay, then of course.
 
But otherwise just keep things simple.
 
The cost of developing this code in a way that can be marginally more
efficient for a zillion values, and the costs of maintenance of that
more than necessary complex code, likely far outweighs the gains from
possibly running it once on a zillion items.
 
 
> a condition like m.count(3) > 4; where m is an unordered_multiset<int>?
> I suppose an approach might be to research how count() works and then
> modify it.
 
For b.count(k) for an unordered associative container b, C++17 table 91,
in §26.2.7, gives complexity requirements average case O(b.count(k)) and
worst case O(b.size()).
 
In §20.4.1.4 it's explained that "Complexity requirements specified in
the library clauses are upper bounds, and implementations that provide
better complexity guarantees satisfy the requirements."
 
The problem with an /unordered/ container is that there's no way to
select only the key values = k that you're interested in, for the
purpose of counting them. An ordered container gives you that, but at
the cost of a log(n) factor of complexity. So you're into trade-offs,
which can be interesting. :)
 
 
Cheers!,
 
- Alf
Paul <pepstein5@gmail.com>: Dec 11 02:40AM -0800

On Tuesday, December 11, 2018 at 9:45:48 AM UTC, Öö Tiib wrote:
 
> That is mixing up iterators of unordered_multiset and unordered_set.
> Does it compile? Also you seemingly call count for every element in
> equal range so it looks something like O(N*log(N) + N*N). Sad.
 
Thanks for your reply. A number of points. In similar exercises, it is
common to have a problem where solutions are assigned a non-negative integer
and -1 is a sentinel to represent the no-solution case.
Here, -1 is valid in the case where a solution is present. So I tried to
mimic this basic technique and chose 0.5 as a sentinel.
However, the technique doesn't work as well because it necessitates changing
the return type which isn't ideal. I hadn't heard of std::optional -- many
thanks for introducing this to me.
The time complexity of my algorithm is O(N)
Thanks for pointing out the mixing of the two types of iterators. I hadn't
noticed that. It does compile with gcc. I avoid posting non-compilable code
by copy-pasting of a verified program (although you couldn't have known
that). I would rather it didn't compile so that I could have uncovered this
mistake myself. I should have just used a range-based for loop.
 
Because of the hashing, my algorithm is O(N). Unordered_multiset uses hashing.
You might be correct that "it looks something like O(N*log(N) + N*N)" but
it is O(N) regardless of what it looks like.
See Alf's post for more info.
 
Paul
Paul <pepstein5@gmail.com>: Dec 11 02:46AM -0800

On Tuesday, December 11, 2018 at 8:04:23 AM UTC, Stuart Redmann wrote:
> over a simple misunderstanding, which would be a pity.
 
> Regards,
> Stuart
 
Ok, no offence intended and all that.
But note that what you (Stuart) are clearly saying is that
1) Jorgen didn't read all of my posting.
2) Based on only a partial reading, Jorgen underestimated me.
You used the word "misunderstood" and the misunderstanding was to think
I couldn't do something that I can do.
 
Anyway, yes, Jorgen is helpful and knows a lot.
 
Thanks to everyone, etc.
 
Paul
Paul <pepstein5@gmail.com>: Dec 11 03:04AM -0800

On Tuesday, December 11, 2018 at 10:05:15 AM UTC, Alf P. Steinbach wrote:
> which can be interesting. :)
 
> Cheers!,
 
> - Alf
 
Hi Alf,
 
I am training for a codility test.
Your algorithm does indeed pass the codility requirements, so it's perfectly
ok for my purposes.
 
Codility aim to make deductions for time-inefficient algorithm but yours
scores 100%.
BTW, my idea with the unordered_multiset count also scores 100% (and it
certainly wouldn't have done if it was O(N ^ 2)).
 
Paul
dawid.bautsch@gmail.com: Dec 11 02:46AM -0800

What happened to this project? Is it already dead? I can't see any activity on the forum as well on the main page.
David Brown <david.brown@hesbynett.no>: Dec 04 12:21PM +0100

On 04/12/18 11:01, Juha Nieminen wrote:
> including).
 
> It might not sound like much, but it's actually pretty handy once you
> get used to it. I wish standard C++ introduced the same directive.
 
One day, one happy day, we will have C++ modules that will handle this
functionality.
 
In the meantime, include guards are simple, portable, reliable,
efficient, and supported by all compilers. I have never felt the need
for #pragma once, nor #import (which some C and C++ tools support).
Manfred <noname@add.invalid>: Dec 04 02:42PM +0100

On 12/4/2018 11:01 AM, Juha Nieminen wrote:
> including).
 
> It might not sound like much, but it's actually pretty handy once you
> get used to it. I wish standard C++ introduced the same directive.
 
#import has been used for a long time by Microsoft compilers to import
COM type libraries. Given that, it is unlikely that it will ever make
into the standard.
 
Besides, I think the meaning that you suggest for #import is too much of
a duplicate of the standard's #include, so it would not be worth a new
standardized directive.
scott@slp53.sl.home (Scott Lurndal): Dec 03 02:11PM


>I benchmarked this at my last company.
 
>One order, maybe. Two - no. It was scary how long it took opening those
>files. Mind, this was on spinning rust.
 
What operating system? Windows file operations are pathetically slow.
David Brown <david.brown@hesbynett.no>: Dec 02 11:35PM +0100

On 02/12/2018 23:29, Jorgen Grahn wrote:
>> files. Mind, this was on spinning rust.
 
> The rust shouldn't matter much, since these headers quickly end up in
> the disk cache -- on Unix anyway, with adequate amounts of RAM.
 
If he is using Windows (at least Win7 and before - I haven't used any
later versions enough to comment about them), it /does/ matter. Windows
file caching is ridiculously bad, and it will re-read them from the disk
most of the time.
Juha Nieminen <nospam@thanks.invalid>: Dec 04 10:01AM

> choosing include guards, as they are standard and supported everywhere.
> But using both kind of defeats the purpose - it combines the
> disadvantages of both methods.
 
I like the approach that Objective-C(++) supports, which is to add a new
preprocessor directive, #import, as an alternative to #include. The former
works like the latter, except that it implicitly behaves as if the file
being included has a #pragma once. Thus you don't need to write any sort
of include guard in your headers (or any other files that you might be
including).
 
It might not sound like much, but it's actually pretty handy once you
get used to it. I wish standard C++ introduced the same directive.
Vir Campestris <vir.campestris@invalid.invalid>: Dec 03 09:10PM

On 03/12/2018 14:11, Scott Lurndal wrote:
> What operating system? Windows file operations are pathetically slow.
 
Windows running in a VM!
 
Andy
Markus Moll <moll.markus@arcor.de>: Dec 04 02:44PM

On Tue, 04 Dec 2018 15:14:40 +0100, Alf P. Steinbach wrote:
 
> execution results in undefined behavior.
> [/quote]
 
> I.e. you're safe. :)
 
Hm, I agree that accessing the sub-objects is safe (which is what I rely
on in my revised code example). However, the problem seems to be
accessing them through a pointer to A, as 3.8 states:
 
[quote]
(...) after the lifetime of an object has ended and before the storage
which the object occupied is reused or released, any pointer that refers
to the storage location where the object will be or was located
may be used but only in limited ways. (...) The program has undefined
behavior if:
(...)
- the pointer is used to access a non-static data member or call a non-
static member function of the object
[/quote]
 
And yes, I think it would be safe to store a pointer to the atomic<bool>
in the thread and use that pointer. However, I would prefer not to do
that. Background: the thread in my example is a timer thread. Users can
add or remove timer callbacks of type "void (*)(void*)". I follow the
familiar pattern of using a static member with that signature which
converts its argument to A* and then calls a corresponding non-static
member function without further arguments. That call, in my opinion,
would be undefined behavior. (And I find that both odd and surprising)
 
Markus
"Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com>: Dec 04 03:14PM +0100

On 04.12.2018 14:53, Markus Moll wrote:
> Accessing any non-static
> members of an object whose lifetime has ended is undefined behavior.
 
No. The formal lifetime ends with start of the destructor execution (if
any). But:
 
C++17 §15.7/1
[quote]
For an object with a non-trivial destructor, referring to any non-static
member or base class of the object after the destructor finishes
execution results in undefined behavior.
[/quote]
 
I.e. you're safe. :)
 
It might feel a little bit weird that during the destructor execution
there is an existing object whose lifetime has ended. But this is
similar to how, during a constructor execution, there is an existing
object whose lifetime has not yet started. It would be difficult to
initialize an object if you couldn't do anything with it in the
constructor body. After the constructor body finishes and the lifetime
starts, the object might turn `const`, say. Similarly, its `const`-ness,
if any, disappears when its lifetime ends and the destructor is invoked.
 
Maybe think of it as a building.
 
With a sufficiently simple view the building's lifetime as a proper
building doesn't start until construction is finished (we disregard the
common practice of doing some final things even after one has started
using the building), and doesn't extend into the eventual destruction.
 
 
Cheers & hth.,
 
- Alf
Markus Moll <moll.markus@arcor.de>: Dec 04 01:53PM

Hi
 
I am suddenly questioning the correctness of a pattern that I've used for
a while now and would like to gather opinions before I make my code
unnecessarily illegible :-)
 
Let's say I have the following class (struct for brevity):
 
struct A : NonTrivialBaseClassWhoseContentsDoNotMatter
{
std::atomic<bool> flag;
 
~A();
};
 
and an object 'a' of type A.
 
Now I have a thread that keeps a pointer to a, 'pa', and occasionally
sets 'pa->flag'. Additionally, there's a function stop_thread() that will
stop that thread. The thread is guaranteed not to access 'a' after a call
to stop_thread.
 
What I've been doing in the past was to call stop_thread() in A's
destructor to make sure that 'a' will not be accessed after its
destruction:
 
A::~A()
{
stop_thread();
}
 
However, a closer reading of the relevant sections in the current C++
draft led me to thinking that this can actually result in undefined
behavior: Per 3.8, an object's lifetime ends when its destructor is
called (if that constructor is non-trivial). Accessing any non-static
members of an object whose lifetime has ended is undefined behavior.
 
Now oddly enough, there seems to be a very easy but awkward way around
this. The destructors of a's sub-objects will only be called once the
body of A's destructor is left. Therefore, their lifetimes end only then.
So to me, the following appears to have defined behavior:
 
struct A : NonTrivialBaseClassWhoseContentsDoNotMatter
{
std::atomic<bool> flag;
};
 
struct B : A
{
~B();
};
 
B::~B()
{
stop_thread();
}
 
Does the original code really exhibit undefined behavior? Does adding
another derived class really help?
 
Any insights are greatly appreciated
 
Markus
James Kuyper <jameskuyper@alumni.caltech.edu>: Dec 04 09:11AM -0500

On 12/4/18 08:53, Markus Moll wrote:
> behavior: Per 3.8, an object's lifetime ends when its destructor is
> called (if that constructor is non-trivial). Accessing any non-static
> members of an object whose lifetime has ended is undefined behavior.
 
The lifetime of an object of type A ends when ~A() starts. However, the
lifetime of A's member objects only ends when they themselves get
destroyed, which occurs at the end of ~A(). It's perfectly safe to
access them from within ~A(). Note the word "finishes" in the following
clause:
 
"For an object with a non-trivial destructor, referring to any
non-static member or base class of the object after the destructor
finishes execution results in undefined behavior." (12.7p1).
Markus Moll <moll.markus@arcor.de>: Dec 04 02:52PM

Oh, alright, I just realized that 3.8 refers to 12.7 for objects under
construction or destruction and that the restriction I quoted really only
applies to "raw storage". That makes a lot more sense :-)
 
Thanks everyone for your help
Markus
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)