How to split a char array?

[Heinz-Mario Frühbeis]

Hi,

momentary I'm working on a Textbox and I had to remove a single char by
Backspace at cursor position...

So, if I have e.g. 'char mText[256];' and the string is 'Hallo', how can
I split, where e.g. cursor position == 3, to 'Hal' and 'lo'?

Currently my idea is to set 'mText[3] = '|'' and using 'strtok' with
char *ptr;
ptr = strtok(mText, "|");
.

But maybe there is a predefined / better way, a function?

Regards and Happy Easter
Heinz-Mario Frühbeis

[Ian Collins]

On 03/27/16 22:17, Heinz-Mario Frühbeis wrote:
> Hi,
>
> momentary I'm working on a Textbox and I had to remove a single char by
> Backspace at cursor position...
>
> So, if I have e.g. 'char mText[256];' and the string is 'Hallo', how can
> I split, where e.g. cursor position == 3, to 'Hal' and 'lo'?
>
> Currently my idea is to set 'mText[3] = '|'' and using 'strtok' with
> char *ptr;
> ptr = strtok(mText, "|");

> ..

Use std::string and substr(0,3).

--
Ian Collins

[Barry Schwarz]

On Sun, 27 Mar 2016 11:17:12 +0200, Heinz-Mario Frühbeis
<D...@Earlybite.individcore.de> wrote:

>Hi,
>
>momentary I'm working on a Textbox and I had to remove a single char by
>Backspace at cursor position...
>
>So, if I have e.g. 'char mText[256];' and the string is 'Hallo', how can
>I split, where e.g. cursor position == 3, to 'Hal' and 'lo'?
>
>Currently my idea is to set 'mText[3] = '|'' and using 'strtok' with
>char *ptr;
>ptr = strtok(mText, "|");

What do you want the result to be?

If you set mText[3] to '|' you will lose the second 'l'. After
strtok, your array will end up with two strings: "Hal" and "o",
perhaps better represented as "Hal\0o\0"

Your description implies you want "Hal\0lo\0". If that is the case,
and you are restricted to using an array of char instead of a
std::string, you can use memmove which will support overlapping source
and destination areas. Something like
set index to location of split (3 in your sample)
memmove(mText+(index+1), mText+index, sizeof mText - (index+1));
mText[index] = '\0';

--
Remove del for email

[Alf P. Steinbach]

On 27.03.2016 11:17, Heinz-Mario Frühbeis wrote:
>
> momentary I'm working on a Textbox and I had to remove a single char by
> Backspace at cursor position...
>
> So, if I have e.g. 'char mText[256];' and the string is 'Hallo', how can
> I split, where e.g. cursor position == 3, to 'Hal' and 'lo'?

It's probably better to use a std::string.

> Currently my idea is to set 'mText[3] = '|'' and using 'strtok' with
> char *ptr;
> ptr = strtok(mText, "|");

To remove the character at index 2 in zero-terminated string you can do

for( int i = strlen( mText ) - 1; i >= 2; --i )
{
mText[i] = mText[i+1];

}


> But maybe there is a predefined / better way, a function?

std::string


Cheers & hth.,

- Alf

[Heinz-Mario Frühbeis]

memmove is working well...
memmove(vText + (nCursorPos - 1), vText + (nCursorPos), nLen_of_Str -
(nCursorPos));
E.g.:
heinz (cursor behind i == 3) // I begin pos counting at 1
After Backspace:
henz
a.s.o

Thank you, sir!
Regards
Heinz-Mario Frühbeis

[Heinz-Mario Frühbeis]

I cannot (currently) use std::string as data type for the member var of
mText, because I (currently) have trouble with this and an event loop,
which is running in a pthread...
But maybe temporarly, but <again> memmove is working really fine.

Anyway, thank you, sir.

Regards
Heinz-Mario Frühbeis

[Heinz-Mario Frühbeis]

Am 27.03.2016 um 15:03 schrieb Alf P. Steinbach:
> On 27.03.2016 11:17, Heinz-Mario Frühbeis wrote:
>>
>> momentary I'm working on a Textbox and I had to remove a single char by
>> Backspace at cursor position...
>>
>> So, if I have e.g. 'char mText[256];' and the string is 'Hallo', how can
>> I split, where e.g. cursor position == 3, to 'Hal' and 'lo'?
>
> It's probably better to use a std::string.
>
>

Easier<?>. Do not know...

>> Currently my idea is to set 'mText[3] = '|'' and using 'strtok' with
>> char *ptr;
>> ptr = strtok(mText, "|");
>
> To remove the character at index 2 in zero-terminated string you can do
>
> for( int i = strlen( mText ) - 1; i >= 2; --i )
> {
> mText[i] = mText[i+1];
> }
>
>

But this is only working good/fast enough for small arrays...isn't it?

>> But maybe there is a predefined / better way, a function?
>
> std::string
>

Currently I've trouble with std::string for the member var (mText),
probably by an event loop running in a pthread and using a callback and
manipulating the string.

I think, I will use memmove. I love the style "bit pushing". :)

Anyway, thank you.
Regards
Heinz-Mario Frühbeis

[Jorgen Grahn]

On Sun, 2016-03-27, Heinz-Mario Frühbeis wrote:
> Am 27.03.2016 um 15:03 schrieb Alf P. Steinbach:
>> On 27.03.2016 11:17, Heinz-Mario Frühbeis wrote:
>>>
>>> momentary I'm working on a Textbox and I had to remove a single char by
>>> Backspace at cursor position...
>>>
>>> So, if I have e.g. 'char mText[256];' and the string is 'Hallo', how can
>>> I split, where e.g. cursor position == 3, to 'Hal' and 'lo'?
>>
>> It's probably better to use a std::string.
>>
>>
> Easier<?>. Do not know...

He's right.

IMO, the single place where you can gain the most from going from C to
C++, is when you start using std::string and the standard containers,
and the things around them (algorithms and iterators).

And there are almost never, IME, any reasons to fall back to the C
mechanisms.

...

>>> But maybe there is a predefined / better way, a function?
>>
>> std::string
>>
>
> Currently I've trouble with std::string for the member var (mText),
> probably by an event loop running in a pthread and using a callback and
> manipulating the string.
>
> I think, I will use memmove. I love the style "bit pushing". :)

At least use the modern C++ mechanism instead of memmove. That
would be std::copy or std::copy_backward.

/Jorgen

--
// Jorgen Grahn <grahn@ Oo o. . .
\X/ snipabacken.se> O o .

[Paavo Helde]

If you use multithreading then you need to synchronize access to shared
data anyway, be it std::string or char array. It might be that the
race-condition bugs manifest themselves less often with arrays, but this
does not mean they are not bugs.

And if you use proper synchronization, then there are no problems using
std::string as shared data.

Also note that strtok() is not guaranteed to be thread-safe and uses
hidden state behind the scenes, so it would be better to avoid it
altogether.

> I think, I will use memmove. I love the style "bit pushing". :)

It looks like you actually want comp.lang.c, not comp.lang.c++. A major
benefit of C++ over C is that one can get rid of things like fixed-size
arrays, memmove and strtok.

HTH
Paavo

[Heinz-Mario Frühbeis]

Am 27.03.2016 um 16:17 schrieb Jorgen Grahn:
> On Sun, 2016-03-27, Heinz-Mario Frühbeis wrote:
>> Am 27.03.2016 um 15:03 schrieb Alf P. Steinbach:
>>> On 27.03.2016 11:17, Heinz-Mario Frühbeis wrote:

[...]

>> I think, I will use memmove. I love the style "bit pushing". :)
>
> At least use the modern C++ mechanism instead of memmove. That
> would be std::copy or std::copy_backward.
>

I've made a little test and I noticed a weird<?> behaviour...:

[Ah first]:
Here
<http://www.cplusplus.com/reference/algorithm/copy/>
is to read:
#include <algorithm> // std::copy

But my Test-Prog is working with 'string.h', too. Why?

Now...

int main(){
char a[512];
char *b = a;
const char *nString = "Hallo";
copy(nString, nString + (strlen(nString)), b);
for(int i = 0; i < (int) strlen(b); ++i){
cout << b[i] << "\n";
}
cout << b << " " << strlen(b) << "\n";
cout.flush();
return 0;
}

Cout prints:
H
a
l
l
o
0 // 0 stands for '\0'
Hallo0 6

But:
int main(){
char a[512];
char *b = a;
const char *nString = "Hallo";
copy(nString, nString + (strlen(nString)), b);
cout << b << " " << strlen(b) << "\n";
cout.flush();
return 0;
}

Prints out:
Hallo 5

Why?

Regards
Heinz-Mario Frühbeis

[woodb...@gmail.com]

On Sunday, March 27, 2016 at 9:18:02 AM UTC-5, Jorgen Grahn wrote:
> On Sun, 2016-03-27, Heinz-Mario Frühbeis wrote:
> > Am 27.03.2016 um 15:03 schrieb Alf P. Steinbach:
> >> It's probably better to use a std::string.
> >>
> >>
> > Easier<?>. Do not know...
>
> He's right.
>
> IMO, the single place where you can gain the most from going from C to
> C++, is when you start using std::string and the standard containers,
> and the things around them (algorithms and iterators).
>

It's a short list in my opinion -- string, vector and deque.

> And there are almost never, IME, any reasons to fall back to the C
> mechanisms.

Probably std::array<char, n> works fine.

Brian
Ebenezer Enterprises - In G-d we trust.
http://webEbenezer.net

[Geoff]

Because your copy call results in undefined behavior. The contents of
the array will not be the zero-terminated string that strlen needs.
Both versions are erroneous and both result in UB. That you get 5 in
the second instance is a function of whether or not the array was
initialized with zeros or not.

You should probably begin by writing C++, not C.

int main() {
const std::string str = "Hallo";
std::string strn = str;
strn.erase(3, 1);
std::cout << strn.data() << " " << strn.length() << "\n";
std::cout.flush();
return 0;
}

[Heinz-Mario Frühbeis]

I difn't know that the zero.termination has to be set manually...
Thanks.

BTW: If I can use std::string, I will do that.

Regards
Heinz-MArio Frühbeis

#include <string.h>
//#include <algorithm>

using namespace std;

int main(){
char a[512];
char *b = a;
const char *nString = "Hallo";
copy(nString, nString + (strlen(nString)), b);

b[strlen(nString)] = '\0';
//for(int i = 0; i <= (int) strlen(b); ++i){

for(int i = 0; i < (int) strlen(b); ++i){

if(b[i] == '\0'){
cout << "A " << b[i] << "\n";
} else {
cout << "B " << b[i] << "\n";

}
}
cout << b << " " << strlen(b) << "\n";
cout.flush();
return 0;
}

Cout:
B H
B a
B l
B l
B o
A '\0'
Hallo 5

[Jens Thoms Toerring]

Heinz-Mario Frühbeis <D...@earlybite.individcore.de> wrote:
> Am 27.03.2016 um 16:17 schrieb Jorgen Grahn:
> > On Sun, 2016-03-27, Heinz-Mario Frühbeis wrote:
> >> Am 27.03.2016 um 15:03 schrieb Alf P. Steinbach:
> >>> On 27.03.2016 11:17, Heinz-Mario Frühbeis wrote:

> [...]

> >> I think, I will use memmove. I love the style "bit pushing". :)
> >
> > At least use the modern C++ mechanism instead of memmove. That
> > would be std::copy or std::copy_backward.
> >

> I've made a little test and I noticed a weird<?> behaviour...:

> [Ah first]:
> Here
> <http://www.cplusplus.com/reference/algorithm/copy/>
> is to read:
> #include <algorithm> // std::copy

> But my Test-Prog is working with 'string.h', too. Why?

> Now...

> int main(){
> char a[512];
> char *b = a;
> const char *nString = "Hallo";

This makes 'nString' point to a (const) array of char
with 6 elements, that contains the following elements

'H', 'a', 'l', 'l', 'o', '\0'

Note the terminating '\0' - otherwise it wouldn't be
a string. A C-style string is always a char arry that
conatains a '\0', indicating where the string ends. And
this terminating '\0' is used by all the functions that
operate on strings to find the end. Thus, if there's
no '\0' it's not a string and none of the functions that
accept strings as their arguments can be used!

The terminating '\0' is the only thing that indicates
the length of the strings - there's no "hidden" vari-
able where that information would be stored and could
be retrieved by the functions operating on strings!

That's an important difference to a std::string, which
does keep track of the length of a string by other means!
(That also means that you never can have a '\0' in a C-style
string - it would be interpreted as the end of the string -
while you can store '\0' characters in std::strings.)

> copy(nString, nString + (strlen(nString)), b);

Here you copy only 5 of the 6 elements from 'nString',
missing the trailing '\0' - strlen() only gives you the
number of non-'\0' characters in a string. So 'b' isn't
pointing to a string, but to a mere array of chars. What
comes after these 5 characters is pure random garbage
and you can't forsee what it will be.

What you need is

copy(nString, nString + strlen(nString) + 1, b);

to also copy the trailing '\0'. (And you also would
need to copy 6 characters when using memcpy() or the
exact same reason!)

> for(int i = 0; i < (int) strlen(b); ++i){
> cout << b[i] << "\n";
> }

This is wrong. Since you didn't copy the terminating '\0'
to what 'b' points to strlen() can't be used because what
'b' points to isn't a string (remember a char array only
is a string if it contains a '\0' somewhere!). Instead
strlen() will keep on running over the array (or even past
its end!) until it finds a '\0' somewhere by chance. Its
result thus is completely bogus. Consider that a primitive
implementation of strlen() may just look like this:

size_t strlen(const char * str) {
size_t len = 0;
while (*str++ != '\0')
len++;
return len;
}

Thus everything printed out after the first 5 chars is
simply garbage and may be different each time you run
your program.

> cout << b << " " << strlen(b) << "\n";

And neither this can work since it also will print out cha-
racters until, by chance, there's a '\0' in the memory some-
where after what 'b' points to.

> cout.flush();

By the way outputting a 'std::endl' will both print out a
'\n' and flush the stream.

> return 0;
> }

> Cout prints:
> H
> a
> l
> l
> o

> ?0 // 0 stands for '\0'
> Hallo0? 6

"?0' definitely doesn't stand for '\0'. '\0' can't be
printed. What you got there was some random garbage from
the mmeory pointed to by 'b' behind the 5 characters you
copied.

> But:
> int main(){
> char a[512];
> char *b = a;
> const char *nString = "Hallo";
> copy(nString, nString + (strlen(nString)), b);
> cout << b << " " << strlen(b) << "\n";
> cout.flush();
> return 0;
> }

> Prints out:
> Hallo 5

> Why?

Because what's in 'a' is random and one thing that can happen
is that the sixth element of 'a', when it's not initialized.
is a '\0'. So it may seem to work at times.

And, BTW, you don't need the 'b' variable at all, you
could simply use 'a' instead - in most places 'a', when
not followed by an index in square braces, is taken to
be a pointer to the first element of 'a'.

It looks a bit as if you're trying to learn C/C++ by experi-
mentation. That's the worst way because these are languages
where minor mistakes can have really bad consequences and
where there's something called "undefined behaviour" which
means that the same code can seem to work at one time and
fail the next or seem to work on one platform but fail on
a different one. And 'fail' can mean a lot more than just
the program crashing...
Regards, Jens
--
\ Jens Thoms Toerring ___ j...@toerring.de
\__________________________ http://toerring.de

[Mr Flibble]

On 28/03/2016 00:10, woodb...@gmail.com wrote:
> On Sunday, March 27, 2016 at 9:18:02 AM UTC-5, Jorgen Grahn wrote:
>> On Sun, 2016-03-27, Heinz-Mario Frühbeis wrote:
>>> Am 27.03.2016 um 15:03 schrieb Alf P. Steinbach:
>>>> It's probably better to use a std::string.
>>>>
>>>>
>>> Easier<?>. Do not know...
>>
>> He's right.
>>
>> IMO, the single place where you can gain the most from going from C to
>> C++, is when you start using std::string and the standard containers,
>> and the things around them (algorithms and iterators).
>>
>
> It's a short list in my opinion -- string, vector and deque.

Short list? ALL the containers have their uses.

/Flibble

[woodb...@gmail.com]

We've been over this a few times. I remember David Brown
posting two scenarios where he thought using std::list
makes sense. I don't remember the scenarios now, but I
remember thinking that the second one he mentioned
was kind of far-fetched. Recently one of Ian's posts
made it clear that std::set is just a std::list that's
sorted. I almost never use any of the standard
containers other than vector or deque.

I don't really disagree with Jorgen's point. String,
vector and deque are important. You don't get them
though without classes so classes are the big advantage
of C++ over C.

[Öö Tiib]

On Monday, 28 March 2016 19:43:59 UTC+3, woodb...@gmail.com wrote:
> On Monday, March 28, 2016 at 9:31:28 AM UTC-5, Mr Flibble wrote:
> > On 28/03/2016 00:10, woodb...@gmail.com wrote:
> > > On Sunday, March 27, 2016 at 9:18:02 AM UTC-5, Jorgen Grahn wrote:
> > >> IMO, the single place where you can gain the most from going from C to
> > >> C++, is when you start using std::string and the standard containers,
> > >> and the things around them (algorithms and iterators).
> > >>
> > >
> > > It's a short list in my opinion -- string, vector and deque.
> >
> > Short list? ALL the containers have their uses.
> >
>

> We've been over this a few times. I remember David Brown
> posting two scenarios where he thought using std::list
> makes sense. I don't remember the scenarios now, but I
> remember thinking that the second one he mentioned
> was kind of far-fetched.

Cheap split and merge of collections and persistent position of
an element in memory are the notable features of 'std::list'.
When such properties are not needed then other containers likely
fit better.

> Recently one of Ian's posts made it clear that std::set is just a
> std::list that's sorted.

What? Set is built upon weighted binary tree. There is too large
difference between sequence and tree.

> I almost never use any of the standard containers other than vector
> or deque.

May be you have limited use-cases?

>
> I don't really disagree with Jorgen's point. String,
> vector and deque are important. You don't get them
> though without classes so classes are the big advantage
> of C++ over C.

Flibble is correct that each container of standard library is performing
differently and so fits better than others into certain situations.
People tend to draw various decision charts how to choose
a container. http://i.stack.imgur.com/G70oT.png

[Geoff]

On Mon, 28 Mar 2016 11:30:34 +0200, Heinz-Mario Frühbeis

In that case, eliminate all the standard library calls, eliminate the
copy function and use the std::string member functions without
worrying about arrays and pointers and all the fiddly bits. :)

#include <iostream>
using namespace std; //DON'T do this in production code.

int main()
{

const char *nString = "Hallo";

// copy-construct string from C string constant
string strn = nString;
strn.insert(3, "|");
cout << strn.data() << " " << strn.length() << "\n";
string::size_type pos = strn.find("|");
strn.erase(pos, 1);
cout << strn.data() << " " << strn.length() << "\n";
string mystring = "llo";
pos = strn.find(mystring);
strn.insert(pos + mystring.length(), "|");
cout << strn.data() << " " << strn.length() << "\n";
cout.flush();
return 0;
}

[Mr Flibble]

On 28/03/2016 17:43, woodb...@gmail.com wrote:
> On Monday, March 28, 2016 at 9:31:28 AM UTC-5, Mr Flibble wrote:
>> On 28/03/2016 00:10, woodb...@gmail.com wrote:
>>> On Sunday, March 27, 2016 at 9:18:02 AM UTC-5, Jorgen Grahn wrote:
>>>> IMO, the single place where you can gain the most from going from C to
>>>> C++, is when you start using std::string and the standard containers,
>>>> and the things around them (algorithms and iterators).
>>>>
>>>
>>> It's a short list in my opinion -- string, vector and deque.
>>
>> Short list? ALL the containers have their uses.
>>
>> /Flibble
>
> We've been over this a few times.

You've been over this a few times and each time you are wrong.

/Flibble

[Ian Collins]

On 03/29/16 05:43, woodb...@gmail.com wrote:
>
> We've been over this a few times. I remember David Brown
> posting two scenarios where he thought using std::list
> makes sense. I don't remember the scenarios now, but I
> remember thinking that the second one he mentioned
> was kind of far-fetched. Recently one of Ian's posts
> made it clear that std::set is just a std::list that's
> sorted.

Did I? Where?

--
Ian Collins

[Daniel]

I think it was in the National Enquirer. Could be wrong.

Daniel

[woodb...@gmail.com]

On Monday, March 28, 2016 at 1:53:23 PM UTC-5, Öö Tiib wrote:
> On Monday, 28 March 2016 19:43:59 UTC+3, woodb...@gmail.com wrote:
> > On Monday, March 28, 2016 at 9:31:28 AM UTC-5, Mr Flibble wrote:
> > >
> > > Short list? ALL the containers have their uses.
> > >
> >
> > We've been over this a few times. I remember David Brown
> > posting two scenarios where he thought using std::list
> > makes sense. I don't remember the scenarios now, but I
> > remember thinking that the second one he mentioned
> > was kind of far-fetched.
>
> Cheap split and merge of collections and persistent position of
> an element in memory are the notable features of 'std::list'.
> When such properties are not needed then other containers likely
> fit better.
>
> > Recently one of Ian's posts made it clear that std::set is just a
> > std::list that's sorted.
>
> What? Set is built upon weighted binary tree. There is too large
> difference between sequence and tree.
>

They both make many more memory allocations compared to deque
or vector. They have more overhead related to their allocations
too. The same reasons people warn against using std::list
apply to std::set also.

> > I almost never use any of the standard containers other than vector
> > or deque.
>
> May be you have limited use-cases?
>

Sure.

> >
> > I don't really disagree with Jorgen's point. String,
> > vector and deque are important. You don't get them
> > though without classes so classes are the big advantage
> > of C++ over C.
>
> Flibble is correct that each container of standard library is performing
> differently and so fits better than others into certain situations.
> People tend to draw various decision charts how to choose
> a container. http://i.stack.imgur.com/G70oT.png

There's no mention of anything but standard containers there.
There are other containers that should be considered.
Maybe that chart has been around a long time and never updated.

Brian
Ebenezer Enterprises - If you can't join 'em, beat 'em.
http://webEbenezer.net

[Öö Tiib]

On Tuesday, 29 March 2016 04:22:10 UTC+3, woodb...@gmail.com wrote:
> On Monday, March 28, 2016 at 1:53:23 PM UTC-5, Öö Tiib wrote:
> > On Monday, 28 March 2016 19:43:59 UTC+3, woodb...@gmail.com wrote:
> > > On Monday, March 28, 2016 at 9:31:28 AM UTC-5, Mr Flibble wrote:
> > > >
> > > > Short list? ALL the containers have their uses.
> > > >
> > >
> > > We've been over this a few times. I remember David Brown
> > > posting two scenarios where he thought using std::list
> > > makes sense. I don't remember the scenarios now, but I
> > > remember thinking that the second one he mentioned
> > > was kind of far-fetched.
> >
> > Cheap split and merge of collections and persistent position of
> > an element in memory are the notable features of 'std::list'.
> > When such properties are not needed then other containers likely
> > fit better.
> >
> > > Recently one of Ian's posts made it clear that std::set is just a
> > > std::list that's sorted.
> >
> > What? Set is built upon weighted binary tree. There is too large
> > difference between sequence and tree.
> >
>
> They both make many more memory allocations compared to deque
> or vector. They have more overhead related to their allocations
> too. The same reasons people warn against using std::list
> apply to std::set also.

Situation can still be where that does not matter even with standard
allocator. Also both templates accept custom allocator. Without
profiling it can be hard to tell if sorted 'std::vector' or 'std::set'
is better but it is quite likely that sorted 'std::list' does lose to
both there.

>
> > > I almost never use any of the standard containers other than vector
> > > or deque.
> >
> > May be you have limited use-cases?
> >
>
> Sure.
>
> > >
> > > I don't really disagree with Jorgen's point. String,
> > > vector and deque are important. You don't get them
> > > though without classes so classes are the big advantage
> > > of C++ over C.
> >
> > Flibble is correct that each container of standard library is performing
> > differently and so fits better than others into certain situations.
> > People tend to draw various decision charts how to choose
> > a container. http://i.stack.imgur.com/G70oT.png
>
> There's no mention of anything but standard containers there.
> There are other containers that should be considered.
> Maybe that chart has been around a long time and never updated.

I am not claiming that the chart (or others like it) is somehow
pure and full truth. It just helps to make first pick from standard
library. For every single case something else can be better. For example
there are numerous containers and container adaptors in boost. I look at
boost mostly when I notice that standard container is likely inconvenient
for some reason or when I later notice that working with container takes
noteworthy time in application's profile. That however happens only with
one from 10 containers. For rest 9 from 10 the simple suggestion of such
chart is close enough to best.

[David Brown]

On 28/03/16 18:43, woodb...@gmail.com wrote:
> On Monday, March 28, 2016 at 9:31:28 AM UTC-5, Mr Flibble wrote:
>> On 28/03/2016 00:10, woodb...@gmail.com wrote:
>>> On Sunday, March 27, 2016 at 9:18:02 AM UTC-5, Jorgen Grahn wrote:
>>>> IMO, the single place where you can gain the most from going from C to
>>>> C++, is when you start using std::string and the standard containers,
>>>> and the things around them (algorithms and iterators).
>>>>
>>>
>>> It's a short list in my opinion -- string, vector and deque.
>>
>> Short list? ALL the containers have their uses.
>>
>> /Flibble
>
> We've been over this a few times. I remember David Brown
> posting two scenarios where he thought using std::list
> makes sense. I don't remember the scenarios now, but I
> remember thinking that the second one he mentioned
> was kind of far-fetched. Recently one of Ian's posts
> made it clear that std::set is just a std::list that's
> sorted. I almost never use any of the standard
> containers other than vector or deque.
>

I don't remember making such a post - but I don't remember /not/ making
such a post, so it is possible.

The different containers have their pros and cons. The ones you mention
here may be the most popular because they have a good balance for
general purpose usage, but that does not mean that the others are not
useful. In general, you pay for the features of the container. If you
are going to use those features, great - if not, it is a waste. So if
you need a simple sequence, your choices are:

std::array - very efficient, compile-time checking, but compile-time
fixed size.

std::deque - random access, but linear time insertion and removal, and
space costs.

std::list - simple and space efficient, but no random access

std::vector - fast access, but space inefficient and high worst-case
times for some operations


Then of course there are other container types such as the maps, queue
and stack, that have different features.

The C++ library standards group picked the containers as being a good
selection of general purpose, useful container types. They certainly
don't cover all possible types of container - but neither did the
authors think "all people /really/ need are vectors and deques. We'll
just throw in the others to make C++ hard, so that we can sell more books".

[Juha Nieminen]

woodb...@gmail.com wrote:
> They both make many more memory allocations compared to deque
> or vector. They have more overhead related to their allocations
> too. The same reasons people warn against using std::list
> apply to std::set also.

std::set (as well as std::map) is actually useful in practice.
std::list not so much. (I'm talking about quite long experience.
I have used the relational data containers quite a lot, but I don't
remember ever using std::list for anything in an actual project.)
The situations where std::list would be useful are so rare that
the standard library wouldn't actually lose much if it didn't have it.

Of course now that we have std::unordered_set (and std::unordered_map),
they are often better alternatives (although the ordered versions are
still useful in situations where you benefit from them being ordered,
eg. you need to traverse the elements in order. This can sometimes be
quite useful.)

Of course one should be aware of the amount of allocations and other
overhead that they have, and not use them spuriously. Know your tools.
On the other hand, they don't need to be religiously avoided either,
if they are the best tools for the task at hand. Just try not to
add/remove elements in tight inner loops that are run millions of
times, and you should be fine.

--- news://freenews.netfront.net/ - complaints: ne...@netfront.net ---

[Juha Nieminen]

David Brown <david...@hesbynett.no> wrote:
> std::vector - fast access, but space inefficient and high worst-case
> times for some operations

How exactly is std::vector space inefficient?

std::vector may cause some minor memory fragmentation if it needs to
reallocate a lot, but other than that, what exactly is "space
inefficient" about it?

[David Brown]

On 29/03/16 11:19, Juha Nieminen wrote:
> David Brown <david...@hesbynett.no> wrote:
>> std::vector - fast access, but space inefficient and high worst-case
>> times for some operations
>
> How exactly is std::vector space inefficient?
>
> std::vector may cause some minor memory fragmentation if it needs to
> reallocate a lot, but other than that, what exactly is "space
> inefficient" about it?
>

If you take a vector, and keep adding more to it, then when its current
allocated space is empty, it will re-allocate with a bigger size. Each
time this happens, the extra size increases. How much overhead this is
will depend on how fast the size increases, and the usage pattern for
the vector. But for a simple example, if the extra size was 40% each
allocation (thus doubling the vector size every two expansions), you
would have a 20% average wasted overhead.

[Juha Nieminen]

David Brown <david...@hesbynett.no> wrote:
> If you take a vector, and keep adding more to it, then when its current
> allocated space is empty, it will re-allocate with a bigger size. Each
> time this happens, the extra size increases. How much overhead this is
> will depend on how fast the size increases, and the usage pattern for
> the vector. But for a simple example, if the extra size was 40% each
> allocation (thus doubling the vector size every two expansions), you
> would have a 20% average wasted overhead.

If you have no idea how many elements there may be in the vector, that
may be so. On the other hand, if you know how many elements there will
be, you can either initialize them all at once, or use reserve() to
reserve an exact amount of space for them.

The way std::vector reallocates memory is, of course, done for
efficiency. It would be highly inefficient to reallocate one element
at a time (and insertion at the end of the vector would become a
linear-time operation rather than amortized constant-time.)

Note that std::deque may have similarly "wasted" space, because it
allocates memory in blocks. The newest block may have unused space
in it. How many % that is, depends on the size of the container and
the size of those blocks. (In fact, if you also insert at the beginning
of the container, there will also usually be unused space there as well.)
std::deque also requires some extra memory for the pointers to those
blocks, which is some (minor) overhead as well. And std::deque can't
be made to reserve exactly as much memory as needed for a given
amount of elements (unless you happen to hit an exact multiple
of the block size.)

[David Brown]

On 29/03/16 14:10, Juha Nieminen wrote:
> David Brown <david...@hesbynett.no> wrote:
>> If you take a vector, and keep adding more to it, then when its current
>> allocated space is empty, it will re-allocate with a bigger size. Each
>> time this happens, the extra size increases. How much overhead this is
>> will depend on how fast the size increases, and the usage pattern for
>> the vector. But for a simple example, if the extra size was 40% each
>> allocation (thus doubling the vector size every two expansions), you
>> would have a 20% average wasted overhead.
>
> If you have no idea how many elements there may be in the vector, that
> may be so. On the other hand, if you know how many elements there will
> be, you can either initialize them all at once, or use reserve() to
> reserve an exact amount of space for them.

Absolutely.

And if you are entirely sure how many elements there will be, you can
use a std::array.

I have nothing against vector, nor do I think it is particularly
inefficient. I am just pointing out that there are pros and cons to the
various container types, and it is wrong to say that vector and deque
are all that are ever needed.

[Mr Flibble]

On 29/03/2016 02:21, woodb...@gmail.com wrote:
> On Monday, March 28, 2016 at 1:53:23 PM UTC-5, Öö Tiib wrote:
>> On Monday, 28 March 2016 19:43:59 UTC+3, woodb...@gmail.com wrote:
>>> On Monday, March 28, 2016 at 9:31:28 AM UTC-5, Mr Flibble wrote:
>>>>
>>>> Short list? ALL the containers have their uses.
>>>>
>>>
>>> We've been over this a few times. I remember David Brown
>>> posting two scenarios where he thought using std::list
>>> makes sense. I don't remember the scenarios now, but I
>>> remember thinking that the second one he mentioned
>>> was kind of far-fetched.
>>
>> Cheap split and merge of collections and persistent position of
>> an element in memory are the notable features of 'std::list'.
>> When such properties are not needed then other containers likely
>> fit better.
>>
>>> Recently one of Ian's posts made it clear that std::set is just a
>>> std::list that's sorted.
>>
>> What? Set is built upon weighted binary tree. There is too large
>> difference between sequence and tree.
>>
>
> They both make many more memory allocations compared to deque
> or vector. They have more overhead related to their allocations
> too. The same reasons people warn against using std::list
> apply to std::set also.

std::deque also makes O(n) memory allocations like std::list and
std::set so you clearly do not know what you are talking about.

/Flibble

[Mr Flibble]

On 29/03/2016 10:16, Juha Nieminen wrote:
> woodb...@gmail.com wrote:
>> They both make many more memory allocations compared to deque
>> or vector. They have more overhead related to their allocations
>> too. The same reasons people warn against using std::list
>> apply to std::set also.
>
> std::set (as well as std::map) is actually useful in practice.
> std::list not so much. (I'm talking about quite long experience.
> I have used the relational data containers quite a lot, but I don't
> remember ever using std::list for anything in an actual project.)
> The situations where std::list would be useful are so rare that
> the standard library wouldn't actually lose much if it didn't have it.

Absolute bollocks mate; I use std::list slightly more than I use
std::set in my codebase: not all lists need to be ordered.

Just because YOU are unfamiliar with the common use-cases for std::list
does not mean that std::list is redundant.

/Flibble

[Alf P. Steinbach]

On 29.03.2016 15:48, Mr Flibble wrote:
> On 29/03/2016 10:16, Juha Nieminen wrote:
>> woodb...@gmail.com wrote:
>>> They both make many more memory allocations compared to deque
>>> or vector. They have more overhead related to their allocations
>>> too. The same reasons people warn against using std::list
>>> apply to std::set also.
>>
>> std::set (as well as std::map) is actually useful in practice.
>> std::list not so much. (I'm talking about quite long experience.
>> I have used the relational data containers quite a lot, but I don't
>> remember ever using std::list for anything in an actual project.)
>> The situations where std::list would be useful are so rare that
>> the standard library wouldn't actually lose much if it didn't have it.
>
> Absolute bollocks mate; I use std::list slightly more than I use
> std::set in my codebase: not all lists need to be ordered.

I would be interested in some concrete example. There is the splice
functionality, but for the general case it's O(n). Is it that you want
pointers and iterators to remain valid after insertions/deletions?

> Just because YOU are unfamiliar with the common use-cases for std::list
> does not mean that std::list is redundant.

True.

However I've been thinking of `std::list` as ~99.99% redundant for a
long time now, and I've not seen anyone arguing the opposite before now.


Cheers!,

- Alf

[Geoff]

On Tue, 29 Mar 2016 14:48:02 +0100, Mr Flibble <fli...@i42.co.uk>
wrote:

OK, let's see what the debate group turns up on this:

I have a project for analysis of RF intermodulation products.
Currently, the project is fundamentally C but is in process of
conversion to C++, as if there is any value to that. Be that as it
may, I have global transmitter and receiver arrays defined as:

#define MAX_ELEMENTS 1000

double Tx[MAX_ELEMENTS + 1];
double Rx[MAX_ELEMENTS + 1];

Arrays are indexed in the analysis section in (horrific to BartC)
'for' loops involving up to five index variables. The marker for the
end of the data is 0 for serialization but is not used to control
analysis.

The number of active elements in the arrays are adjusted and tracked
as elements are added/deleted by the user. Elements are always
inserted at the end of the arrays and are sorted numerically only when
initiated by the user. Removal shifts the elements downward from the
removal point.

Elements are optionally sorted using
std::sort(std::begin(Tx), std::begin(Tx) + Ttotal);
std::sort(std::begin(Rx), std::begin(Rx) + Rtotal);

Question, in converting to C++, should the arrays be converted to a
standard container such as a list?

What are the advantages/disadvantages?

[Mr Flibble]

On 29/03/2016 15:17, Alf P. Steinbach wrote:
> On 29.03.2016 15:48, Mr Flibble wrote:
>> On 29/03/2016 10:16, Juha Nieminen wrote:
>>> woodb...@gmail.com wrote:
>>>> They both make many more memory allocations compared to deque
>>>> or vector. They have more overhead related to their allocations
>>>> too. The same reasons people warn against using std::list
>>>> apply to std::set also.
>>>
>>> std::set (as well as std::map) is actually useful in practice.
>>> std::list not so much. (I'm talking about quite long experience.
>>> I have used the relational data containers quite a lot, but I don't
>>> remember ever using std::list for anything in an actual project.)
>>> The situations where std::list would be useful are so rare that
>>> the standard library wouldn't actually lose much if it didn't have it.
>>
>> Absolute bollocks mate; I use std::list slightly more than I use
>> std::set in my codebase: not all lists need to be ordered.
>
> I would be interested in some concrete example. There is the splice
> functionality, but for the general case it's O(n). Is it that you want
> pointers and iterators to remain valid after insertions/deletions?

Yes the primary reason I use std::list is for stable element references
and iterators: std::list elements have "identity" unlike std::vector
elements for example. Other reasons I use std::list are the occasional
use of the splice functionality and fast insert/erase in the middle
(assuming one already has an iterator to the middle).

/Flibble

[Paavo Helde]

If it works and there is no need to add features or change
functionality, then there is not much reason to convert anything.

OTOH, if there is a need to change any related functionality, then it
would probably be a good idea to change the arrays to a standard
container, just in order to simplify the changes and later maintenance.

The choice of the container depends on the needs: if performance is
critical, then probably std::vector will do. If performance is not
critical and you want to get rid of manual sort-trim step, then use
std::set which keeps the elements in sorted order all the time.

With std::vector, sorting and removing would then become:

std::sort(Tx.begin(), Tx.end());
Tx.resize(newsize);

Benefits:
- no arbitrary limit of 1000 elements
- no fear of buffer overrun
- no need to track the actual size in a separate variable
- elements may move in memory so there would be no temptation to
create long-living pointers to them and complicate the code.
- serialization terminator does not fit here any more and should be
thrown out of the array, making the code clearer.

Drawbacks:
- a couple of dynamic allocations in total (might cost some
microseconds).
- elements may move in memory so one cannot create long-living
pointers to them.
- serialization needs to be rewritten a bit to work without the
terminator.

std::list is useful only if the elements have identity (i.e. their
address is important) or you need things like splice. In this usage
scenario I do not see any need to use std::list, it would just combine
the worst properties of std::vector and std::set (for this scenario).

hth
Paavo

[woodb...@gmail.com]

On Tuesday, March 29, 2016 at 7:33:45 AM UTC-5, David Brown wrote:
> On 29/03/16 14:10, Juha Nieminen wrote:
> > David Brown <david...@hesbynett.no> wrote:
> >> If you take a vector, and keep adding more to it, then when its current
> >> allocated space is empty, it will re-allocate with a bigger size. Each
> >> time this happens, the extra size increases. How much overhead this is
> >> will depend on how fast the size increases, and the usage pattern for
> >> the vector. But for a simple example, if the extra size was 40% each
> >> allocation (thus doubling the vector size every two expansions), you
> >> would have a 20% average wasted overhead.
> >
> > If you have no idea how many elements there may be in the vector, that
> > may be so. On the other hand, if you know how many elements there will
> > be, you can either initialize them all at once, or use reserve() to
> > reserve an exact amount of space for them.
>
> Absolutely.
>
> And if you are entirely sure how many elements there will be, you can
> use a std::array.
>
> I have nothing against vector, nor do I think it is particularly
> inefficient. I am just pointing out that there are pros and cons to the
> various container types, and it is wrong to say that vector and deque
> are all that are ever needed.
>

After vector and deque I prefer to use non-standard containers.
One thing that's nice about writing on line services is you have
more flexibility in what you can use compared to some apps.

Brian
Ebenezer Enterprises
http://webEbenezer.net

[Paavo Helde]

On 29.03.2016 9:16, David Brown wrote:
> std::list - simple and space efficient, but no random access
>
> std::vector - fast access, but space inefficient and high worst-case
> times for some operations

std::list allocates each element dynamically and adds forth-and-back
pointers. This would mean e.g. 32 bytes overhead for *each* element in
64-bit builds. I would not call this "space efficient" in any sense.

For example, a million-element container of doubles might take 40MB with
std::list and 12 MB with a 50% over-allocated std::vector.

(Not to speak about that the processing of compactly placed array in
std::vector would be many times faster than the scattered data in
std::list.)

Cheers
Paavo

[woodb...@gmail.com]

On Tuesday, March 29, 2016 at 2:16:14 AM UTC-5, David Brown wrote:
>
> I don't remember making such a post - but I don't remember /not/ making
> such a post, so it is possible.

Now I'm wondering if it was Chris Vine. Sorry.

Brian

[Scott Lurndal]

Paavo Helde <myfir...@osa.pri.ee> writes:
>On 29.03.2016 9:16, David Brown wrote:
>> std::list - simple and space efficient, but no random access
>>
>> std::vector - fast access, but space inefficient and high worst-case
>> times for some operations
>
>std::list allocates each element dynamically and adds forth-and-back
>pointers. This would mean e.g. 32 bytes overhead for *each* element in
>64-bit builds. I would not call this "space efficient" in any sense.

Surely 16 bytes (8 for flink, 8 for blink). If the element stored in the
list is 320 bytes, then it's not a significant overhead (just 5%).

>
>For example, a million-element container of doubles might take 40MB with
>std::list and 12 MB with a 50% over-allocated std::vector.

Contrived example? Why would you use a std::list for doubles?

[Paavo Helde]

On 29.03.2016 19:42, Scott Lurndal wrote:
> Paavo Helde <myfir...@osa.pri.ee> writes:
>> On 29.03.2016 9:16, David Brown wrote:
>>> std::list - simple and space efficient, but no random access
>>>
>>> std::vector - fast access, but space inefficient and high worst-case
>>> times for some operations
>>
>> std::list allocates each element dynamically and adds forth-and-back
>> pointers. This would mean e.g. 32 bytes overhead for *each* element in
>> 64-bit builds. I would not call this "space efficient" in any sense.
>
> Surely 16 bytes (8 for flink, 8 for blink).

You are forgetting the dynamic allocation service block.

> If the element stored in the
> list is 320 bytes, then it's not a significant overhead (just 5%).
>
>>
>> For example, a million-element container of doubles might take 40MB with
>> std::list and 12 MB with a 50% over-allocated std::vector.
>
> Contrived example? Why would you use a std::list for doubles?

I wouldn't, and this space inefficiency is one one of the reasons why
std::list of doubles would not make sense (the main reason would be of
course that a million of dynamic allocations would be quite slow).

I have not yet found a usage case for std::list. If I have identity
objects they are allocated dynamically and accessed via smartpointers,
and smartpointers are best held in a std::vector or std::deque, in my
(definitely limited) experience.

Cheers
Paavo

[Geoff]

On Tue, 29 Mar 2016 18:36:05 +0200, Paavo Helde
<myfir...@osa.pri.ee> wrote:

>> Question, in converting to C++, should the arrays be converted to a
>> standard container such as a list?
>>
>> What are the advantages/disadvantages?
>
>If it works and there is no need to add features or change
>functionality, then there is not much reason to convert anything.
>

It works very well and there are no features to add.

>OTOH, if there is a need to change any related functionality, then it
>would probably be a good idea to change the arrays to a standard
>container, just in order to simplify the changes and later maintenance.
>
>The choice of the container depends on the needs: if performance is
>critical, then probably std::vector will do. If performance is not
>critical and you want to get rid of manual sort-trim step, then use
>std::set which keeps the elements in sorted order all the time.
>
>With std::vector, sorting and removing would then become:
>
> std::sort(Tx.begin(), Tx.end());
> Tx.resize(newsize);

This would be most likely, since access speed to the array is critical
to the speed of the computations.

>
>Benefits:
> - no arbitrary limit of 1000 elements
> - no fear of buffer overrun
> - no need to track the actual size in a separate variable

These reasons we in my mind while considering the question.

> - elements may move in memory so there would be no temptation to
>create long-living pointers to them and complicate the code.
> - serialization terminator does not fit here any more and should be
>thrown out of the array, making the code clearer.
>
>Drawbacks:
> - a couple of dynamic allocations in total (might cost some
>microseconds).
> - elements may move in memory so one cannot create long-living
>pointers to them.
> - serialization needs to be rewritten a bit to work without the
>terminator.
>

The 1000 limit was chosen to limit the study. As it stands, a 1000 x
1000 array can take dozens of hours to compute all the products on a
modern platform. Back when this was written, a 400MHz i486 was a fast
machine and it would take several days.

>std::list is useful only if the elements have identity (i.e. their
>address is important) or you need things like splice. In this usage
>scenario I do not see any need to use std::list, it would just combine
>the worst properties of std::vector and std::set (for this scenario).

I think I'd have to test and measure the speeds of analysis of an
array compared with a std::vector before committing to it.

Thank you for your well-considered reply.

[Juha Nieminen]

Mr Flibble <fli...@i42.co.uk> wrote:
>> std::set (as well as std::map) is actually useful in practice.
>> std::list not so much. (I'm talking about quite long experience.
>> I have used the relational data containers quite a lot, but I don't
>> remember ever using std::list for anything in an actual project.)
>> The situations where std::list would be useful are so rare that
>> the standard library wouldn't actually lose much if it didn't have it.
>
> Absolute bollocks mate; I use std::list slightly more than I use
> std::set in my codebase: not all lists need to be ordered.
>
> Just because YOU are unfamiliar with the common use-cases for std::list
> does not mean that std::list is redundant.

I am perfectly aware of how linked lists work, and what their advantages
and disadvantages are.

Yet, I have not used std::list since forever, for the simple reason that
I have never needed it. I remember using it in one serious project for
university, where it was actually necessary (the algorithm in question was
explicitly designed to work with fast splicing of linked lists). But
that's about it.

The problem with std::list is that it consumes more memory, adding
elements to it is slower (because memory allocation is slow), and it
easily gets fragmented in memory, potentially adding to the slowness
of even element access. (This slowness does not technically speaking
affect its asymptotic complexity, but slowness is slowness.)

Perhaps you are too reliant on pointers/iterators all over the place,
outliving their creation scope?

[Juha Nieminen]

Mr Flibble <fli...@i42.co.uk> wrote:
> std::deque also makes O(n) memory allocations like std::list and
> std::set so you clearly do not know what you are talking about.

But std::deque makes n/x memory allocations while std::list makes n.
That makes a big difference in efficiency.

[Heinz-Mario Frühbeis]

Am 28.03.2016 um 22:12 schrieb Geoff:
> On Mon, 28 Mar 2016 11:30:34 +0200, Heinz-Mario Frühbeis
> <D...@Earlybite.individcore.de> wrote:
>
>> Am 28.03.2016 um 01:39 schrieb Geoff:
>>> On Sun, 27 Mar 2016 22:13:10 +0200, Heinz-Mario Frühbeis
>>> <D...@Earlybite.individcore.de> wrote:
>>>
>>>> Am 27.03.2016 um 16:17 schrieb Jorgen Grahn:
>>>>> On Sun, 2016-03-27, Heinz-Mario Frühbeis wrote:
>>>>>> Am 27.03.2016 um 15:03 schrieb Alf P. Steinbach:
>>>>>>> On 27.03.2016 11:17, Heinz-Mario Frühbeis wrote:
>
[...]
> In that case, eliminate all the standard library calls, eliminate the
> copy function and use the std::string member functions without
> worrying about arrays and pointers and all the fiddly bits. :)
>
> #include <iostream>
> using namespace std; //DON'T do this in production code.
>
> int main()
> {
> const char *nString = "Hallo";
>
> // copy-construct string from C string constant
> string strn = nString;
> strn.insert(3, "|");
> cout << strn.data() << " " << strn.length() << "\n";
> string::size_type pos = strn.find("|");
> strn.erase(pos, 1);
> cout << strn.data() << " " << strn.length() << "\n";
> string mystring = "llo";
> pos = strn.find(mystring);
> strn.insert(pos + mystring.length(), "|");
> cout << strn.data() << " " << strn.length() << "\n";
> cout.flush();
> return 0;
> }
>

std::string (of its own; not c_str) is *not thread safe...
Yes, you can store a member var as std::string, but e.g. within a
callback function e.g. from a loop which is runnnung in a pthread, you
can only use c_str, also *not length(). Else, undef behaviour, or even
crash...

[Alf P. Steinbach]

I'm sorry, that's bollocks. The threading issues are the same with
`std::string` as with C style strings. If some code is unsafe with the
former, then its unsafe with the latter, and vice versa, except that its
easier to introduce bugs with C style strings.

Cheers & hth.,

- Alf

[Heinz-Mario Frühbeis]

Here, I have a XLib-Event-Loop running in a pthread and *every access on
std::string in a callback-function from this loop results in an error,
except I'm using c_str!

E.g.:
std::string string_var;
if(string_var.length() > 0){ // ERROR
}
if(strlen(string_var.c_str) > 0){ // NO ERROR
}

if(string_var == "HALLO"() > 0){ // ERROR
}
if(string_var.c_str == "HALLO"){ // NO ERROR
}

To me, it seems to be the same behaviour like XLib has...

Regards
Heinz-Mario Frühbeis

[Öö Tiib]

You seem to claim that 'char' array is more thread safe than 'std::string'.
That is dangerous nonsense. Only very few things that are immutable
whole program run are thread safe (constexpr, static const and string
literals). In C++ it is *possible* to make rest of things thread safe.
However that is it. Read up on C++ memory model.

[Öö Tiib]

Huh? What you now posted should not compile in C++.
It seems full of strange syntax errors.
There must be no way to run it. Stop the nonsense, please.

[Mr Flibble]

On 30/03/2016 07:22, Juha Nieminen wrote:
> Mr Flibble <fli...@i42.co.uk> wrote:
>> std::deque also makes O(n) memory allocations like std::list and
>> std::set so you clearly do not know what you are talking about.
>
> But std::deque makes n/x memory allocations while std::list makes n.
> That makes a big difference in efficiency.

x is a constant though so it makes no difference as far as algorithmic
"efficiency" (complexity) is concerned.

/Flibble

[Mr Flibble]

On 30/03/2016 07:19, Juha Nieminen wrote:
> Mr Flibble <fli...@i42.co.uk> wrote:
>>> std::set (as well as std::map) is actually useful in practice.
>>> std::list not so much. (I'm talking about quite long experience.
>>> I have used the relational data containers quite a lot, but I don't
>>> remember ever using std::list for anything in an actual project.)
>>> The situations where std::list would be useful are so rare that
>>> the standard library wouldn't actually lose much if it didn't have it.
>>
>> Absolute bollocks mate; I use std::list slightly more than I use
>> std::set in my codebase: not all lists need to be ordered.
>>
>> Just because YOU are unfamiliar with the common use-cases for std::list
>> does not mean that std::list is redundant.
>
> I am perfectly aware of how linked lists work, and what their advantages
> and disadvantages are.
>
> Yet, I have not used std::list since forever, for the simple reason that
> I have never needed it. I remember using it in one serious project for
> university, where it was actually necessary (the algorithm in question was
> explicitly designed to work with fast splicing of linked lists). But
> that's about it.

If you have only used std::list once in your entire career then it is
painfully obvious that you are not aware of (or stubbornly ignore) its
advantages.

>
> The problem with std::list is that it consumes more memory, adding
> elements to it is slower (because memory allocation is slow), and it
> easily gets fragmented in memory, potentially adding to the slowness
> of even element access. (This slowness does not technically speaking
> affect its asymptotic complexity, but slowness is slowness.)

std::set, std::multiset, std::map and std::multimap also have a single
node based allocation strategy so are you suggesting we shouldn't use
these containers either as they are "slow"? Besides, the allocation
problems of which you speak can be mostly mitigated against through the
use of a custom allocator such as one of the Boost pool allocators which
should, IMO, be part of C++.

>
> Perhaps you are too reliant on pointers/iterators all over the place,
> outliving their creation scope?

No more than I should be.

/Flibble

[Geoff]

On Wed, 30 Mar 2016 09:58:54 +0200, Heinz-Mario Frühbeis

If you are using memmove or strlen without obtaining appropriate locks
then you are not thread safe. It makes no difference if you are using
the c_str member or not, you are still accessing the same object and
if you don't own the lock on it you are not thread safe. Your
experiment is flawed and your statement above is incorrect.

Thread safety is YOUR problem, not the functions and not the objects
(necessarily). You asked about string manipulation and splitting and
presented non-threaded C code. I showed you an example of a
non-threaded C++ way to do it. Thread safety is a separate issue.

Since you were copying a const char *nString, I assumed you knew where
it was coming from and would obtain the lock on that string before
copying it to the local mutable string for manipulation.

[woodb...@gmail.com]

On Wednesday, March 30, 2016 at 9:42:45 AM UTC-5, Mr Flibble wrote:
> On 30/03/2016 07:19, Juha Nieminen wrote:
> >
> > I am perfectly aware of how linked lists work, and what their advantages
> > and disadvantages are.
> >
> > Yet, I have not used std::list since forever, for the simple reason that
> > I have never needed it. I remember using it in one serious project for
> > university, where it was actually necessary (the algorithm in question was
> > explicitly designed to work with fast splicing of linked lists). But
> > that's about it.
>
> If you have only used std::list once in your entire career then it is
> painfully obvious that you are not aware of (or stubbornly ignore) its
> advantages.

Whatever.

>
> >
> > The problem with std::list is that it consumes more memory, adding
> > elements to it is slower (because memory allocation is slow), and it
> > easily gets fragmented in memory, potentially adding to the slowness
> > of even element access. (This slowness does not technically speaking
> > affect its asymptotic complexity, but slowness is slowness.)
>
> std::set, std::multiset, std::map and std::multimap also have a single
> node based allocation strategy so are you suggesting we shouldn't use
> these containers either as they are "slow"? Besides, the allocation
> problems of which you speak can be mostly mitigated against through the
> use of a custom allocator such as one of the Boost pool allocators which
> should, IMO, be part of C++.

There's junk in the standard that should be removed and
there are some things that should have been added years
ago. The standard adds "any" but what about something
useful like pool allocators? Leave out the good stuff and
throw in some junk. More about this after the next paragraph.

Chandler Carruth gave a talk a few years ago about data
structures and performance. He said he despises std::map.
I agree with that.

Maybe this is like a Scooby Doo cartoon where a group
of friends is out playing and they run into a crook.
They put the pieces of the puzzle together and they
eventually catch up to the crook and take off his
mask. Then they are stunned to realize it's someone
they thought they knew. I think Chandler, Andrei A.
Bjarne S. and myself are some of the good guys. I have
hope for people here to go in the right path also,
but it's not clear yet to me what they will do. I
understand Andrei A.'s effort to be a trailblazer. If
that doesn't work out, I hope he will come back to C++.
I could name some people I think are suspect, but am not
sure that would help.

Brian
Ebenezer Enterprises - In G-d we trust.
http://webEbenezer.net

[Heinz-Mario Frühbeis]

Am 30.03.2016 um 17:25 schrieb Geoff:
> On Wed, 30 Mar 2016 09:58:54 +0200, Heinz-Mario Frühbeis
> <D...@Earlybite.individcore.de> wrote:
>
>> Am 28.03.2016 um 22:12 schrieb Geoff:
>>> On Mon, 28 Mar 2016 11:30:34 +0200, Heinz-Mario Frühbeis
>>> <D...@Earlybite.individcore.de> wrote:
>>>
>>>> Am 28.03.2016 um 01:39 schrieb Geoff:
>>>>> On Sun, 27 Mar 2016 22:13:10 +0200, Heinz-Mario Frühbeis
>>>>> <D...@Earlybite.individcore.de> wrote:
>>>>>
>>>>>> Am 27.03.2016 um 16:17 schrieb Jorgen Grahn:
>>>>>>> On Sun, 2016-03-27, Heinz-Mario Frühbeis wrote:
>>>>>>>> Am 27.03.2016 um 15:03 schrieb Alf P. Steinbach:
>>>>>>>>> On 27.03.2016 11:17, Heinz-Mario Frühbeis wrote:
>>>
>> [...]
>

[...]

> If you are using memmove or strlen without obtaining appropriate locks
> then you are not thread safe. It makes no difference if you are using
> the c_str member or not, you are still accessing the same object and
> if you don't own the lock on it you are not thread safe. Your
> experiment is flawed and your statement above is incorrect.
>
> Thread safety is YOUR problem, not the functions and not the objects
> (necessarily). You asked about string manipulation and splitting and
> presented non-threaded C code. I showed you an example of a
> non-threaded C++ way to do it. Thread safety is a separate issue.
>
> Since you were copying a const char *nString, I assumed you knew where
> it was coming from and would obtain the lock on that string before
> copying it to the local mutable string for manipulation.
>

I know, what I experience... std::string.c_str works, std::string not.

Regards
Heinz-Mario Frühbeis

[Dombo]

Op 30-Mar-16 om 16:38 schreef Mr Flibble:

But it does make a difference as far as effective speed and memory
fragmentation is concerned.

[Mr Flibble]

You can use a custom allocator with std::list to avoid fragmentation;
without a custom allocator std::deque also suffers from fragmentation.

/Flibble

[Paavo Helde]

On 30.03.2016 21:04, Heinz-Mario Frühbeis wrote:

>
> I know, what I experience... std::string.c_str works, std::string not.

Sorry, with C++ this is not sufficient. You have to know whether and why
something works and something does not. If you do not know and do not
want to learn, please choose another language, with less Undefined Behavior.

Cheers
Paavo

[Öö Tiib]

On Wednesday, 30 March 2016 22:04:42 UTC+3, Heinz-Mario Frühbeis wrote:
>
> I know, what I experience... std::string.c_str works, std::string not.

And we know that you are incorrect. The code that you posted
should not compile on C++ compiler. It is full of odd screaming
syntax errors. Your code, my comments added:

std::string string_var;
if(string_var.length() > 0)

// FINE ... you wrote ERROR
{}
if(strlen(string_var.c_str) > 0)
// ERROR: invalid use of member function 'c_str' ... you wrote NO ERROR

{}
if(string_var == "HALLO"() > 0)

// ERROR: string literal can't be called as function ... you wrote ERROR
{}
if(string_var.c_str == "HALLO")
// ERROR: invalid use of member function 'c_str' ... you wrote NO ERROR
{}

So you either experience troll lulz from responses of you pretending
ignorance or you really write such kooky voodoo code and anything you
experience with it is only within your imagination.

[Jens Thoms Toerring]

Heinz-Mario Frühbeis <D...@earlybite.individcore.de> wrote:
>> Am 30.03.2016 um 17:25 schrieb Geoff:
>> If you are using memmove or strlen without obtaining appropriate locks
>> then you are not thread safe. It makes no difference if you are using
>> the c_str member or not, you are still accessing the same object and
>> if you don't own the lock on it you are not thread safe. Your
>> experiment is flawed and your statement above is incorrect.

> I know, what I experience... std::string.c_str works, std::string not.

Please take a deep breath, relax and consider for just a moment
that you may have misunderstood a number of things: unfortunately,
your "experience" is completely irrelevant here as programming is
not an experimental science. Just because something happens with
a lower probability (e.g. the problems you experienced with a C
arrays compared to a C++ std::string) and you thus may not yet have
experienced it is no proof that it can't happen. What you say is
a bit like "experimental mathematics": 3 is a prime, 5 is a prime,
7 is a prime, thus, according to "experience", all odd numbers are
prime;-)

If you use threads and a thread can modify an object while another
thread accesses it (even just for reading) at the same time you've
got a massive problem, called a "race condition" (do yourself a
favour and look it up). These problems are insidious because they
are non-deterministic - most of the time it looks as if everything
is fine and dandy (because most of the time there's just one thread
doing anything with the object), but once in a while something
strange will happen but can't be reproduced. Threads are nice and
all, but they come with their own set of requirements to work pro-
perly: you either have to operate on "atomic" objects or obtain
locks while accessing them when there's even the slightest chance
that this object could be accessed by a different thread simulta-
nously. Everything else is simply a recipe for disaster.

A function can be "thread-safe", which just means that it will
work properly when two different threads call it at the same
time. But (with very few exceptions) objects aren't (neither a C
array nor a C++ std::string is) - only objects that can be acces-
sed "atomically" are - and there are very few of that kind (and
what is an "atomic" types can differ on different machines, so
that's another realm where your "experience" you gained on one
platform is, unfortunately, worth zilch).

And - BTW and out of context - one other of your code snippets
from a different thread

if (my_string.c_str() == "HELLO") {
....
}

is very unlikely to do what you seem to think it does. It com-
pares the address of where the 'my_string' std::string object
has stored it's string to where the compiler has stored the
non-modifiable C string "HELLO". That's rather unlikely to be
what you really want to know: from the looks of it you want to
know if these strings have the same content. But that's a dif-
ferent question and would require the use of the strcmp() func-
tion.

if (my_string == "HELLO")

and

if (my_string.c_str() == "HELLO")

may look similar (up to the point of getting fooled into assu-
ming that they are equivalent), but what they actually test for
is very, very different.
Regards, Jens
--
\ Jens Thoms Toerring ___ j...@toerring.de
\__________________________ http://toerring.de

[Juha Nieminen]

Mr Flibble <fli...@i42.co.uk> wrote:
> If you have only used std::list once in your entire career then it is
> painfully obvious that you are not aware of (or stubbornly ignore) its
> advantages.

I am perfectly aware of its properties. I have never needed it.

>> The problem with std::list is that it consumes more memory, adding
>> elements to it is slower (because memory allocation is slow), and it
>> easily gets fragmented in memory, potentially adding to the slowness
>> of even element access. (This slowness does not technically speaking
>> affect its asymptotic complexity, but slowness is slowness.)
>
> std::set, std::multiset, std::map and std::multimap also have a single
> node based allocation strategy so are you suggesting we shouldn't use
> these containers either as they are "slow"?

I was comparing std::list to std::vector and std::deque.

std::set & co. have advantages that std::list does not have, and those
are useful in certain situations. I have yet to encounter a practical
situation where std::list would be more useful than eg. std::vector.

[Juha Nieminen]

Mr Flibble <fli...@i42.co.uk> wrote:
> You can use a custom allocator with std::list to avoid fragmentation;
> without a custom allocator std::deque also suffers from fragmentation.

std::deque is a lot faster than std::list when adding elements to the
beginning or end, without the need for any custom allocators.

Even *with* a custom allocator, I doubt std::list would become even
equally fast.

[Ian Collins]

Implementing a queue?

--
Ian Collins

[Mr Flibble]

On 04/04/2016 07:19, Juha Nieminen wrote:
> Mr Flibble <fli...@i42.co.uk> wrote:
>> You can use a custom allocator with std::list to avoid fragmentation;
>> without a custom allocator std::deque also suffers from fragmentation.
>
> std::deque is a lot faster than std::list when adding elements to the
> beginning or end, without the need for any custom allocators.
>
> Even *with* a custom allocator, I doubt std::list would become even
> equally fast.

You are missing the point: std::deque and std::list have different
use-cases; your problem is that you are blissfully unaware of the
std::list use-cases.

/Flibble

[SG]

On Monday, April 4, 2016 at 1:16:18 PM UTC+2, Mr Flibble wrote:
> [...]
> std::list use-cases.

Out of curiosity: Name one.

Cheers!
sg

[Mr Flibble]

Any time you need element identity.

/Flibble

[SG]

You can get "element identity" in many ways. A collegue of mine relies
on "element identity" but uses std::deque. As long as you only add/
remove elements at/from the beginning or end, references will stay
valid. std::deque gives you a memory layout that's not too bad without
having to use a custom allocator and it offers random access. And then
there are things like Boost's ptr_vector giving you "element identity"
as well, even supporting polymorphism. In what situations would you
prefer std::list and why? Could you be a little more specific?

Cheers!
sg

[leigh.v....@googlemail.com]

ptr_vector requires two different allocators and allocation strategies whilst std::list requires just one. std::list is often better than both vector and ptr_vector if there are frequent insertions/erases in the middle.

Support for polymorphic types is a different kettle of fish and use-cases.

[SG]

Am Montag, 4. April 2016 18:10:41 UTC+2 schrieb leigh.v....@googlemail.com:
> [...] std::list is often better than both vector and ptr_vector if there are frequent insertions/erases in the middle.

Can you name an example where you did this? And if you can, how did
you find the insertion locations? Did you store iterators to the
elements somewhere else for O(1) insertion into the list at the desired
locations? Or did you do a linear search for this location? What was
the significance of the ordering in the list? What were *all* the
requirements w.r.t. the data structure?

I can't remember a situation during my last 9 years in which std::list
would have been beneficial over anything else. If you have, please
share this use-case.

Cheers!
sg

[leigh.v....@googlemail.com]

As you also appear to have stubbornly refused to utilise the advantages of std::list during your career probably due to following some blinkered groupthink I suspect you would simply reject any valid std::list use-case I provide so I won't even bother.

[Juha Nieminen]

So you are calling me a liar. I have said several times now that I know
perfectly what the properties and behavior of std::list are. (Heck, I once
even created my own STL-compatible singly-linked list implementation,
before one was added to C++11, just for the kicks.) In fact, I think that
the standardization committee pretty much ruined std::list when they
changed the complexity requirement of splice() from constant-time to
linear-time. That pretty much destroyed one of the big reasons to ever
use std::list. (As I commented earlier, there are algorithms that depend
on constant-time splicing of lists, for efficiency. Algorithms that are
very hard to implement using anything else, at least while maintaining
that efficiency.)

I have never needed std::list for anything. Your "use-cases" just don't
come up.

[Mr Flibble]

Juha Nieminen <nos...@thanks.invalid> wrote:
> Mr Flibble <fli...@i42.co.uk> wrote:
>> On 04/04/2016 07:19, Juha Nieminen wrote:
>>> Mr Flibble <fli...@i42.co.uk> wrote:
>>>> You can use a custom allocator with std::list to avoid fragmentation;
>>>> without a custom allocator std::deque also suffers from fragmentation.
>>>
>>> std::deque is a lot faster than std::list when adding elements to the
>>> beginning or end, without the need for any custom allocators.
>>>
>>> Even *with* a custom allocator, I doubt std::list would become even
>>> equally fast.
>>
>> You are missing the point: std::deque and std::list have different
>> use-cases; your problem is that you are blissfully unaware of the
>> std::list use-cases.
>
> So you are calling me a liar. I have said several times now that I know
> perfectly what the properties and behavior of std::list are. (Heck, I once
> even created my own STL-compatible singly-linked list implementation,
> before one was added to C++11, just for the kicks.) In fact, I think that
> the standardization committee pretty much ruined std::list when they
> changed the complexity requirement of splice() from constant-time to
> linear-time. That pretty much destroyed one of the big reasons to ever
> use std::list. (As I commented earlier, there are algorithms that depend
> on constant-time splicing of lists, for efficiency. Algorithms that are
> very hard to implement using anything else, at least while maintaining
> that efficiency.)

There are multiple overloaded splice functions only one of which is linear
complexity and the reason for that is to keep std::list::size() constant
time (which was a good decision IMO).

It remains obvious that you are still blissfully unaware of the std::list
use-cases.

/Flibble

[Chris Vine]

On Tue, 5 Apr 2016 06:43:46 +0000 (UTC)
Juha Nieminen <nos...@thanks.invalid> wrote:
> In fact, I think that the standardization committee pretty much
> ruined std::list when they changed the complexity requirement of
> splice() from constant-time to linear-time. That pretty much
> destroyed one of the big reasons to ever use std::list.

Can you provide a reference for me of this? C++14 is the same as C++98
on the complexity of splice. size() has gone from linear time to
constant time, but that is a different matter.

Chris

[Mr Flibble]

One of the splice() overloads needs to be linear time if size() is to be
constant time.

/Flibble

[Öö Tiib]

Before C++11 there was no requirement that 'size' is constant time.
When standard was made then committee assumed that typically 'size' is
not needed massively. Committee assumed that typically it is of interest
if container "is empty", Unfortunately a method with awful (IMHO)
"emptying" name 'empty' was added instead of 'is_empty'.

Many implementations made 'size' of some containers linear time, since it
can speed up inserts, erases and splices from trees and lists. It is just
as rarely needed to 'splice' a lot (as is to 'size' a lot) but 'std::list'
had its exceptionally strong side in those implementations.

However noob user (and typical user is noob) code did not use 'c.empty()';
most code used 'c.size() == 0' and C++ noob code was inefficient. So C++11
went noob friendly and now requires that size must be constant.

Therefore splice has now to be linear complexity since the new size has to
be found out during splice. Well ... we can use 'boost::intrusive::list'
(with its inconveniences) if we ever need well-performing lists again.

[Juha Nieminen]

Mr Flibble <flibbleREM...@i42.co.uk> wrote:
> There are multiple overloaded splice functions only one of which is linear
> complexity and the reason for that is to keep std::list::size() constant
> time (which was a good decision IMO).
>
> It remains obvious that you are still blissfully unaware of the std::list
> use-cases.

The decision to make that splice() function linear-time was idiotic because
it pretty much destroys one of the use cases where linked lists are
actually efficient. There are algorithms that depend on splicing parts of
lists onto other lists in constant-time. Now std::list became useless
for that purpose.

I think it's *you* who doesn't know the use cases for linked lists.

[SG]

On Monday, April 4, 2016 at 8:52:01 PM UTC+2, leigh.v....@googlemail.com wrote:
> As you also appear to have stubbornly refused to utilise the advantages of std::list during your career probably due to following some blinkered groupthink I suspect you would simply reject any valid std::list use-case I provide so I won't even bother.

How convenient for you.

Why would I refuse to utilise the advantages of std::list? Such a
situation just never came up. If anything, I'm unimaginative -- not
stubborn. I would have liked to read about actual problems you solved
using std::list. But I guess I won't be hearing about them since you
avoided answering my questions.

[Chris Vine]

On Tue, 5 Apr 2016 17:12:05 -0700 (PDT)
Öö Tiib <oot...@hot.ee> wrote:
[snip]

> Therefore splice has now to be linear complexity since the new size
> has to be found out during splice. Well ... we can use
> 'boost::intrusive::list' (with its inconveniences) if we ever need
> well-performing lists again.

OK, thanks for explaining that. I can see that the complexity of range
splicing between different lists has changed from constant time to
linear time over the range (but not over the whole list). For single
element splicing (the three argument version of std::list::splice()),
constant time should still be possible because you know you can just
increment the size variable of the sink by one and decrement the source
by one. For whole list splicing (the two argument version of
std::list::splice()), you can just add the two previous sizes to get
the new size of the sink, and set the size of the source to 0. C++98,
C++14 and the latest version of the draft standard produced by WG21
(N4582) indeed still say that these must be constant time. Likewise
range splicing (the four argument version of splice) should still be
constant time if the sink and source are the same because the size does
not change, and the standard still requires this (§23.3.10.5 of N4582).

Previously range splicing where the source list is different from the
sink list could presumably have been constant time since you would only
need to fix up the affected node pointers. What puzzles me on thinking
about this is that C++98 says the same as the current standard, namely
that range splicing between different lists has linear time
(§23.2.2.4/14). Presumably most implementations in fact ignored this
and made the operation constant time, and it is ability of
implementations to 'improve on' the standard which has now gone.

Chris

[Juha Nieminen]

Öö Tiib <oot...@hot.ee> wrote:
> However noob user (and typical user is noob) code did not use 'c.empty()';
> most code used 'c.size() == 0' and C++ noob code was inefficient. So C++11
> went noob friendly and now requires that size must be constant.

One possible solution would have been to keep splice constant-time, and
have size() be linear-time only the first time it's called, and constant-time
with subsequent calls, until the next time the list is spliced. (Element
addition and removal wouldn't need to invalidate the size because those
are done one at a time. Only splicing can add an unknown number of elements.)

[Mr Flibble]

Juha Nieminen <nos...@thanks.invalid> wrote:
> Öö Tiib <oot...@hot.ee> wrote:
>> However noob user (and typical user is noob) code did not use 'c.empty()';
>> most code used 'c.size() == 0' and C++ noob code was inefficient. So C++11
>> went noob friendly and now requires that size must be constant.
>
> One possible solution would have been to keep splice constant-time, and
> have size() be linear-time only the first time it's called, and constant-time
> with subsequent calls, until the next time the list is spliced. (Element
> addition and removal wouldn't need to invalidate the size because those
> are done one at a time. Only splicing can add an unknown number of elements.)

I suggested several years ago in this very newsgroup that std::list::size()
could be amortised constant time (basically make the size member variable
mutable optional) as a solution to this problem however the range variant
of splice() isn't the only std::list use-case so perhaps such a change was
seen as too irksome with a too-low priority.

/Flibble

[Mr Flibble]

It remains painfully obvious that it is YOU who doesn't know when to use
std::list as you are only aware of one (non-ideal) use-case (range variant
of splice).

/Flibble

[Juha Nieminen]

Mr Flibble <flibbleREM...@i42.co.uk> wrote:
> It remains painfully obvious that it is YOU who doesn't know when to use
> std::list as you are only aware of one (non-ideal) use-case (range variant
> of splice).

You seem to be like a broken record.

Did you have an actual argument to make?