Tuesday, January 31, 2017

Digest for comp.lang.c++@googlegroups.com - 9 updates in 4 topics

woodbrian77@gmail.com: Jan 30 05:14PM -0800

> needs support for such long strings? Does the standard
> require that? I could live with 4 billion as a limit for the
> length of strings.
 
When string_view is 16 bytes it's probably a good idea
to use (lvalue) references with it. If it were 12 bytes,
taking it by value would be more palatable. And if I
understand correctly, taking it by rvalue reference
would be the same as taking it by value.
 
Are others interested in a 12 byte string_view?
 

Brian
Ebenezer Enterprises - "If I give to a needy soul, but don't
have love then who is poor?" for KING & COUNTRY
 
https://duckduckgo.com/?q=%22proof+of+your+love%22+king+and+country&t=ffsb&ia=videos&iax=1&iai=b-2dKOfbC9c
 
http://webEbenezer.net
"Öö Tiib" <ootiib@hot.ee>: Jan 31 12:52AM -0800

> understand correctly, taking it by rvalue reference
> would be the same as taking it by value.
 
> Are others interested in a 12 byte string_view?
 
We go back to such first grade basics now?
 
Imagine that we would only be content with up to 255 byte
view then 1 byte size would be fine? So sizeof string_view
would be 9? Wrong!
 
#include <iostream>
 
struct nah {void* ptr; uint8_t size;};

int main()
{
std::cout << "Size is still " << sizeof (nah)
<< " bytes, Brian.\n";
}
 
What it answers?
Why it is so? ;-)
scott@slp53.sl.home (Scott Lurndal): Jan 31 02:06PM


>> It seems though that putting the pointer first might help
>> in terms of preventing some padding in the type if the pointer
>> is 8 bytes and the length member is 4.
 
On linux systems, size_t is the same size as a pointer
(4 bytes on ia32, 8 bytes on x86_64). size_t must be a
type large enough to represent the entire physical address
space.
 
Can't speak to windows, but I'd find it unusual for size_t to be
4 bytes on any 64-bit system.
 
 
>> length of strings.
 
>When string_view is 16 bytes it's probably a good idea
>to use (lvalue) references with it.
 
Not necessarily, a processor specific ABI's may pass it
in a 128-bit SIMD register when passed by value, or it may
pass a 128-bit value in two integer 64-bit registers. e.g.
as required by the intel x86_64 psABI:
 
The classification of aggregate (structures and arrays) and union types works
as follows:
1. If the size of an object is larger than two eightbytes, or it contains unaligned
fields, it has class MEMORY.
2. If a C++ object has either a non-trivial copy constructor or a non-trivial
destructor 10 it is passed by invisible reference (the object is replaced in the
parameter list by a pointer that has class INTEGER). 11
3. If the size of the aggregate exceeds a single eightbyte, each is classified
separately. Each eightbyte gets initialized to class NO_CLASS.
4. Each field of an object is classified recursively so that always two fields are
considered. The resulting class is calculated according to the classes of the
fields in the eightbyte:
(a) If both classes are equal, this is the resulting class.
(b) If one of the classes is NO_CLASS, the resulting class is the other
class.
(c) If one of the classes is MEMORY, the result is the MEMORY class.
(d) If one of the classes is INTEGER, the result is the INTEGER.
(e) If one of the classes is X87, X87UP, COMPLEX_X87 class, MEM-
ORY is used as class.
(f) Otherwise class SSE is used.
5. Then a post merger cleanup is done:
(a) If one of the classes is MEMORY, the whole argument is passed in
memory.
(b) If SSEUP is not preceeded by SSE, it is converted to SSE.
 
 
 
 
>understand correctly, taking it by rvalue reference
>would be the same as taking it by value.
 
>Are others interested in a 12 byte string_view?
 
Nyet.
woodbrian77@gmail.com: Jan 31 08:43AM -0800

On Tuesday, January 31, 2017 at 2:52:15 AM UTC-6, Öö Tiib wrote:
> << " bytes, Brian.\n";
> }
 
> What it answers?
 
16.
 
> Why it is so? ;-)
 
I think it's due to alignment and arrays. In some cases, a reordering
of the data members can help reduce the size of a class, but not in
this case. Thank you for your reply.
 
 
Brian
Ebenezer Enterprises - In G-d we trust.
http://webEbenezer.net
scott@slp53.sl.home (Scott Lurndal): Jan 31 05:25PM


>I think it's due to alignment and arrays. In some cases, a reordering
>of the data members can help reduce the size of a class, but not in
>this case. Thank you for your reply.
 
It is so because the compiler is required to align members of structure (MoS)
on natural boundaries. The natural boundary for size_t and any pointer will
be 8-bytes (since both are 8-byte quantities) on modern 64-bit architectures.
 
If the uint8_t preceeds the pointer, then the compiler will need to allocate
7 filler bytes before the pointer. If the uint8_t follows the pointer, the
filler bytes will be added because the structure has a minimum alignment
derived from the largest minimum alignment of any MoS, which in this case is
again eight bytes (consider, for example, an array of this structure - for
the pointer to be aligned correctly in all elements of the array, each element
of the array must be a multiple of 8-bytes in size).
 
You can specify that the structure should be "packed" using implementation
defined mechanisms (__attribute__((packed)) in gcc, #pragma packed in other
compilers) if you really don't want padding between the fields (and are
prepared to take the substantial performance hit from accessing unaligned
data (which requires trapping and fixup on some architectures that don't
allow direct access to unaligned data), and causes substantial pipeline
bubbles on architectures that do support access to unaligned data).
 
The linux tool 'pahole' will extract the structure definition from the
DWARF data in the ELF executable and show where the holes are and how
large they are.
 
e.g.:
 
struct tm {
int tm_sec; /* 0 4 */
int tm_min; /* 4 4 */
int tm_hour; /* 8 4 */
int tm_mday; /* 12 4 */
int tm_mon; /* 16 4 */
int tm_year; /* 20 4 */
int tm_wday; /* 24 4 */
int tm_yday; /* 28 4 */
int tm_isdst; /* 32 4 */
 
/* XXX 4 bytes hole, try to pack */
 
long int tm_gmtoff; /* 40 8 */
const char * tm_zone; /* 48 8 */
 
/* size: 56, cachelines: 1, members: 11 */
/* sum members: 52, holes: 1, sum holes: 4 */
/* last cacheline: 56 bytes */
};
"Chris M. Thomasson" <invalid@invalid.invalid>: Jan 31 01:53PM -0800

On 1/31/2017 9:25 AM, Scott Lurndal wrote:
 
> It is so because the compiler is required to align members of structure (MoS)
> on natural boundaries. The natural boundary for size_t and any pointer will
> be 8-bytes (since both are 8-byte quantities) on modern 64-bit architectures.
 
Well, just to be safe: alignof(size_t)?
 
 
 
 
Juha Nieminen <nospam@thanks.invalid>: Jan 31 03:30PM

> delete [] answers; // <------- (1)
> delete answers; (2)
> }
 
This demonstrates why you should really avoid doing your own allocations,
if you can, and instead use the standard containers, if they suffice for
the task. std::vector does not only make your class much simpler to
implement, but also safer.
 
If you really, really need to do your own allocation, because the
standard containers just don't do what you need, then you have to
either disable or implement the copy constructor and assignment
operator of that class. Else you have a big problem leading to
multiple deallocations and accessing deallocated memory.
 
Disabling the copy constructor and assignment operator is the
easiest solution. But if you class really, really needs them enabled,
then it becomes quite a laborious task to implement them.
ram@zedat.fu-berlin.de (Stefan Ram): Jan 31 02:46PM

>Note that the original question was about the case where the character
>type is biggish, not `char` but perhaps `wchar_t` or `char32_t`.
 
I changed my code to that:
 
using tchar = char32_t;
using tstring = ::std::basic_string< tchar >;
 
static tchar first_unique_char_in( tstring const & s )
{ ::std::unordered_multiset< tchar >const chars( begin( s ), end( s ));
for( tchar const ch : s )
if( chars.count( ch ) == 1 )return ch;
return tchar{ 0 }; }
 
static tchar first_unique_char_of( tstring const & s )
{ auto const z = s.size();
auto i = z; for( i = 0; i < z; ++i )
{ tchar const ch = s[ i ]; bool found = false;
auto j = z; for( j = 0; j < z; ++j )
if( s[ j ]== ch && i != j ){ found = true; break; }
if( !found )return ch; }
return tchar{ 0 }; }
 
When the program runs, it blocks my computer. So, I cannot
afford to have it run for hours. So, the maximum feasible
length for a string for my tests is about 200'000. It gives
 
dti = 3317031700
dtf = 1800200
 
That means, in this case, »first_unique_char_of« is more
than 1000 times faster. (Unless I made an error, so feel
free to reproduce this.)
Jeff-Relf.Me <@.>: Jan 31 04:04AM -0800

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:

Monday, January 30, 2017

Digest for comp.lang.c++@googlegroups.com - 20 updates in 7 topics

Paul <pepstein5@gmail.com>: Jan 30 02:11AM -0800

On Sunday, January 29, 2017 at 7:15:20 PM UTC, Paavo Helde wrote:
...
> > }
 
> These multiple map find and lookup operations could be replaced by a
> single insert().
...
 
Thanks a lot for your feedback. I'm still not sure how to replace the
find and lookup operations by a single insert().
 
Could you (or someone else) possibly say a bit more about how to do this?
 
Many thanks,
Paul
"Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com>: Jan 30 12:00PM +0100

On 29.01.2017 15:31, Paul wrote:
> }
> return letters.front();
> }
 
I would do this:
 
[code]
#include <iostream>
#include <string> // std::basic_string
#include <iterator> // std::(begin, end)
#include <locale.h> // setlocale
#include <unordered_set> // std::unordered_multiset
 
#define TXT( s ) L ## s
 
using Char = decltype( TXT( ' ' ) );
using String = std::basic_string<Char>;
 
auto first_unique_char_in( String const& s )
-> Char
{
std::unordered_multiset<Char> const chars( begin( s ), end( s ) );
for( Char const ch : s )
{
if( chars.count( ch ) == 1 ) { return ch; }
}
return Char{ 0 };
}
 
auto main()
-> int
{
using namespace std;
setlocale( LC_ALL, "" );
wcout << first_unique_char_in( TXT( "Blah dah Bladihdah!" ) ) << endl;
}
[/code]
 
Cheers & hth.,
 
- Alf
Paul <pepstein5@gmail.com>: Jan 30 05:22AM -0800

On Monday, January 30, 2017 at 11:01:52 AM UTC, Alf P. Steinbach wrote:
> [/code]
 
> Cheers & hth.,
 
> - Alf
 
Thanks, Alf.
I'm a bit concerned that this appears to O(N * log(N)) where N is the
length of the string. I'm not saying that it's slower than my code,
by any means. However, solutions are always frowned upon if their
theoretical time complexities are suboptimal.
 
I have a more novice-friendly version of your idea below:
 
Paul
 
char findFirstUnique(const std::string& str)
{
std::unordered_multiset<char>word(str.begin(), str.end());
for(char c : str)
if(word.count(c) == 1)
return c;
 
std::cout << "No unique characters\n";
return 0;
}
Paavo Helde <myfirstname@osa.pri.ee>: Jan 30 04:24PM +0200

On 30.01.2017 12:11, Paul wrote:
> ...
 
> Thanks a lot for your feedback. I'm still not sure how to replace the
> find and lookup operations by a single insert().
 
E.g.
 
typedef std::unordered_map<char, std::list<char>::iterator> Map_t;
Map_t Map;
std::list<char> letters;
 
for (char letter : str) {
Map_t::iterator iter;
bool inserted;
 
std::tie(iter, inserted) =
Map.insert(std::make_pair(letter, letters.end()));
 
if (inserted) {
letters.push_back(letter);
iter->second = --letters.end();
} else if (iter->second != letters.end()) {
letters.erase(iter->second);
iter->second = letters.end();
}
}
Paavo Helde <myfirstname@osa.pri.ee>: Jan 30 04:38PM +0200

On 30.01.2017 15:30, Stefan Ram wrote:
> { if( rand() < RAND_MAX / 100 )break;
> s.push_back( set[ rand() %( sizeof( set )- 1 )] ); }
> v.push_back( s ); }}
 
If I am able to interpret this line noise correctly, then you are
claiming that a simple O(N*N) algorithm is performing better than a
O(N*log N) algorithm which is using more complex data structures.
 
This is the expected result, *for small N*. Increase your data size to
e.g. 10 times the L3 cache size, e.g. 80 MB, and test again.
scott@slp53.sl.home (Scott Lurndal): Jan 30 04:27PM


> I wrote another implementation which I called »first_unique_char_of«
> and a microbenchmark to show that under some circumstances it might
> seem to be faster.
 
It's completely unreadable.
Gareth Owen <gwowen@gmail.com>: Jan 30 07:04PM

> length of the string. I'm not saying that it's slower than my code,
> by any means. However, solutions are always frowned upon if their
> theoretical time complexities are suboptimal.
 
 
// Doesn't use a complicated data structure, but guaranteed O(n)
// Assumes CHAR_BIT is 8
char findFirstUnique(const std::string&str){
std::array<int,256> arr;
if(str.length() == 0) return 0;
for(int i=0;i < str.length(); ++i){
unsigned char ch = str[ch];
if(arr[ch] == 0) arr[ch] = i;
else arr[ch] = INT_MAX;
}
int minval=INT_MAX;
int minch = 0;
for(int i=0;i < 256; ++i){
if(arr[i] > 0 && arr[i] < INT_MAX) {
minval = arr[i];
minch = (char)i;
}
}
return minch;
}
Ian Collins <ian-news@hotmail.com>: Jan 31 08:14AM +1300

On 01/31/17 05:27 AM, Scott Lurndal wrote:
>> and a microbenchmark to show that under some circumstances it might
>> seem to be faster.
 
> It's completely unreadable.
 
I thought at first glance it was a post from that Relf bloke...
 
--
Ian
"Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com>: Jan 30 10:58PM +0100

On 30.01.2017 14:22, Paul wrote:
 
> Thanks, Alf.
> I'm a bit concerned that this appears to O(N * log(N)) where N is the
> length of the string.
 
Where on Earth did you get that idea?
 
Cheers!,
 
- Alf
"Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com>: Jan 30 11:10PM +0100

On 30.01.2017 20:04, Gareth Owen wrote:
>> theoretical time complexities are suboptimal.
 
> // Doesn't use a complicated data structure, but guaranteed O(n)
> // Assumes CHAR_BIT is 8
 
Note that the original question was about the case where the character
type is biggish, not `char` but perhaps `wchar_t` or `char32_t`.
 
 
> char findFirstUnique(const std::string&str){
> std::array<int,256> arr;
 
I don't think std::array has a defined default constructor. The original
Boost implementation was based on `array` being a POD so that it could
be initialized with C++03 curly braces. I think that's so still after
C++11, and if so then due to the assumption in the code below of zero
array values, you have Undefined Behavior.
 
 
> }
> return minch;
> }
 
 
Cheers!,
 
- Alf
Brett Dong <brett.browning.dong@gmail.com>: Jan 30 10:12PM +0800

I have a project that takes about five minutes to build with clang on
Linux (make -j4), optimization enabled (-Os). But it takes me ten
minutes and even more to build with Visual Studio 2015. I tried all the
ways on the Internet that can help reduce build time with Visual Studio:
turned off "Whole Program Optimization", turned off Link Time Code
Generation in the linker (/LTCG:OFF), even turned off any optimizations
in the linker (two options /OPT:REF and /OPT:ICF are turned off), and
turned off PDB debug information generation, turned on incremental
linking (/INCREMENTAL), turned on parallel compiling (/MP). After all
those efforts, it still takes me ten minutes to build the project. Twice
as long as the time clang uses! Why could there be so much difference?
 
I'm using a SSD, so IO shouldn't be a bottleneck. I'm using a 2-core
4-thread Broadwell-U processor FYI.
Paavo Helde <myfirstname@osa.pri.ee>: Jan 30 04:29PM +0200

On 30.01.2017 16:12, Brett Dong wrote:
> as long as the time clang uses! Why could there be so much difference?
 
> I'm using a SSD, so IO shouldn't be a bottleneck. I'm using a 2-core
> 4-thread Broadwell-U processor FYI.
 
Make sure you are using precompiled headers.
Ian Collins <ian-news@hotmail.com>: Jan 31 08:12AM +1300

On 01/31/17 03:12 AM, Brett Dong wrote:
> as long as the time clang uses! Why could there be so much difference?
 
> I'm using a SSD, so IO shouldn't be a bottleneck. I'm using a 2-core
> 4-thread Broadwell-U processor FYI.
 
Visual studio is rubbish at parallel builds: even their own people
recommend using a third party tool!
 
https://blogs.msdn.microsoft.com/visualstudio/2015/11/30/improving-your-build-times-with-incredibuild-and-visual-studio-2015/
 
I've used Incredibuild on single systems and distributed servers and it
works well.
 
--
Ian
legalize+jeeves@mail.xmission.com (Richard): Jan 30 06:23PM

[Please do not mail me a copy of your followup]
 
alexo <alessandro.volturno@libero.it> spake the secret code
 
>Too many "magic" numbers.
 
He is using ANSI escape sequences, which are well documented.
 
<https://en.wikipedia.org/wiki/ANSI_escape_code>
--
"The Direct3D Graphics Pipeline" free book <http://tinyurl.com/d3d-pipeline>
The Terminals Wiki <http://terminals-wiki.org>
The Computer Graphics Museum <http://computergraphicsmuseum.org>
Legalize Adulthood! (my blog) <http://legalizeadulthood.wordpress.com>
ram@zedat.fu-berlin.de (Stefan Ram): Jan 30 01:30PM

>auto first_unique_char_in( String const& s )
 
I wrote another implementation which I called »first_unique_char_of«
and a microbenchmark to show that under some circumstances it might
seem to be faster.
 
#include <cassert>
#include <chrono>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <iterator>
#include <ostream>
#include <string>
#include <vector>
#include <unordered_set>
 
using namespace ::std::literals;
 
static void escape( void * p )
{ asm volatile( "" : : "g"(p) : "memory" ); }
 
static char first_unique_char_in( ::std::string const& s )
{ ::std::unordered_multiset< char >const chars( begin( s ), end( s ));
for( char const ch : s )
if( chars.count( ch ) == 1 )return ch;
return char{ 0 }; }
 
static char first_unique_char_of( ::std::string const& s )
{ auto const z = s.size();
auto i = z; for( i = 0; i < z; ++i )
{ char const ch = s[ i ]; bool found = false;
auto j = z; for( j = 0; j < z; ++j )
if( i != j && s[ j ]== ch )found = true;
if( !found )return ch; }
return char{ 0 }; }
 
static void fill( ::std::vector< ::std::string >& v )
{ static const char set[] =
"0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz !";
for( int i = 0; i < 1000; ++i )
{ ::std::string s{};
while( true )
{ if( rand() < RAND_MAX / 100 )break;
s.push_back( set[ rand() %( sizeof( set )- 1 )] ); }
v.push_back( s ); }}
 
int main ()
{ ::std::srand( static_cast< unsigned int >( ::std::time( nullptr )));
::std::vector< ::std::string >v; fill( v );
{ ::std::chrono::high_resolution_clock::time_point t1;
::std::chrono::high_resolution_clock::time_point t2;
decltype( t2 - t1 )sum{};
t1 = ::std::chrono::high_resolution_clock::now();
escape( &t1 );
for( auto const & s: v )
{ auto result = first_unique_char_in( s );
escape( &result ); }
t2 = ::std::chrono::high_resolution_clock::now();
escape( &t2 );
sum += t2 - t1;
::std::cout << "dt = " <<( sum ).count() << '\n'; }
{ ::std::chrono::high_resolution_clock::time_point t1;
::std::chrono::high_resolution_clock::time_point t2;
decltype( t2 - t1 )sum{};
t1 = ::std::chrono::high_resolution_clock::now();
escape( &t1 );
for( auto const & s: v )
{ auto result = first_unique_char_of( s );
escape( &result ); }
t2 = ::std::chrono::high_resolution_clock::now();
escape( &t2 );
sum += t2 - t1;
::std::cout << "dt = " <<( sum ).count() << '\n'; }}
ram@zedat.fu-berlin.de (Stefan Ram): Jan 30 01:39PM

>if( i != j && s[ j ]== ch )found = true;
 
I now microoptimized the above line to
 
if( s[ j ]== ch && i != j ){ found = true; break; }
 
. And the result is that now »first_unique_char_of«
here is significanly faster, by a factor better than 5,
which in some cases is better than 10
ram@zedat.fu-berlin.de (Stefan Ram): Jan 30 02:16PM

>>if( i != j && s[ j ]== ch )found = true;
>if( s[ j ]== ch && i != j ){ found = true; break; }
 
I now added
 
for( auto const & s: v )
assert( first_unique_char_in( s )== first_unique_char_of( s ));
 
to have at least some verification.
 
I then added statistics for the lenght of the strings:
 
{ double l = 0; double c = 0;
for( auto const & s: v ){ l += s.length(); ++c; }
::std::cout << "average = " <<( l / c )<< '\n'; }
 
and it turned out that the average length is indeed
that number which happens to be 100 below:
 
if( rand() < RAND_MAX / 100 )break;
 
. I changed that to 1000 and 10000, and »first_unique_char_of«
still was faster by a factor better than 5, when I changed
it to 10 (and increased the size of the vector) the factor
became better than about 50.
Jeff-Relf.Me <@.>: Jan 30 03:04AM -0800

woodbrian77@gmail.com: Jan 29 07:23PM -0800

On Thursday, January 19, 2017 at 1:28:36 AM UTC-6, Öö Tiib wrote:
> constructors overloads some of what are templates themselves. So deducing
> two levels of template arguments from overloaded constructor call may
> mean some quite fragile and confusing heuristics.
 
I asked professor Spertus about this and he came up with this:
 
https://github.com/mspertus/p0433/commit/9e4643943eeee39b2cb4873026dad381d58cd50c
 
Using that, my program compiles and runs fine.
"Chris M. Thomasson" <invalid@invalid.invalid>: Jan 29 04:48PM -0800

>> A lot of the original crew hasn't shown up as often or at all anymore
>> though.
 
> I miss James Kanze.
 
Big time. Thank you for sparking the memories. :^)
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:

Sunday, January 29, 2017

Digest for comp.lang.c++@googlegroups.com - 22 updates in 9 topics

"Öö Tiib" <ootiib@hot.ee>: Jan 29 11:32AM -0800

> > A lot of the original crew hasn't shown up as often or at all anymore
> > though.
 
> I miss James Kanze.
 
Times are changing. Good is suppressed and disappearing but weird is
winning and dominating. There are less people like James Kanze but lot of
jeff-relfs, ramines and rick-c-hodgins everywhere.
Jorgen Grahn <grahn+nntp@snipabacken.se>: Jan 29 10:43PM

> On Friday, January 27, 2017 at 2:43:48 PM UTC-6, Christopher J. Pisz wrote:
>> On 1/27/2017 5:14 AM, JiiPee wrote:
>> > This is one of the best newsgroup I have been. Also been learning many
...
>> A lot of the original crew hasn't shown up as often or at all anymore
>> though.
 
> I miss James Kanze.
 
Me too.
 
/Jorgen
 
--
// Jorgen Grahn <grahn@ Oo o. . .
\X/ snipabacken.se> O o .
Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk>: Jan 29 10:48PM

On 29/01/2017 22:43, Jorgen Grahn wrote:
>>> though.
 
>> I miss James Kanze.
 
> Me too.
 
I also miss James Kanze even if he was an annoying cunt.
 
/Flibble
woodbrian77@gmail.com: Jan 29 01:38PM -0800


> But there should be support for appending a string_view to
> std::string. That seems to still be missing from gcc 7.0
> and clang 3.9.1. That's kind of frustrating.
 
I found support for this with gcc7 now. I had to use
-std=c++17 rather than the -std=c++1z that clang likes.
 
And I found a bug with my usage of string_view. I was passing
the results from it's "data" member function to a constructor
that takes a char const*. I knew that that function doesn't
guarantee to return a null terminated string, but forgot about
that.
 
This page says:
http://en.cppreference.com/w/cpp/experimental/basic_string_view/data
 
"Returns a pointer to the underlying character array. The pointer is such that the range [data(); data() + size()) is valid and the values in it correspond to the values of the view. (n.b. Unlike basic_string::data() and string literals, data() may return a pointer to a buffer that is not null-terminated. Therefore it is typically a mistake to pass data() to a routine that takes just a const CharT* and expects a null-terminated string.) "
 
One thing I would add to that is that is if you encounter this problem,
you might want to add a function that takes a string_view. If you
already have a string_view, then it's good to use that. That's what I did
in fixing the problem and it will help me avoid a few calls to strlen.
 
 
I've been looking at Clang and GCC's implementations of string_view.
 
This is from Clang 3.9.1:
 
private:
const value_type* __data;
size_type __size;
 
---------------------------
 
And this is from GCC 7.0
 
private:
// blah blah
size_t _M_len;
const _CharT* _M_str;
 
---------------------------
 
I think GCC's version is better in terms of the name _M_len
rather than __size.
 
It seems though that putting the pointer first might help
in terms of preventing some padding in the type if the pointer
is 8 bytes and the length member is 4. So maybe Clang's way
is better... I just wrote a little test program and the
size of string_view is 16 on both clang and gcc. But who
needs support for such long strings? Does the standard
require that? I could live with 4 billion as a limit for the
length of strings.



Brian
Ebenezer Enterprises - In G-d we trust.
http://webEbenezer.net
David Brown <david.brown@hesbynett.no>: Jan 29 10:27PM +0100

On 28/01/17 00:22, Alf P. Steinbach wrote:
> Sausage here. Of course in a matter of life and death we'll help you,
> but not for something less. I guess four months or so of normal behavior
> would suffice to forgive (but not forget) your behavior.
 
I don't approve of Rick's religious posts any more than anyone else
here. And it is a perfectly reasonable attitude to withhold help to
people who don't follow the rules of a newsgroup, at least roughly.
 
But Rick did start this thread with a reasonable C++ question. His
religious posting was a follow up to Mr. Flibble's post - which was a
clear and deliberate troll post knowing /exactly/ the reaction he was
going to provoke.
 
I have no idea what it would take to stop Rick bursting into religious
posts. But I /do/ know that posts like Mr. Flibble's certainly do not help.
Jeff-Relf.Me <@.>: Jan 29 04:34AM -0800

deplorable owl <owl@rooftop.invalid>: Jan 29 07:38PM

> Why would I manually run _your "blah" and "offon"
> when _my "X.EXE" does it all, automatically ? to wit:
 
It's not about what program you run to process the data. It's about
keeping the data in a flexible and compact form. The form you use for
input data requires at least five times as much space as would simply
keeping a record of timestamps, and also requires that any other program
that might want to make use of your data has to go through unnecessary
contortions.

 
> as it _only shows "When I slept" and "%OffLine"; to wit:
 
> http://Jeff-Relf.Me/SleepPat.PNG
> http://Jeff-Relf.Me/SleepPat.HTM
 
 
It's cleaner, but you lose information for days when you
might have slept fewer than 7 hours.
Snit <usenet@gallopinginsanity.com>: Jan 29 01:38PM -0700

On 1/29/17, 12:38 PM, in article hgvnbmfk98g.k@rooftop.invalid, "deplorable
> keeping a record of timestamps, and also requires that any other program
> that might want to make use of your data has to go through unnecessary
> contortions.
 
But you can script it and take more steps... which is what I noted was bad
and then you twisted to say I do not think scripting things to avoid work
makes sense.
 
Now you are in the position I was... no reason for him to not do things in a
more direct and logical way, eh?
 
 
--
Personal attacks from those who troll show their own insecurity. They cannot
use reason to show the message to be wrong so they try to feel somehow
superior by attacking the messenger.
 
They cling to their attacks and ignore the message time and time again.
Jeff-Relf.Me <@.>: Jan 29 12:44PM -0800

"Öö Tiib" <ootiib@hot.ee>: Jan 29 11:52AM -0800

On Friday, 27 January 2017 23:37:50 UTC+2, Ian Collins wrote:
> > need it, and who cares about the copy? It's an exception, which should
> > occur exceptionally.
 
> Indeed. The cost of throwing far outweighs the cost of generating a string.
 
The difference of 'const char* what() const' of 'std::exception'
from 'string_view' is basically that it is required to end with character
zero.
 
It likely feels major difference only because of Parkinson's law of
triviality. ;)
Paul <pepstein5@gmail.com>: Jan 29 06:31AM -0800

The code below is intended to return the value of the first-occurring
unique character in a string, and to return the null character if no
characters are unique. This can be done quite simply with a vector of
length 256 because the number of chars is small. Imagine that the char type
is huge. Is the below code correct and efficient or is there something
a bit unpleasant about it?
 
Many thanks,
Paul
 
#include <iostream>
#include <list>
#include <string>
#include <unordered_map>
 
char findFirstUnique(const std::string& str)
{
std::unordered_map<char, std::list<char>::iterator> Map;
std::list<char> letters;
for(char letter : str)
if(Map.find(letter) == Map.end())
{
letters.push_back(letter);
Map[letter] = --letters.end();
}
else if(Map[letter] != letters.end())
{
letters.erase(Map[letter]);
Map[letter] = letters.end();
}

if(letters.empty())
{
std::cout << "All letters duplicated";
return 0;
}

return letters.front();

}
Daniel <danielaparker@gmail.com>: Jan 29 10:18AM -0800

On Sunday, January 29, 2017 at 9:31:35 AM UTC-5, Paul wrote:
> characters are unique. This can be done quite simply with a vector of
> length 256 because the number of chars is small. Imagine that the char type
> is huge. Is the below code correct and efficient
 
Using maps or sets for this is going to be less efficient than sequence
containers. Also, I think you should be more explicit about the empty string or
all duplicates case. An alternative might be
 
std::pair<char,bool> findFirstUnique(const std::string& str)
{
std::string s(str);
std::sort(s.begin(), s.end());
 
bool unique = true;
 
auto prev = s.begin();
auto it = s.begin();
 
if (s.begin() != s.end())
{
++it;
bool done = false;
while (!done && it != s.end())
{
if (*it == *prev)
{
++it;
}
else if ((it - prev) == 1)
{
done = true;
}
else
{
prev = it;
++it;
}
}
}
return ((it - prev) == 1) ? std::make_pair(*prev,true) : std::make_pair(0,false);
}
 
Note, however, that a function like this would be mostly useless today because
an std::string would be expected to contain UTF-8 sequences, so you should
probably modify it to return the first unique UTF-8 sequence.
 
Daniel
Paul <pepstein5@gmail.com>: Jan 29 10:40AM -0800

On Sunday, January 29, 2017 at 6:18:41 PM UTC, Daniel wrote:
> an std::string would be expected to contain UTF-8 sequences, so you should
> probably modify it to return the first unique UTF-8 sequence.
 
> Daniel
 
Thanks for your thoughts, Daniel.
I should have said this before, but the context for the
question is my attempt to learn about Data Structures and Algorithms
for the purpose of performing well in job interviews.
 
Rightly or wrongly, solutions are always frowned upon which have
suboptimal worst-case time complexity. Sorting the string would be
heavily criticised for providing an O(N * log N) algorithm instead of an
O(N) algorithm where N is the string length.
 
 
Paul
Paul <pepstein5@gmail.com>: Jan 29 10:52AM -0800

On Sunday, January 29, 2017 at 6:18:41 PM UTC, Daniel wrote:
> an std::string would be expected to contain UTF-8 sequences, so you should
> probably modify it to return the first unique UTF-8 sequence.
 
> Daniel
 
I don't think this solves the same problem that I solved.
I meant that the task is to find the unique character that occurs
earliest. For example f("character") == 'h' because the non-repeaters
are 'h', 'e' and 't', and 'h' occurs at an earlier point in the string
than the other non-repeaters.
 
Paul
Paavo Helde <myfirstname@osa.pri.ee>: Jan 29 09:04PM +0200

On 29.01.2017 20:18, Daniel wrote:
> }
> return ((it - prev) == 1) ? std::make_pair(*prev,true) : std::make_pair(0,false);
> }
 
This is finding the smallest unique character, not the first occurring
one as specified in the task description.
 
std::sort() is also O(N*log N) which is worse than the OP's O(N) using
hash map operations which have average constant complexity.
 
Cheers
Paavo
Daniel <danielaparker@gmail.com>: Jan 29 11:06AM -0800

On Sunday, January 29, 2017 at 1:52:29 PM UTC-5, Paul wrote:
 
> I don't think this solves the same problem that I solved.
 
You're right. I replied too quickly.
 
Daniel
Paavo Helde <myfirstname@osa.pri.ee>: Jan 29 09:15PM +0200

On 29.01.2017 16:31, Paul wrote:
> letters.erase(Map[letter]);
> Map[letter] = letters.end();
> }
 
These multiple map find and lookup operations could be replaced by a
single insert(). Not sure the optimizer is able to do this by itself.
 
> }
 
> return letters.front();
 
> }
 
The algorithm itself seems OK, as std::list iterators are not
invalidated when deleting or adding other elements to the list. This
might actually be one of the very few valid usage cases for std::list I
have ever seen.
 
About performance: the requirement 'char type is huge' basically says
that a solution with a lookup array is infeasible, so something like a
hash map seems to be needed indeed.
 
I have some suspicions about the std::list still. It is a very expensive
data structure, each node requires separate dynamic allocation which is
slow, plus the nodes are not guaranteed to be compact in the memory
which makes accessing it yet slower. I would get rid of the list and
just use a hash map which counts the occurrences of characters. This
would mean two passes: first count the occurrences, then in the second
pass find the first character with count 1. My gut feeling tells me this
would be faster than messing with a std::list, but YMMV.
 
Cheers
Paavo
Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk>: Jan 29 03:47PM

abuse@glorb.com
 
/Flibble
"Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com>: Jan 29 05:29PM +0100

On 29.01.2017 16:47, Mr Flibble wrote:
> abuse@glorb.com
 
> /Flibble
 
I don't see his postings but I believe he's an old-time troll (if memory
serves). Whatever address he's posting from is one that let's him keep
on doing it. The best strategy may be to just silently killfile him.
 
Cheers!,
 
- Alf
alexo <alessandro.volturno@libero.it>: Jan 29 01:02PM +0100

Il 28/01/2017 21:40, Christiano ha scritto:
 
> }
 
> Reference:
> http://www.tldp.org/HOWTO/Bash-Prompt-HOWTO/c327.html
 
Too many "magic" numbers.
Thank you anyway,
 
this is the output compiled with Code::Block 16.01 - MingW compiler
under MS-Windows:
 
[2J
[0;0f
[0;31mH [0;32me [0;33ml [0;34ml [0;35mo [0;36m, [0;37m
[0;31mw [0;32mo [0;33mr [0;34ml [0;35md [0;36m. [0;37m. [0;31m. [0;32m
[10;30f:)...
 
Microsoft Visual Studio 17 RC doesn't evn compile it.
Paul <pepstein5@gmail.com>: Jan 28 05:08PM -0800

The code below is copied from a blog. Should the author have said
Guard(const Guard& other)=delete;
 
Does the const omission matter? I would have thought that the author's
code doesn't prevent copying. The version without the const is a different
function.
 
Paul
 
 
 
#include <iostream>
#include <thread>
 
class Guard
{
public:
Guard(std::thread& t)
: thread(t)
{ }

~Guard()
{
if (thread.joinable())
{
thread.join();
}
}

Guard(Guard& other)=delete;
Guard& operator=(const Guard& rhs)=delete;
 
private:
std::thread& thread;
};
 
void function()
{
std::cout << "I'm inside function." << std::endl;
}
 
int main()
{
std::thread t(function);
Guard guard(t);
 
return 0;
}
"Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com>: Jan 29 03:11AM +0100

On 29.01.2017 02:08, Paul wrote:
> Guard guard(t);
 
> return 0;
> }
 
In the formal there are four possible "copy" constructors: T(T&), T(T
const&), T(T volatile& ) and T(T const volatile&). Declaring any of them
prevents the automatic generation of a "copy constructor".
 
 
Cheers!,
 
- Alf
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:

雞年吉:祥


       好珍貴的畫冊，收集了那麼多歷代名畫家畫的雞，實在難得。特與欣賞中國畫的朋友共賞。
Posted by at No comments:

Saturday, January 28, 2017

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

alexo <alessandro.volturno@libero.it>: Jan 28 02:55PM +0100

Hi all,
I'd like to write a console program for a text-based game.
(I know it's overdated, but I like the console - it reminds me when I
started using computers). And probably I will be the only one to use it :(
 
Sometimes when the buffer on screen is too clumsy, thers the need to
clear the screen. I know of the system() function defined in the
<stdlib.h> header file, and I know that in MS-Windows I get what I want
calling system("cls").
 
I also need the program run under linux, were the system function would
be system("reset"). So my question is: is there a way to know from the
inside of a C/C++ program which OS is running it?
 
I could write something like:
 
 
 
#ifdef SOME_WINDOWS_VARIABLE
#define CLEARSCR() system("cls")
 
#ifdef SOME_LINUX_VARIABLE
#define CLEARSCR() system("rset")
 
 
and at need call generically CLEARSCR();
 
Thank you for your replies,
Alex
Paavo Helde <myfirstname@osa.pri.ee>: Jan 28 04:19PM +0200

On 28.01.2017 15:55, alexo wrote:
> #define CLEARSCR() system("cls")
 
> #ifdef SOME_LINUX_VARIABLE
> #define CLEARSCR() system("rset")
 
Why macros? What is wrong with functions?
 
> and at need call generically CLEARSCR();
 
For console programs there are some portable libraries like ncurses. But
if you just want to clear the screen then this would probably be an
overkill.
 
In practice, for telling apart Windows and Linux you could study some
environment variables like OS, OSTYPE, WINDIR etc. But do you really
need to distinguish them? Just run both cls and reset and be done.
 
system("cls 2>/dev/null");
system("reset 2>NUL");
 
hth
Paavo
alexo <alessandro.volturno@libero.it>: Jan 28 04:55PM +0100

Il 28/01/2017 15:19, Paavo Helde ha scritto:
> system("reset 2>NUL");
 
> hth
> Paavo
 
 
Hi Paavo,
thank you for your quick reply.
 
Maybe I was not as clear as I hoped.
What I need to do is to compile my sourcecode under windows and then
compiling take the same sourcecode (without modifying a thing) and under
linux. I'm too new to programming to make a cross-compilation.
 
The macro serves to generically say to the program: CLEARSCR()
If I'm under Windows it should expand to: system("cls"),
if I'm under linux it should expand to system("reset").
 
At least this would be my intention.
 
I'm studying PDcurses - it is portable. As far as I know ncurses is tied
to linux only (but I may be wrong).
 
Anyway this is not what I want. It is not my intention to build a Text
User Interface; it's just OK the output cout or printf put to the console.
 
thank you
Paavo Helde <myfirstname@osa.pri.ee>: Jan 28 06:20PM +0200

On 28.01.2017 17:55, alexo wrote:
> What I need to do is to compile my sourcecode under windows and then
> compiling take the same sourcecode (without modifying a thing) and under
> linux. I'm too new to programming to make a cross-compilation.
 
OK, I see you want to find out this at compile time. My earlier
suggestion was to just issue both commands, with any errors suppressed,
and not bother even to find out which platform you are on, neither at
compile or run time. But I see you insist on doing things "properly",
that's OK too.
 
There is no standard C++ way to find out the OS at the compile time
(presumably because C++ does not even require an OS to be present), but
in practice there are some predefined preprocessor macros which you can
check, e.g.
 
#if (defined (_WIN32) || defined (_WIN64))
void ClearScreen() {
system("cls");
}
#elif (defined (LINUX) || defined (__linux__))
void ClearScreen() {
system("reset");
}
#else
#error Unsupported platform.
Posted by at No comments:

Digest for comp.programming.threads@googlegroups.com - 3 updates in 3 topics

Ramine <toto@toto.net>: Jan 27 10:51PM -0500

Hello,
 
My Scalable Distributed Reader-Writer Mutex was updated, i have
optimized it more, and now it is faster.
 
Note please that you can configure my Scalable Distributed Reader-Writer
Mutex by uncommenting the defines options inside defines1.inc file
inside the zip file, you have 3 options, you can choose my
starvation-free scalable rwlock that spin wait by uncommenting the
option LW_RWLockX inside the defines1.inc file, and you can choose my
starvation-free scalable rwlock that is blocking and that is enegy
efficient by uncommenting the option RWLockX inside the defines1.inc,
the third option inside defines.inc file is the option RWLock and is a
scalable rwlock that is not starvation-free and that spin wait.
 
It's the same that you set my concurrent Skiplists from the defines1.inc
file.
 
You can download the Linux and the Windows versions from:
 
https://sites.google.com/site/aminer68/scalable-distributed-reader-writer-mutex
 
 
Thank you,
Amine Moulay Ramdane
Ramine <toto@toto.net>: Jan 27 10:07PM -0500

Hello,
 
 
About my projects in C++ and Object Pascal..
 
You have to know that i have also used the following method of testing
called black box testing:
 
https://en.wikipedia.org/wiki/Black-box_testing
 
This is why i have written this:
 
I have thoroughly tested and stabilized more my projects for many years,
and now i think that they are more stable and efficient, so i think that
you can be more confident with them, i have also followed the black box
testing also with them...
 
For race conditions , i think for an experienced programmer in parallel
programming like me, this is not a so difficult task to avoid race
conditions.
 
For sequential consistency i have also written this:
 
I have implemented my inventions with FreePascal and Delphi compilers
that don't reorder loads and stores even with compiler optimization, and
this is less error prone than C++ that follows a relaxed memory model
when compiled with optimization, so i have finally compiled my
algorithms implementations with FreePascal into Dynamic Link Libraries
that are used by C++ in a form of my C++ Object Synchronization Library.
 
So this is much easier to make a correct sequential consistency with
Delphi and Freepascal because it is less error prone.
 
Other than that you have to know that i am an experienced programmer in
parallel programming also, so i think that my projects are more stable
and fast.
 
You can download all my C++ and Object Pascal projects from:
 
https://sites.google.com/site/aminer68/
 
 
 
Thank you,
Amine Moulay Ramdane.
Ramine <toto@toto.net>: Jan 27 09:34PM -0500

Hello,
 
 
My C++ synchronization objects library was updated..
 
My scalable DRWLock and scalable DRWLockX were updated, i have optimized
them more, and now they are faster.
 
You can download the new updated Linux and the Windows versions from:
 
https://sites.google.com/site/aminer68/c-synchronization-objects-library
 
 
Thank you,
Amine Moulay Ramdane.
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.programming.threads+unsubscribe@googlegroups.com.
Posted by at No comments:
Subscribe to: Posts (Atom)