Tuesday, April 5, 2016

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

Juha Nieminen <nospam@thanks.invalid>: Apr 05 06:43AM


> 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.)
 
I have never needed std::list for anything. Your "use-cases" just don't
come up.
 
--- news://freenews.netfront.net/ - complaints: news@netfront.net ---
Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk>: Apr 05 10:37AM -0500

> 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 <chris@cvine--nospam--.freeserve.co.uk>: Apr 06 12:09AM +0100

On Tue, 5 Apr 2016 06:43:46 +0000 (UTC)
> 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
Paul <pepstein5@gmail.com>: Apr 05 12:43AM -0700

My code below seems to run fine but I'm not happy with the memory management side of it. The explore function is supposed to delete the pointers in vertices which is a vector of pointers and replace them with the new v.
However, this doesn't seem to work. In function explore, I'm confused by the fact that vertices[index]->component seems to give the correct value, straight after I've done delete vertices[index]; I would have expected a runtime crash.
 
Also, what is the simplest method here to avoid memory leaks? The values of vertices[index] are allocated using new. I'm assuming that changing them (such as vertices[index] = v;) will leak memory. Is this correct? Or is delete vertices[index]; unnecessary?
 
I'm interested in the case where vertex is replaced by a much more complex struct or class whose objects are not limited to ints.
 
Many thanks for your comments.
 
Paul
 
 
struct vertex{
vertex(int num, int vcomp = -1):component(vcomp), label(num){}
// Value of -1 indicates the component is unassigned.
int label;
int component;
 
};
 
class Graph{
 
int numVertices;
std::vector<vertex*> vertices;
std::vector<int> v2comp; // ith member gives component of ith vertex.
std::vector<bool> visited;
std::vector<std::vector<int> > adjLists;
std::vector<std::vector<int> > componentsAsVector;
int currentComponent;
 
void explore(vertex* v)
{
const int index = v->label;
visited[index] = true;
v->component = currentComponent;
v2comp[index] = currentComponent;
 
delete vertices[index];
std::cout <<std::endl << vertices[index]->component << std::endl
<< v->component << std::endl;
vertices[index] = v;
for(auto w : adjLists[index])
if(!visited[w])
explore(vertices[w]);
}
 
void Vazirani()
{
for(int i = 0; i < numVertices; ++i)
if(!visited[i])
{
++currentComponent;
explore(vertices[i]);
}
 
}
 
void presentAsVector()
{
componentsAsVector= std::vector<std::vector<int> > (++currentComponent);
for(int i = 0; i < numVertices; ++i)
componentsAsVector[v2comp[i]].push_back(i);
}
 
public:
Graph(const std::vector<std::vector<int> >& graph): numVertices(graph.size()), vertices(numVertices), v2comp(numVertices), visited(numVertices), currentComponent(-1), adjLists(graph)
{
for(int i = 0; i < numVertices; ++i)
vertices[i] = new vertex(i);
}
 
~Graph()
{
for(auto v : vertices)
delete v;
}
 
void generateComponents()
{
Vazirani();
presentAsVector();
}
 
void display()
{
int index = 1;
for(auto c : componentsAsVector )
{
std::cout << "Now displaying connected component " << index++ << std::endl;
std::cout << "This component contains vertices: " << std::endl;
for(auto v : c)
std::cout << v << std::endl;
}
}
 
};
 
 
int main()
{
/* 0->1->2->3->4->5
6->3
7 */ std::vector<std::vector<int> > graph = {{1}, {0,2}, {1,3}, {2, 4, 6}, {3, 5}, {4}, {3}, {}};
Graph g(graph);
g.generateComponents();
g.display();
return 0;
}
Barry Schwarz <schwarzb@dqel.com>: Apr 05 01:16AM -0700

On Tue, 5 Apr 2016 00:43:03 -0700 (PDT), Paul <pepstein5@gmail.com>
wrote:
 
>My code below seems to run fine but I'm not happy with the memory management side of it. The explore function is supposed to delete the pointers in vertices which is a vector of pointers and replace them with the new v.
>However, this doesn't seem to work. In function explore, I'm confused by the fact that vertices[index]->component seems to give the correct value, straight after I've done delete vertices[index]; I would have expected a runtime crash.
 
Evaluating a pointer after the memory it points to has been released
causes undefined behavior. While a crash at this point is certainly
desirable, you cannot depend on any particular result.
 
>Also, what is the simplest method here to avoid memory leaks? The values of vertices[index] are allocated using new. I'm assuming that changing them (such as vertices[index] = v;) will leak memory. Is this correct? Or is delete vertices[index]; unnecessary?
 
The only method of avoiding memory leaks is careful programming. If a
pointer points to allocated memory and you assign a new value to the
pointer, the allocated memory becomes inaccessible for any purpose and
you have a memory leak. On most modern systems, any allocated memory
will be recovered by the system when your program terminates. However,
issuing a delete for every new is still considered good practice.
 
>I'm interested in the case where vertex is replaced by a much more complex struct or class whose objects are not limited to ints.
 
The type of object pointed to is not a deciding factor. If the memory
was dynamically allocated, it should be released.
 
If the object contains pointers to other dynamically allocated memory,
then you need to release in the reverse order of the allocations. If
pointer a points to dynamic object b which contains a pointer c which
also points to dynamic memory, you would delete a->c before you delete
a.
 
--
Remove del for email
"Öö Tiib" <ootiib@hot.ee>: Apr 05 12:29PM -0700

On Tuesday, 5 April 2016 10:43:17 UTC+3, Paul wrote:
> management side of it. The explore function is supposed to delete
> the pointers in vertices which is a vector of pointers and replace
> them with the new v.
 
Then use vector of 'std::unique_ptr'. Attempts to derefence
'vertices[index]' after 'vertices[index].reset()' is null pointer
dereference with 'std::unique_ptr'. All platforms with virtual
memory (IOW most used) reward null pointer dereference with crash.
 
Instead of attempting to write a class named "Graph" one should
perhaps study how 'boost::adjacency_list' is written and why it is
bad and weak class. Skill of inventing square wheels is not
desirable in our industry. ;)
Paul <pepstein5@gmail.com>: Apr 05 12:41PM -0700

On Tuesday, April 5, 2016 at 8:29:57 PM UTC+1, Öö Tiib wrote:
> perhaps study how 'boost::adjacency_list' is written and why it is
> bad and weak class. Skill of inventing square wheels is not
> desirable in our industry. ;)
 
Thanks. I'm trying to prepare for a technical interview. I don't think they will test for knowledge of boost. It's even somewhat unlikely that they will test for knowledge of pointers. They are interested in basic data structures and algorithms and the approach is language agnostic, but the code needs to run, and not just be pseudo-code, but it should still be correct.
 
Thank You.
 
Paul
"Öö Tiib" <ootiib@hot.ee>: Apr 05 01:07PM -0700

On Tuesday, 5 April 2016 22:42:19 UTC+3, Paul wrote:
> in basic data structures and algorithms and the approach is language
> agnostic, but the code needs to run, and not just be pseudo-code, but
> it should still be correct.
 
I do not know on what planet the interview is supposed to take place.
Most masters on this planet dislike square wheels. Making square wheels
wastes time and the product that has those does roll very badly.
Paul <pepstein5@gmail.com>: Apr 05 01:56PM -0700

On Tuesday, April 5, 2016 at 9:07:15 PM UTC+1, Öö Tiib wrote:
 
> I do not know on what planet the interview is supposed to take place.
> Most masters on this planet dislike square wheels. Making square wheels
> wastes time and the product that has those does roll very badly.
 
The interview is by phone so it's not limited to any single planet. It's very common for the interviewer and interviewee to be located on different planets and to communicate by interplanetary phones.
 
Paul
"Öö Tiib" <ootiib@hot.ee>: Apr 05 02:24PM -0700

On Tuesday, 5 April 2016 23:57:09 UTC+3, Paul wrote:
 
> The interview is by phone so it's not limited to any single planet.
> It's very common for the interviewer and interviewee to be located
> on different planets and to communicate by interplanetary phones.
 
Sounds like someone is scamming you.
Chris Vine <chris@cvine--nospam--.freeserve.co.uk>: Apr 05 11:54PM +0100

On Tue, 05 Apr 2016 01:16:28 -0700
> pointer, the allocated memory becomes inaccessible for any purpose and
> you have a memory leak. On most modern systems, any allocated memory
> will be recovered by the system when your program terminates.
 
Out of interest, can you name a modern system in practical use that does
not recover memory when a program terminates?
 
> However, issuing a delete for every new is still considered good
> practice.
 
No. Using resource handles such as std::unique_ptr is considered good
practice.
 
Chris
Paolo Biagini <paolobo1.pb@gmail.com>: Apr 05 04:38AM -0700

see code...
 
 
#include <iostream>
#include <typeinfo>
using namespace std;

int main()
{
class fff
{
float val;
public:
explicit fff(float f) : val(f) {}
operator float() const { return val; }
float getfloat() const { return val; }
} f(42.42f);
 
auto foo1 = true ? 1 : f;
auto foo2 = true ? 1 : f.getfloat();
auto foo3 = true ? 1.1 : f;
auto foo4 = true ? 1.1 : f.getfloat();
 
cout << typeid(foo1).name(); // foo1 = int ???
cout << typeid(foo2).name(); // foo2 = float ok
cout << typeid(foo3).name(); // foo3 = double ok
cout << typeid(foo4).name(); // foo4 = double ok

float uffa = false ? 1 : f; // LOOK THIS !!!
cout << uffa;
return 0;
}
 
output is: ifdd42
while I expected: ffdd42.42
or better a compiler arror !!!
"Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com>: Apr 05 07:37PM +0200

On 05.04.2016 14:01, Stefan Ram wrote:
> ...
> |an attempt is made to convert each of those operands to the
> |type of the other.
 
And there is no implicit conversion from `int` to your class `fff`.
 
Cheers!,
 
- Alf
"Öö Tiib" <ootiib@hot.ee>: Apr 05 03:31PM -0700

On Tuesday, 5 April 2016 14:38:46 UTC+3, Paolo Biagini wrote:
> see code...
 
Implicit conversion operators, implicit conversion constructors,
operator overloading, 'auto' and 'std::initializer_list' are
ILLUSION school spells of C++ wizard. Sometimes carefully cast
illusion makes something to look bit nicer than it really is.
 
Wussies and weenies will self-confuse with those and run away, evil
sorcerers will confuse their colleagues and will be kicked out and
so only good engineers will be left in C++ teams. It will be bit
painful but that is the procedure. Hopefully you got the warning. ;)
Juha Nieminen <nospam@thanks.invalid>: Apr 05 06:59AM

> 96 is not 512. You have made a mistake: you compiled the program with a
> C++ compiler. Use a C compiler instead.
 
Fine:
 
//-------------------------------------------------------------------
#include "ccl/intdlist.h"
#include <stdio.h>
 
int main()
{
printf("%zu %zu\n",
sizeof(struct INTERFACE_STRUCT_INTERNAL_NAME(int)),
sizeof(struct ITERATOR(int)));
return 0;
}
//-------------------------------------------------------------------
 
Compiled with "clang -O3", output:
 
512 112
 
 
> The difference between a direct and an indirect call is just ONE MEMORY
> ACCESS. Does a single memory access make ANY difference at 2.7GB/second?
 
> Of course not.
 
It can have a difference in tight inner loops that are run millions of times.
 
C++ doesn't need this kind of indirection, and the optimization comes for
free, without you having to do anything for it.
 
> C offers the added flexibility (that you loose when the call is
> hard-wired like in C++) that you can change the call at run time if you
> want.
 
You say it like it's a C feature (rather than a feature of your library),
as if it were impossible in C++. After all, you didn't say "this library
offers the added flexibility". You said "C offers the added flexibility".
As if C++ didn't, if you implemented it like that.
 
> additional level of indirection, and the compiler has no possibility
> of inlining.
 
> Of course the compiler could inline IF THE COMPILER WRITERS WANTED.
 
You first give the very reason why it can't be inlined (because, as you
said, the pointer could be changed at runtime to point somewhere else,
which effectively precludes inlining), and then you say that it could
be inlined if the compiler writers wanted. I don't think even you know
what you are talking about.
 
> But since C is not being developed anymore as a language
 
Oh, that's why the latest C standard is from 2011? That's ancient indeed.
Belongs to a museum.
 
--- news://freenews.netfront.net/ - complaints: news@netfront.net ---
jacobnavia <jacob@jacob.remcomp.fr>: Apr 05 09:16AM +0200

Le 05/04/2016 08:59, Juha Nieminen a écrit :
> which effectively precludes inlining), and then you say that it could
> be inlined if the compiler writers wanted. I don't think even you know
> what you are talking about.
 
I said:
 
<quote>
You could install a
"freeze" switch in the compiler that would it allow to inline calls
through a known function pointer assuming the function pointer is fixed
at the start of the program.
<end quote>
 
but you ignored that part of my message. This "selective quoting" is
normal in these polemics in Usenet.
 
Then, the other stuff:
 
You get 512 bytes
jacobnavia <jacob@jacob.remcomp.fr>: Apr 05 09:18AM +0200

Le 05/04/2016 08:59, Juha Nieminen a écrit :
> Compiled with "clang -O3", output:
 
> 512 112
 
 
This is ridiculous. There is only ONE object of this kind in the whole
program. If it takes more or less bytes is irrelevant.
Randy Howard <rhoward.mx@EverybodyUsesIt.com>: Apr 05 08:48AM -0500

On 4/5/16 2:18 AM, jacobnavia wrote:
 
>> 512 112
 
> This is ridiculous. There is only ONE object of this kind in the whole
> program. If it takes more or less bytes is irrelevant.
 
You must be used to this by now Jacob. :-) Welcome to Usenet.
 
--
Randy Howard
(replace the obvious text in the obvious way if you wish to contact me
directly)
ram@zedat.fu-berlin.de (Stefan Ram): Apr 05 12:01PM

>true ? 1 : f;
 
5.16p3
 
|Otherwise, if the second and third operand have different
|types and either has (possibly cv-qualified) class type,
...
|an attempt is made to convert each of those operands to the
|type of the other.
kurt.krueckeberg@gmail.com: Apr 04 06:03PM -0700

Changing
 
f(*current, current_tree_level)
 
in the method
template<class Key, class Value> template<typename Functor> void tree23<Key, Value>::levelOrderTraverse(Functor f) const noexcept
 
to be

f.template operator()<Key, Value>(*current, current_tree_level);
 
gets rid of the "unable to deduct template parameter 'Key'" error, and it now compiles successfully.
You received this digest because you're subscribed to updates for this group. You can change your settings on the group membership page.
To unsubscribe from this group and stop receiving emails from it send an email to comp.lang.c+++unsubscribe@googlegroups.com.
Posted by at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)