Friday, October 13, 2017

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

Christopher Pisz <christopherpisz@gmail.com>: Oct 13 07:49AM -0700

I want to use a custom structure for a key in an std::unordered_map. The compiler complains that C++ does not provide a hash function for that type. From what I can find in googling, I need to implement some manner of hash operator. Can someone help me with a small example?
 
Let's assume I have
 
struct MyClass
{
std::string m_id1;
int m_id2;
int m_id3;
};
 
where a combination of all 3 ids are unique, but none are unique on their own.
 
What do I need to do to use this as a key in std::unordered_map?
 
I see https://stackoverflow.com/questions/17016175/c-unordered-map-using-a-custom-class-type-as-the-key
 
but I do not understand the actual hashing he is doing there.
Marcel Mueller <news.5.maazl@spamgourmet.org>: Oct 13 05:07PM +0200

On 13.10.17 16.49, Christopher Pisz wrote:
> I want to use a custom structure for a key in an std::unordered_map. The compiler complains that C++ does not provide a hash function for that type. From what I can find in googling, I need to implement some manner of hash operator. Can someone help me with a small example?
[...]
> What do I need to do to use this as a key in std::unordered_map?
 
> I see https://stackoverflow.com/questions/17016175/c-unordered-map-using-a-custom-class-type-as-the-key
 
> but I do not understand the actual hashing he is doing there.
 
The code in the first reply is exactly what yo need, i.e. the
specialization of std::hash for your type. A typical implementation
calls std::hash for each member and combines the result somehow.
 
 
Marcel
Ben Bacarisse <ben.usenet@bsb.me.uk>: Oct 13 04:59PM +0100


> where a combination of all 3 ids are unique, but none are unique on
> their own.
 
> What do I need to do to use this as a key in std::unordered_map?
 
A relatively minimal example would be:
 
struct MyClass
{
std::string m_id1;
int m_id2;
int m_id3;
 
bool operator==(const MyClass &mc) const {
return m_id1 == mc.m_id1 && m_id2 == mc.m_id2 && m_id3 == mc.m_id3;
}
};
 
struct MyClassHash {
std::size_t operator()(const MyClass &k) const
{
return std::hash<std::string>()(k.m_id1) ^
std::hash<int>()(k.m_id2) ^
std::hash<int>()(k.m_id3);
}
};
 
int main()
{
std::unordered_map<MyClass, std::string, MyClassHash> map = {
{ {"abc", 1, 2}, "ABC"},
{ {"def", 2, 3}, "DEF"}
};
}
 
You can even use the class itself as a hash functor (an object that
behaves like a function) by defining a member function
 
std::size_t operator()(const MyClass &k) const
 
in it rather than in a separate struct, but that mean you can never use
the () operator on your class for anything else.
 
<snip>
--
Ben.
Christopher Pisz <christopherpisz@gmail.com>: Oct 13 09:09AM -0700

On Friday, October 13, 2017 at 10:07:27 AM UTC-5, Marcel Mueller wrote:
> [...]
> > What do I need to do to use this as a key in std::unordered_map?
 
> > I see https://stackoverflow.com/questions/17016175/c-unordered-map-using-a-custom-class-type-as-the-key
 
SNIP
 
> specialization of std::hash for your type. A typical implementation
> calls std::hash for each member and combines the result somehow.
 
> Marcel
 
So my attempt looks like this
 
 
#pragma once
 
// Standard Includes
#include <unordered_map>
#include <string>
 
 
//--------------------------------------------------------------------------------------------------
namespace MyNamespace
{
namespace Domain
{
 
//--------------------------------------------------------------------------------------------------
enum MyEnum
{
VAL_1,
VAL_2
};
 
//--------------------------------------------------------------------------------------------------
/// Contains information (that we care about) that identifies an XTend client.
/// These details are passed to the Mid Level when we make requests
struct __declspec(dllexport) MyClass
{
MyClass();
MyClass(const std::string & nonUniqueId
, bool isOn
, const MyEnum & myEnum);
~MyClass();
 
MyClass(const MyClass & rhs);
MyClass(const MyClass && rhs);
 
MyClass & operator = (const MyClass & rhs);
MyClass & operator = (const MyClass && rhs);
 
bool operator < (const MyClass & rhs) const;
bool operator == (const MyClass & rhs) const;
 
 
std::string m_nonUniqueId;
bool m_isOn;
MyEnum m_myEnum;
};
 
//--------------------------------------------------------------------------------------------------
 
} // End namespace
} // End namespace
 
//--------------------------------------------------------------------------------------------------
template<> struct std::hash<MyNamespace::Domain::MyClass>
{
typedef MyNamespace::Domain::MyClass argument_type;
typedef std::size_t result_type;
result_type operator()(argument_type const& s) const noexcept
{
result_type const h1(std::hash<std::string>{}(s.m_nonUniqueId));
result_type const h2(std::hash<bool>{}(s.m_isOn));
result_type const h3(std::hash<int>{}(s.m_myEnum));
return (h1 ^ (h2 << 1) ^ h3 << 2);
}
};
 
 
This line that I don't understand is
return (h1 ^ (h2 << 1) ^ h3 << 2);
 
^ is XOR and << is bit shift. Is this correct? If so, how does this contribute to my making a unique size_t or something that is close to unique? Can someone break that down a bit?
Marcel Mueller <news.5.maazl@spamgourmet.org>: Oct 13 06:28PM +0200

On 13.10.17 18.09, Christopher Pisz wrote:
> return (h1 ^ (h2 << 1) ^ h3 << 2);
 
> ^ is XOR and << is bit shift. Is this correct?
> If so, how does this contribute to my making a unique size_t or something that is close to unique? Can someone break that down a bit?
 
Well, the idea is to combine the hash values of the components in an
asymmetric way to avoid hash collisions when two components are swapped.
 
Using left shift is not that ideal because it discards bits. A bit
rotation would perform better. Unfortunately C++ misses this kind of
operator, although almost any existing hardware support it.
 
Better implementations use more complex polynomials. In fact writing
good hash functions is a rather challenging task.
 
For your purpose it is just fine since nether the boolean nor the enum
provide enough bits that anything gets lost.
 
 
Marcel
asetofsymbols@gmail.com: Oct 13 11:30AM -0700

Ben B. Wrote:
struct MyClassHash {
std::size_t operator()(const MyClass &k) const
{
return std::hash<std::string>()(k.m_id1) ^
std::hash<int>()(k.m_id2) ^
std::hash<int>()(k.m_id3);
}
};
-----
If size_t is the return type of hash<T>()const
if sizeof(size_t)>=sizeof(int)
 
why use one hash function and not just the value, in this case k.m_id3?
asetofsymbols@gmail.com: Oct 13 11:36AM -0700

Something as
 
struct MyClassHash {
std::size_t operator()(const MyClass &k) const
{
return std::hash<std::string>()(k.m_id1) ^ (k.m_id2) ^ (k.m_id3);
}
};
"Öö Tiib" <ootiib@hot.ee>: Oct 12 10:40PM -0700

On Friday, 13 October 2017 01:31:35 UTC+3, Chris Vine wrote:
> > and unlock of it. Then you have both const and thread safety like
> > Herb Sutter said. :D
 
> Your posting is impenetrable. It certainly misses my point.
 
Huh? I mostly wrote about RW locks and those are the tool for
situation where one thread (to what object belongs) may sometimes write
into it while other threads (that have const references to it) often
read it.
 
> thread referencing the object by const reference, say as a function
> argument, can make no automatic assumptions about whether it can safely
> read that object without synchronization.
 
I understood that Herb Sutter meant such design style. It can't be that
he literally meant that we get thread safety for free by using const
keyword and synchronization is not needed with such.
 
For example of design style one can make it so that object does not
return non-const references to its members. It is achievable merely by
not using such function signatures in interface of class. As result
non-const references to its members do not spread all around the board
and so every by-passer can't modify those members.
 
> When Herb said "const means thread-safe" he was not referring to
> objects which are _created_ as const objects and so which cannot
> lawfully be modified at all, if that was your point.
 
It wasn't my point. My point was that communication between threads
has to be under control of design like communication between objects
has to be under control of design.
 
Now lets start from what I think has to be hurtingly obvious. If
something passes const references to some object to other thread
then that sure has to mean promise to not destroy and deallocate
that object when the other thread is processing it. Or how else?
 
Further it also means promise not to modify that object anymore
or it means promise that the object synchronizes accesses of it
itself (for example by using atomics). That is also obvious?
 
If passer can't make such promises then it should pass copies of
object (instead of references) to that other thread. Period.
That is how I understood Herb Sutter.
 
> with something different from thread safety: by itself it guarantees
> nothing about thread safety, unless the object concerned happened to be
> created as a const object.
 
It must be was put up in unfortunate and misleading manner because
as I understand it ... you were mislead.
 
In real software majority of objects are actually immutable (may have
short initialization immediately after their creation). Passing not
synchronized const references to such objects between threads is safe
and easy and works.
 
However here is also a trap. Software will evolve and the immutable
things become "mostly immutable but sometimes configurable". Result
is potential race condition during that "configuration".
 
> guarantees); and their greater complexity compared to mutexes means that
> except where reads considerably exceed writes mutexes are usually
> better.
 
Yes, but that all is about performance of primitives and possible
micro-optimizations by exchanging those. It is more interesting how
your confusion about that big picture did arise. The "const" keyword
does mean nothing like "private" only some compile-time checks. So
how you assumed it carries thread safety unless programmer puts it
to carry that?
Chris Vine <chris@cvine--nospam--.freeserve.co.uk>: Oct 13 10:05AM +0100

On Thu, 12 Oct 2017 22:40:02 -0700 (PDT)
> On Friday, 13 October 2017 01:31:35 UTC+3, Chris Vine wrote:
[run]
> situation where one thread (to what object belongs) may sometimes
> write into it while other threads (that have const references to it)
> often read it.
 
The claim was not that "const means thread-safe if you use RW locks or
mutexes". The claim was that "const means thread safe". Both const
and non-const are thread-safe if you use RW locks or mutexes: you can
just as well read objects concurrently under a RW lock which are held by
non-const reference as those held by const reference. Constness
doesn't come into it.
 
There is a category error being made here: see below.
 
> something passes const references to some object to other thread
> then that sure has to mean promise to not destroy and deallocate
> that object when the other thread is processing it. Or how else?
 
Except that that is wrong. It is perfectly OK (as far as the C++
standard is concerned) to call the delete expression on an object via a
reference to const, just as you can call the delete expression on a
pointer to const. Constness is about whether a particular section of
code modifies an object's state, not about whether it deletes the
object. Some people say that that is a hole in the language. But when
you claim that const means thread-safe, you take the language as it is,
not as you think it should be.
 
> does mean nothing like "private" only some compile-time checks. So
> how you assumed it carries thread safety unless programmer puts it
> to carry that?
 
I agree with very little of this.
 
Thread safety is about shared state: if there is no shared state,
thread safety is irrelevant. You say "in real software majority of
objects are actually immutable". The sad fact is that in real
software, most shared state is mutable, otherwise sharing it is barely
relevant. You are right, as I previously said, that in those few cases
where the shared state itself is immutable, then in those cases (and
only in those cases) the immutability does confer thread safety, at
least so far as the standard library is concerned.
 
The problem is that trying to argue that const means thread safe is a
category error. When you say that something is held as const it means
only that the particular piece of code holding the object as const may
not modify it. Thread safety however is about every thread to which the
object is visible in some form: it is about what the whole program can
do at any point in time, not about what one particular thread can do at
any point in time.
 
Chris
"Öö Tiib" <ootiib@hot.ee>: Oct 13 03:14AM -0700

On Friday, 13 October 2017 12:05:23 UTC+3, Chris Vine wrote:
> On Thu, 12 Oct 2017 22:40:02 -0700 (PDT)
> Öö Tiib <ootiib@hot.ee> wrote:
 
snip
 
> standard is concerned) to call the delete expression on an object via a
> reference to const, just as you can call the delete expression on a
> pointer to const.
 
Of course I can take address of reference to automatic storage object
and call delete to it and I can also call const_cast and write to the
const object and same way I can easily remove all effects of private
by just few lines of code.
Unlike with actual shooting into my actual feet (where I may become
prosecuted for attempt of suicide by some jurisdictions) it is all legal.
 
> object. Some people say that that is a hole in the language. But when
> you claim that const means thread-safe, you take the language as it is,
> not as you think it should be.
 
And here is likely the error in your thinking. C++ is full anarchy language,
do whatever you want, all soft checks that compiler does can be ignored
and rest of the things can be worked around. Or can you bring any
examples of opposite? That was also from list of painfully obvious things
to anyone exposed to C++.
So I meant that the programmer who wrote that passer that passes a
reference to const to other thread has to be author of that promise.
Otherwise the software contains defect.
 
 
> > If passer can't make such promises then it should pass copies of
> > object (instead of references) to that other thread. Period.
> > That is how I understood Herb Sutter.
 
Lack of comments here indicate that you did read it, understood your
error but decided to whine on about how bad is C++ and Herb Sutter.
Use other languages then.
 
 
> > However here is also a trap. Software will evolve and the immutable
> > things become "mostly immutable but sometimes configurable". Result
> > is potential race condition during that "configuration".
 
Lack of comments here indicate that you did read it, understood your
error but decided to whine on about how bad is C++ and Herb Sutter.
Use other languages then.
 
> where the shared state itself is immutable, then in those cases (and
> only in those cases) the immutability does confer thread safety, at
> least so far as the standard library is concerned.
 
And I also wrote that if author of your crap passer of reference to
constant can not promise that it (the described crap itself) won't
destroy or modify the object while other thread (to what it passed the
thing) is potentially using it in processing then it should pass copy of
object and not const reference to it. It is still quoted above.
 
> object is visible in some form: it is about what the whole program can
> do at any point in time, not about what one particular thread can do at
> any point in time.
 
The problem is that you misunderstood what was told to you and pulled
pile of awful and painfully obviously awful nonsense out of it. my current
experience how you pretend that you do not understand what is told to
you makes it close to certain.
Chris Vine <chris@cvine--nospam--.freeserve.co.uk>: Oct 13 11:47AM +0100

On Fri, 13 Oct 2017 03:14:45 -0700 (PDT)
Öö Tiib <ootiib@hot.ee> wrote:
[snip]
> Lack of comments here indicate that you did read it, understood your
> error but decided to whine on about how bad is C++ and Herb Sutter.
> Use other languages then.
 
[snip]
 
> pile of awful and painfully obviously awful nonsense out of it. my
> current experience how you pretend that you do not understand what is
> told to you makes it close to certain.
 
Your posting is the most bizarre piece of writing I have ever seen. It
is completely obvious that I was making no comment "about how bad is
C++". Nor was I commenting on Herb Sutter except in relation to the
choice of his headline summary that "const means thread safe" in the
context of online videos, which was itself in the context of a posting
by someone else which (correctly) pointed out that if you have to lock
threads which modify shared state, you also need to lock threads which
read it.
 
I don't want to prolong this weird ranting, but on the first paragraph
above I tried not to comment on barely intelligible parts of your
posting which were irrelevant to what had appeared to become the issue.
"Öö Tiib" <ootiib@hot.ee>: Oct 13 05:47AM -0700

On Friday, 13 October 2017 13:48:08 UTC+3, Chris Vine wrote:
 
> I don't want to prolong this weird ranting, but on the first paragraph
> above I tried not to comment on barely intelligible parts of your
> posting which were irrelevant to what had appeared to become the issue.
 
Why do not you complain that "resource allocation is initialization" is also
"bad summary", (this time from Stroustrup), since resource allocation does
initialize nothing and strictly from C++ standard one may even call new
without assigning its outcome to anything? If you do not understand what
is told to you then my current impression is that the issue is most likely
on your side.
Stuart Redmann <DerTopper@web.de>: Oct 13 08:30PM +0200


> Sorry for the formatting. All I can use here is Google Groups. I am not
> allowed to install software, I am not allowed to open most sites, I am
> not allowed to access production, I am not allowed....you get the point.
 
That's quite a clue! Apparently there is a bug in your implementation of
the comparator object which has been found in debug mode through additional
checks in your STL implementation. In release mode these checks will not
get executed and your app is simply crashing.
 
Note that you may get breaks in your code even if you have set no
breakpoints. The easiest way to make an application break is to insert
__asm { int 4; } into your code. Under windows that is the equivalent of a
breakpoint in your IDE (if you set a breakpoint in the IDE, the IDE will
simply replace the processor instruction of the breakpoint line by the
interrupt 4 command, which is the software IRQ for breakpoints on Intel
machines).
 
This debug window should give you enough information about where the error
is: std::less<MyClass>!
 
Regards,
Stuart
JiiPee <no@notvalid.com>: Oct 13 02:26PM +0100

This is a bit difficult to find, so asking...
 
 
I thought that when using if-statement the order of logical statements
are evaluated from left to right?!
 
But using my VS 2017 I am suprised that the following crashes:
 
        vector<int> vec;
 
        int a = 5;
 
        if ((0 < vec.size() - 1) && (a > vec[8]))
            ++a;
 
I thought the: (0 < vec.size() - 1) is evaluated first, and if its false
then the second is not evaluated. But it crashes here because of vec[8].
 
Or is there something else in my code possible crashing it? This should
not crash? But the crash report is about the index 8.....
 
 
(here is my real code if interested:
 
        if ((playerInd < playersPrintIndex.size() - 1) &&
            (order + 1 > playersPrintIndex[playerInd] + compactOffset))
            ++playerInd;
 
playerInd= 0 and playersPrintIndex.size = 0
 
 
)
"Öö Tiib" <ootiib@hot.ee>: Oct 13 06:36AM -0700

On Friday, 13 October 2017 16:27:18 UTC+3, JiiPee wrote:
>             ++a;
 
> I thought the: (0 < vec.size() - 1) is evaluated first, and if its false
> then the second is not evaluated. But it crashes here because of vec[8].
 
It is, but trouble is that vec.size() is unsigned number 0 and subtracting
1 from it results with very large unsigned number that is larger than 0
and so first operand of && evaluates to true. Therefore second operand
is also evaluated.
guinness.tony@gmail.com: Oct 13 06:44AM -0700

On Friday, 13 October 2017 14:27:18 UTC+1, JiiPee wrote:
 
> I thought that when using if-statement the order of logical statements
> are evaluated from left to right?!
 
They are.
 
> But using my VS 2017 I am suprised that the following crashes:
 
I'm not.
 
 
>         int a = 5;
 
>         if ((0 < vec.size() - 1) && (a > vec[8]))
>             ++a;
 
Your (0 < vec.size() - 1) is the same as (vec.size() > 1): it tests whether
vec contains at least two items (vec[0] and vec[1]). It gives no guarantees
about the existence of the 9th element (vec[8]).
 
> I thought the: (0 < vec.size() - 1) is evaluated first,
 
It is.
 
< and if its false
> then the second is not evaluated.
 
Correct.
 
> But it crashes here because of vec[8].
 
Of course. You only know that there are at least two elements present,
yet you're trying to access the 9th. It probably doesn't exist.
 
> Or is there something else in my code possible crashing it?
 
Your logic.
 
> This should
> not crash?
 
It could if you don't have at least 9 elements.
 
> But the crash report is about the index 8.....
 
> (here is my real code if interested:
 
I'm not.
JiiPee <no@notvalid.com>: Oct 13 02:58PM +0100

On 13/10/2017 14:36, Öö Tiib wrote:
> 1 from it results with very large unsigned number that is larger than 0
> and so first operand of && evaluates to true. Therefore second operand
> is also evaluated.
 
wow, you are right!! lol, I am blind. I do understand this... so just a
newbie error there. Thanks.
JiiPee <no@notvalid.com>: Oct 13 03:00PM +0100

> about the existence of the 9th element (vec[8]).
 
>> I thought the: (0 < vec.size() - 1) is evaluated first,
> It is.
 
ok but if done first and false it would not evaluate the second, like
Tiib says.
Vlad from Moscow <vlad.moscow@mail.ru>: Oct 13 10:36AM -0700

This statement
 
if ((0 < vec.size() - 1) && (a > vec[8]))
             ++a;
 
is logically wrong. The first subexpression of the condition says nothing about whether there a 9-th element in the vector. Moreover if the vector is empty then this subexpression will yield true due to the fact that the type of the returned value of the member function size() is unsigned.
 
So it would be correctly to write at least like
 
if ( not (vec.size() < 9 ) and (a > vec[8]))
             ++a;
 
 
 
пятница, 13 октября 2017 г., 16:27:18 UTC+3 пользователь JiiPee написал:
Ralf Goertz <me@myprovider.invalid>: Oct 13 11:29AM +0200

Hi,
 
I have a vector of type vector<char> with very many elements. Now I want
to clear it keeping its current capacity because it is going to be
filled again to about its previous size. Ist there a way to do that? At
http://www.cplusplus.com/reference/vector/vector/clear/ I read that
"reallocation is not guaranteed to happen, and the vector capacity is
not guaranteed to change due to calling this function". That means it is
also not guaranteed not to change. Can I make sure it doesn't change?
Bo Persson <bop@gmb.dk>: Oct 13 12:05PM +0200

On 2017-10-13 11:29, Ralf Goertz wrote:
> "reallocation is not guaranteed to happen, and the vector capacity is
> not guaranteed to change due to calling this function". That means it is
> also not guaranteed not to change. Can I make sure it doesn't change?
 
Yes, by using a better reference
 
http://en.cppreference.com/w/cpp/container/vector/clear
 
 
 
Bo Persson
Paavo Helde <myfirstname@osa.pri.ee>: Oct 13 01:13PM +0300

On 13.10.2017 12:29, Ralf Goertz wrote:
> "reallocation is not guaranteed to happen, and the vector capacity is
> not guaranteed to change due to calling this function". That means it is
> also not guaranteed not to change. Can I make sure it doesn't change?
 
The standard does not give certain guarantees either way. However, there
would be not much point to call clear() if one does not intend to reuse
the vector, so from QOI viewpoint the capacity should remain the same
and as far as I have understood most implementations have always
followed this.
 
In C++11 a new function std::vector::shrink_to_fit() was added
specifically to address the concerns of people who wanted to reduce the
capacity after erase() and clear(). This also gives a strong hint that
clear() should not do that.
 
I would put a debug-mode assert into the code checking that the
capacity() remains the same after clear(), so I would get alerted
whenever some new compiler version does not follow the suite.
Paavo Helde <myfirstname@osa.pri.ee>: Oct 13 06:49PM +0300

On 13.10.2017 13:05, Bo Persson wrote:
>> also not guaranteed not to change. Can I make sure it doesn't change?
 
> Yes, by using a better reference
 
> http://en.cppreference.com/w/cpp/container/vector/clear
 
This reference relies on the verbiage in the standard: "No reallocation
shall take place during insertions that happen after a call to reserve()
until the time when an insertion would make the size of the vector
greater than the value of capacity()."
 
However, this claim does not really hold. If there is a shrink_to_fit()
call or a swap() with a default-constructed vector between reserve() and
insert, then the vector capacity is reset (as it should). So I think the
above remark makes a silent assumption that the vector is not shrink or
swapped meanwhile "during insertions"; this silent assumption could very
reasonably involve clear() and erase() as well. Ergo, it does not say
anything about how clear() behaves regarding the capacity.
Bo Persson <bop@gmb.dk>: Oct 13 12:02PM +0200

> Commands == commandments
 
Ah, The Commandments. Yes, they are important
 
https://www.quora.com/What-are-the-Pastafarian-commandments
Bo Persson <bop@gmb.dk>: Oct 13 11:36AM +0200

> I remember for the C standard are ok signed char values -127..127
> So -128 could be implemented as one error value...
 
That's the MINIMUM required range. Most implementations already have
-128..127 as valid values.
 
 
Bo Persson
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)