Thursday, August 13, 2015

Digest for comp.lang.c++@googlegroups.com - 23 updates in 11 topics

Paul <pepstein5@gmail.com>: Aug 13 02:43PM -0700

Full disclosure -- I have also posted this implementation of a solution to the maximum gap problem to sci.math (no answer received there so far).
 
Although my algorithm appears to work, I'm concerned that my use of data structures is poor. Any ideas for improvement? Or does anyone think it's fine?
 
Thank you,
 
Paul.
 
/* Given an unsorted array, find the maximum difference between the successive elements in its sorted form.
Try to solve it in linear time/space. Return 0 if the array contains less than 2 elements.
You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.*/
 
// Algorithm implemented is: http://cgm.cs.mcgill.ca/~godfried/teaching/dm-reading-assignments/Maximum-Gap-Problem.pdf
#include <utility>
#include <vector>
#include <stdexcept>
#include <unordered_map>
#include <algorithm>
#include <cstdlib>
#include <iostream>
 
// Step 1. Use a pair to find the min and the max.
std::pair<int, int> findExtrema(const std::vector<int>& vec)
{
if(vec.empty())
throw std::runtime_error("Empty vector");
 
int min = vec[0];
int max = vec[0];
 
for(unsigned i = 1; i < vec.size(); ++i)
{
if(vec[i] < min)
min = vec[i];
else if (vec[i] > max)
max = vec[i];
}
 
return {min, max};
}
 
// Step 2.
// Divide the min - max interval into n - 1 buckets of equal size.
// The end-points of each bucket are generated and returned in order.
 
/* std::vector<int> buckets(const std::vector<int>& vec, const std::pair<int, int>& extrema)
{
if(vec.size() < 2)
throw std::runtime_error("Vector with less than two elements.");
int min = extrema.first;
int max = extrema.second;
 
std::vector<int> result;
 
for(int i = 0; i < vec.size() - 1; ++i)
result.push_back (min + i * (max - min)/(vec.size() - 1));
}*/
 
// Step 3. Use an unordered_map (hash table) to obtain the correct bucket index (as in step 2).
// for each element of the vector.
 
std::unordered_map<int, unsigned> index(const std::vector<int>& vec)
{
if(vec.size() < 2)
throw std::runtime_error("vector has less than two elements");
 
const auto minMax = findExtrema(vec);
const int min = minMax.first;
const int max = minMax.second;
const double intervalWidth = max - min;
const double bucketSize = intervalWidth/(vec.size()-1);
std::unordered_map<int, unsigned> result;
for(unsigned i = 0; i < vec.size(); ++i)
result[vec[i]] = std::floor((vec[i] - min)/bucketSize);
 
return result;
}
 
// Step 4. For each bucket, define a pair of integers.
// One integer corresponds to the max within the bucket. The other corresponds
// to the min within the bucket.
// However some buckets are empty.
 
std::vector<std::pair<int, int> > extremaInBuckets(const std::vector<int>& vec)
{
std::vector<std::pair<int, int> > result;
auto hash = index(vec);
std::vector<std::vector<int>> vectorOfBuckets(hash.size());
for(unsigned i = 0; i < vec.size(); ++i)
vectorOfBuckets[hash[vec[i]]].push_back(vec[i]);
 
for(unsigned i = 0; i < hash.size(); ++i)
if(!vectorOfBuckets[i].empty())
result.push_back(findExtrema(vectorOfBuckets[i]));
 
return result;
}
 
// Step 5. Use the above function to obtain the max gap
int maxGap(const std::vector<int>& vec)
{
if(vec.size() < 2)
return 0;
 
auto gaps = extremaInBuckets(vec);
if(gaps.size() < 2)
throw std::runtime_error("Algorithm not performing as expected.");
 
int max = 0;
for(unsigned i = 0; i < gaps.size() - 1; ++i)
max = std::max(gaps[i+1].first - gaps[i].second, max);
 
return max;
}
 
int main()
{
std::vector<int>testVec;
for(int i = 0; i < 20; ++i)
testVec.push_back(rand());
 
std::cout << "Original vector is\n";
for(int i = 0; i < testVec.size(); ++ i)
std::cout << testVec[i] << "\n";
 
std::cout << "\n Sorted vector is \n";
std::vector<int> copyVec = testVec;
std::sort(copyVec.begin(), copyVec.end());
for(int i = 0; i < copyVec.size(); ++ i)
std::cout << copyVec[i] << "\n";
 
std::cout << "\n Max gap is " << maxGap(testVec);
}
Doug Mika <dougmmika@gmail.com>: Aug 12 07:18PM -0700

I have the following code snippet:
 
std::shared_ptr<my_data> p;
void process_global_data()
{
std::shared_ptr<my_data> local=std::atomic_load(&p);
process_data(local);
}
 
what confuses me is why we don't write
 
std::shared_ptr<my_data> local=std::atomic_load(p);
 
after all, p is already a pointer, won't getting an address of p (&p) lead to me having a pointer to a pointer to my_data?
 
Thanks
"Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com>: Aug 13 09:16AM +0200

On 13-Aug-15 4:18 AM, Doug Mika wrote:
 
> std::shared_ptr<my_data> local=std::atomic_load(p);
 
> after all, p is already a pointer, won't getting an address of p (&p)
> lead to me having a pointer to a pointer to my_data?
 
It's just the design of `atomic_load` is imperfect, that it expects a
pointer rather than a reference as argument.
 
You can look up standard library functions in any decent reference, e.g.
<url: http://en.cppreference.com/w/cpp/atomic/atomic_load>.
 
That said, the code shown appears to be very meaningless, and exhibiting
several Unholy Worst Practices™. So whatever source you got it from is
not a good source of examples to learn from.
 
 
Cheers & hth.,
 
- Alf
 
--
Using Thunderbird as Usenet client, Eternal September as NNTP server.
Bo Persson <bop@gmb.dk>: Aug 13 05:33PM +0200

On 2015-08-13 09:16, Alf P. Steinbach wrote:
>> lead to me having a pointer to a pointer to my_data?
 
> It's just the design of `atomic_load` is imperfect, that it expects a
> pointer rather than a reference as argument.
 
The interface was supposed to be compatible with C, and a pointer is all
they have.
 
 
Bo Persson
"Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com>: Aug 13 11:00PM +0200

* 13-Aug-15 5:33 PM, Bo Persson:
> > pointer rather than a reference as argument.
 
> The interface was supposed to be compatible with C, and a pointer is all
> they have.
 
Well, 2 things wrong with that idea:
 
* The function is in namespace `std`, no such in C.
 
* There's no problem with the same function having binding as foo(T&) in
C++ and as foo(T*) in C; that's what language bindings are all about,
offering an interface that's suitable for the language.
 
 
Cheers & hth.,
 
- Alf
 
--
Using Thunderbird as Usenet client, Eternal September as NNTP server.
Chris Vine <chris@cvine--nospam--.freeserve.co.uk>: Aug 10 12:14AM +0100

On Sun, 9 Aug 2015 14:55:32 -0700 (PDT)
Doug Mika <dougmmika@gmail.com> wrote:
[snip]
> what each line did. And it was buggy on top of that. I mean, the
> error message the compiler threw at me, well, I didn't know what the
> problem was in the least.
 
It works if you pass std::move(myInt) to spawn_task() because that
converts the lvalue to a rvalue and this causes A in spawn_task() to
be deduced as int, which works. Obviously however, requiring the
argument to be passed only as an rvalue is completely wrong: it "works"
for that particular case only as a side effect of a defective design.
As you suggest, it would also compile for lvalues if you passed the
argument to std::thread's constructor via std::ref. However that would
also be completely wrong for this usage - first, it would no longer work
for rvalue arguments, and secondly you should almost never pass an
argument to std::thread by reference rather than by value because the
variable passed may be out of scope by the time it is accessed by the
thread concerned. (The last point would not be true here though because
your code blocks on std::future::get() within the scope of the int
argument, but that is just an artifact of your simplistic example.)
 
It is difficult to believe that the code you have posted is actually in
a published book. Perhaps you are "converting" C++98 code using boost
into C++11 code using the standard library, but not doing so
correctly - C++98 does not have rvalue references, which means that it
does not have std::move, std::forward or collapsible references. If the
code really was in a book in the form in which you have presented it,
throw it in the bin.
 
This is basic stuff about lvalue and rvalue types, perfect forwarding
and reference collapsing, and is not specific to threads. Any decent
book which purports to cover C++11 should deal with it. The other
point to make is that this is normally only an issue for library
writers. Your code is redundant by virtue of std::async.
 
Chris
Chris Vine <chris@cvine--nospam--.freeserve.co.uk>: Aug 10 11:10AM +0100

On Sun, 9 Aug 2015 19:10:43 -0700 (PDT)
Doug Mika <dougmmika@gmail.com> wrote:
[snip]
> multithreading. It's not an easy read, but some examples seem
> useful. Any suggestion on a good intro to intermediate level book
> for C++ multithreading? Anyone? (of course in C++11)
 
Although I have never read it, I have heard quite good things about that
book so it is a bit worrying that it should come up with a code listing
which not only does not compile but which shows such a lack of
understanding of rvalue references, move semantics and template type
deduction. Anyway, you now have a corrected version from me. I
suggest you submit an erratum to the publisher because as I say I have
heard that the book is reasonably good on threading matters.
 
To be honest though, spending your time looking at a book about
multi-threading is probably not wise for someone who has yet to acquire
the basics. If you want to operate at this low level, you need to
understand rvalue references and template type deduction to understand
the code, and not just the particulars about std::packaged_task and
std::future. The basic point is that with this function signature for
perfect forwarding:
 
template <class T> void func(T&& t) {...}
 
T deduces as a reference type if passed a lvalue and a value type if
passed a rvalue. That's how forwarding works. But it does mean that
you cannot use T in the same way as you could in the C++98 days if the
signature were, say
 
template <class T> void func(T& t) {...}
 
which works completely differently - here func can only take a lvalue
and T deduces as the underlying value type, either const or non-const.
 
template <class T> void func(T t) {...}
 
does similarly, except that it discards const qualifiers and will
accept rvalues as well as lvalues (and a signature of func(const T& t)
would do the same but would differ in its treatment of volatile).
 
The literature on this is not that good in my opinion. Section 23.5.2
and 23.5.2.1 of Stroustrup's the C++ Programming Language (4th ed) is
unnecessarily light in content in my view. The following link is a
great deal more complete, but consequently more difficult for a
beginner to understand:
http://en.cppreference.com/w/cpp/language/template_argument_deduction
 
Part of the problem is probably that in C++ the use of && (rvalue
reference) has been overloaded to cover perfect forwarding by a sleight
of hand involving reference collapsing. It might have been thought
cute at the time but it is highly confusing for beginners (and also for
others, it would appear).
 
I also repeat the point I made before. Most C++ users don't actually
need to know about the details of template type deduction. Mostly it
just works as you would expect. But be on your guard whenever you see a
forwarding reference, where sometimes it does not.
 
Chris
ram@zedat.fu-berlin.de (Stefan Ram): Aug 10 03:37PM

> { ::std::cout <<( i > 0 ? ", " : "" )<< x; });
>Where »i« is a loop counter, and »left« gives the
>number of iterations still left to be done.
 
The problem with int counters is that they can
overflow or underflow. So a single variable with
only few values might be more save:
 
1 first iteration
2 last iteration
3 first and last iteration
0 neither first nor last iteration
 
One also might consider having an optional lambda
that is to be called for the special case of an
empty container.
ram@zedat.fu-berlin.de (Stefan Ram): Aug 10 03:00PM

>( ::std::vector{ 5, 6, 7 },
> []( int const x ){ ::std::cout << ", " << x; },
> []( int const x ){ ::std::cout << x; })
 
Or, another possible interface:
 
myforeach
( ::std::vector{ 5, 6, 7 },
[]( int const x, int const i, int const left )
{ ::std::cout <<( i > 0 ? ", " : "" )<< x; });
 
Where »i« is a loop counter, and »left« gives the
number of iterations still left to be done.
ram@zedat.fu-berlin.de (Stefan Ram): Aug 10 02:53PM

>it seems that the "special case" where I can't use the
>new syntax (without paying the extra price) is for me
>more often the case than not.
 
It reminds my of copying a container to »::std::cout«:
 
::std::copy( ::std::begin( a ), ::std::end( a ),
::std::ostream_iterator< ::std::string >( ::std::cout, "\n" ))
 
. The above will /terminate/ each entry with »"\n"«.
But what if you want to /separate/ them with »","«?
 
You can write you own looper using lambdas:
 
myforeach
( container,
execute this lambda(x) for each entry,
execute this optional lambda(x) for the first entry,
execute this optional lambda(x) for the last entry )
 
giving nullptr for a optional lambda is the same as not
giving a value for it. If the second or third lambda is
not given then the first lambda is used for the first and
last entry, too, respectively.
 
E.g.,
 
myforeach
( ::std::vector{ 5, 6, 7 },
[]( int const x ){ ::std::cout << ", " << x; },
[]( int const x ){ ::std::cout << x; })
 
is intended to print »5, 6, 7«.
 
Disclaimer: I have not implemented this yet, so I am not
sure that it will work as intended.
ram@zedat.fu-berlin.de (Stefan Ram): Aug 10 06:59PM

>One also might consider having an optional lambda
>that is to be called for the special case of an
>empty container.
 
Here is a first implementation:
 
#include <iostream>
#include <ostream>
#include <functional> // ::std::function
#include <vector>
 
template< typename C >
bool foreach
( C const container,
::std::function< bool( typename C::value_type, bool, bool )> body )
{ auto const b = ::std::cbegin( container );
auto const e = ::std::cend( container );
bool first = true;
bool last = false;
auto next = b;
for( auto i = b; i != e; i = next )
{ if( next != e )++next;
if( next == e )last = true;
if( !body( *i, first, last ))return false;
first = false; }
return true; }
 
int main()
{ foreach
( ::std::vector< int >{ 4, 5, 6, 7 },
[]( int const i, bool const isfirst, bool const islast )
{ ::std::cout <<( isfirst ? "" : ", " )<< i <<( islast ? ".\n" : "" );
return true; } ); }
 
. This prints:
 
4, 5, 6, 7.
 
. However, having to write
 
[]( int const i, bool const isfirst, bool const islast )
 
in the client of »foreach« is rather cumbersome!
Jorgen Grahn <grahn+nntp@snipabacken.se>: Aug 09 10:38PM

On Sat, 2015-08-08, K. Frank wrote:
 
> for (auto x : collection) // do stuff with x;
 
> But lots of times you want to give slightly special
> treatment to the first or last element:
...
 
I noted this just like you did, but eventually concluded that "ok, so
I can't use the new syntax in that special case. The simplification
comes at a price."
 
/Jorgen
 
--
// Jorgen Grahn <grahn@ Oo o. . .
\X/ snipabacken.se> O o .
Jorgen Grahn <grahn+nntp@snipabacken.se>: Aug 10 01:51PM

On Mon, 2015-08-10, K. Frank wrote:
> it seems that the "special case" where I can't use the
> new syntax (without paying the extra price) is for me
> more often the case than not.
 
That's how it felt for me too (when I went through my hobby projects
and applied C++11 features like this one, as an exercise) but I think
in my case it was an illusion.
 
I /hope/ it is an illusion, because otherwise ranged-for is flawed.
It should be something that's frequently useful ...
 
And why would it be, given how useful it is in other languages like
shell script, Perl and Python?
 
> [...] the old-school "for (i = ...)"
> syntax does get the job done.
 
Yes, and with 'auto', std::begin() and so on, a lot of the ugliness
goes away.
 
/Jorgen
 
--
// Jorgen Grahn <grahn@ Oo o. . .
\X/ snipabacken.se> O o .
scott@slp53.sl.home (Scott Lurndal): Aug 10 08:21PM


> . However, having to write
 
>[]( int const i, bool const isfirst, bool const islast )
 
> in the client of »foreach« is rather cumbersome!
 
Man, that is unnecessarly complicated for such a simple
problem. Just use the interators directly and dump the
unreadable auto/lamda parts.
Bo Persson <bop@gmb.dk>: Aug 11 12:26AM +0200

On 2015-08-10 23:19, Doug Mika wrote:
 
> atomic<bool> b(true);
> b=false; //assignment operation which relies on the overloaded copy assignment operator.
 
> What is copy assignable and which operator does it rely on?
 
You are assigning a value, which is not a copy of an atomic variable.
Copy assign means assigning a value of the same type. Atomic types have
these operators deleted, to make them non-copyable.
 
atomic(const atomic&) = delete;
atomic& operator=(const atomic&) = delete;
atomic& operator=(const atomic&) volatile = delete;
 
 
Bo Persson
Ian Collins <ian-news@hotmail.com>: Aug 11 01:14PM +1200

Doug Mika wrote:
>> atomic& operator=(const atomic&) volatile = delete;
 
>> Bo Persson
 
> so which operator is used to assign a bool to an atomic, as in my case above?
 
atomic& operator=( T );
 
--
Ian Collins
Juha Nieminen <nospam@thanks.invalid>: Aug 10 08:25AM

> for (int i = 0; i < 4000000; ++i){
> char s[200];
> ::strncpy(s, "We few; we happy few; we band of brothers.", sizeof(s));
 
You are copying data from a string literal to a stack-allocated static array.
Of course it's going to be faster than allocating a string dynamically.
(And of course it should be done like that, if it suffices and if it indeed
requires the speed.)
 
Btw, are you sure the compiler isn't optimizing the loop away? After all,
it can see that 's' isn't doing anything. It can also see that the body
of the loop isn't using the loop variable nor has any side effects.
I wouldn't be surprised if the complier optimized the whole thing away.
 
For a more reliable (and fairer) comparison, change it so that the string
being built is of a length unknown at compile time, and the result is
used for something...
 
--- news://freenews.netfront.net/ - complaints: news@netfront.net ---
Barry Schwarz <schwarzb@dqel.com>: Aug 10 02:14AM -0700


>Omniorb uses gnu make scripts to build (with Cygwin), but I have not idea: How to force VC++ to include one of those directories?
 
>please help me, regards
>Szyk Cech
 
Please adjust your newsreader to limit your line length.
 
Since this is obviously not a standard header, you might have better
luck in a newsgroup that deals with Visual C++ or an appropriate
Microsoft forum.
 
--
Remove del for email
Anna Zrazhevska <rmannazr@gmail.com>: Aug 13 10:10AM -0700

About the client:
 
Headquartered in one of the most picturesque surroundings of Germany, our company invites IT specialists from all over the world. By now our team has been joined by professionals from over 50 countries. And we still have got a lot of room to grow. "Thinking without borders" is a business concept that puts us forth before the rest. If you ever dreamt to build a fabulous career, this is your chance. We are ready to help you professionally grow and explore new opportunities. During 30 years of company's existence we've achieved quite a number of awards which we are proud of. And surely we do have a rich experience to share.
 
Your role:
 
*Implement the right technologies and platforms in order to push forward the product, and yet, leave it user-friendly and straightforward;
*Learn new things and share new ideas with the browser team;
*Always work with a focus on security and privacy;
*Together with the rest of the team make contribution to the open-source projects;
*Make sure that a code you develop is accurate, clear and cross-platform;
*Be both, a good independent developer and a team player;
*Closely work with the rest team and share your working experience.
 
Your qualification:
 
*Either C++ or JavaScript knowledge;
*3-5 years experience in browser development (or at least building plugins for Chrome or Chromium);
*Advanced user of Windows, Mac and Linux;
*Don't be afraid to take responsibility for something;
*Excellent English knowledge, both written and spoken.
 
Additional information:
 
The company is located in a picturesque place of Germany, 7 km away from the shores of the Lake of Constance. Tettnang is not a big city, and yet it's a wonderful place to work and stay in. Living in Tettnang will give you a unique opportunity to visit some of the key European countries. It's located on the border of Switzerland and in 180 km away from Munchen. Such location makes Tettnang a nice place to move to. You will be able to freely travel and at the same time, most of the time live in a quiet suburban area of Germany. The Lake of Constance which Tettnang is famous for, lies on the borders of three European countries, Austria, Germany and Switzerland. You should definitely go out there with your family on a picnic. It's the lake (similarly to the company) that has got no borders. The three above countries didn't sign any agreement with regards to the geographic borders of the lake so they actually don't exist.
 
Contacts
 
For additional details on this role contact us - hire@relocateme.eu
For more information check relocateme.eu/open
Anna Zrazhevska <rmannazr@gmail.com>: Aug 13 09:58AM -0700

About the client:
 
Headquartered in one of the most picturesque surroundings of Germany, our company invites IT specialists from all over the world. By now our team has been joined by professionals from over 50 countries. And we still have got a lot of room to grow. "Thinking without borders" is a business concept that puts us forth before the rest. If you ever dreamt to build a fabulous career, this is your chance. We are ready to help you professionally grow and explore new opportunities. During 30 years of company's existence we've achieved quite a number of awards which we are proud of. And surely we do have a rich experience to share.
 
Your role:
 
*Implement the right technologies and platforms in order to push forward the product, and yet, leave it user-friendly and straightforward;
*Learn new things and share new ideas with the browser team;
*Always work with a focus on security and privacy;
*Together with the rest of the team make contribution to the open-source projects;
*Make sure that a code you develop is accurate, clear and cross-platform;
*Be both, a good independent developer and a team player;
*Closely work with the rest team and share your working experience.
 
Your qualification:
 
*Either C++ or JavaScript knowledge;
*3-5 years experience in browser development (or at least building plugins for Chrome or Chromium);
*Advanced user of Windows, Mac and Linux;
*Don't be afraid to take responsibility for something;
*Excellent English knowledge, both written and spoken.
 
Additional information:
 
The company is located in a picturesque place of Germany, 7 km away from the shores of the Lake of Constance. Tettnang is not a big city, and yet it's a wonderful place to work and stay in. Living in Tettnang will give you a unique opportunity to visit some of the key European countries. It's located on the border of Switzerland and in 180 km away from Munchen. Such location makes Tettnang a nice place to move to. You will be able to freely travel and at the same time, most of the time live in a quiet suburban area of Germany. The Lake of Constance which Tettnang is famous for, lies on the borders of three European countries, Austria, Germany and Switzerland. You should definitely go out there with your family on a picnic. It's the lake (similarly to the company) that has got no borders. The three above countries didn't sign any agreement with regards to the geographic borders of the lake so they actually don't exist.
 
Contacts
 
For additional details on this role contact us - hire@relocateme.eu
For more information check relocateme.eu/open
Doug Mika <dougmmika@gmail.com>: Aug 12 07:25PM -0700

So the compare_exchange_weak is defined as follows:
bool compare_exchange_weak( T& expected, T desired,
std::memory_order success,
std::memory_order failure );
where it atomically compares *this == expected and
*this==expected ==> *this=desired;
*this!=expected ==> expected=*this.
 
My question is, I can make sense of the condition evaluating to true and why we would want it, but why would we want expected=*this when we get false? Where is this used (How did they get the idea to let expected=*this if *this!=expected?)
"Lőrinczy Zsigmond" <zsiga@nospam.for.me>: Aug 13 01:18PM +0200

I think you are trying to ask about compare-and-swap mechanism,
which is an important tool in synchronization.
 
https://en.wikipedia.org/wiki/Compare-and-swap
 
A simpler version of this is test-and-set:
 
https://en.wikipedia.org/wiki/Test-and-set
Bo Persson <bop@gmb.dk>: Aug 13 05:38PM +0200

On 2015-08-13 04:25, Doug Mika wrote:
> *this==expected ==> *this=desired;
> *this!=expected ==> expected=*this.
 
> My question is, I can make sense of the condition evaluating to true and why we would want it, but why would we want expected=*this when we get false? Where is this used (How did they get the idea to let expected=*this if *this!=expected?)
 
The idea is to detect if 'expected' is unchanged since last time you
read it, and then update its value. If not, you might want to know what
has happened - like, has someone else changed the value? Into what?
 
 
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)