Computing desk
< May 30	<< Apr \| May \| Jun >>	June 1 >

Welcome to the Wikipedia Computing Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

May 31

C++ recursive tagged union problem

#include <iostream>
#include <vector>

struct Tree {
	bool is_leaf;
	union {
		int leaf;
		std::vector<Tree> children;
	};
	Tree(): is_leaf(false), children() {/*std::cout << "default constructor called\n";*/}
	Tree(const Tree& t) {/*std::cout << "copy constructor called\n";*/ *this = t;}
	Tree operator= (const Tree& t) {
		/*std::cout << "copy assignment called\n";*/
		if (is_leaf = t.is_leaf) {leaf = t.leaf;}
		else {children = t.children;}
		/*std::cout << " copy assignment ends\n";*/
		return *this;
	}
	~Tree() {
		/*std::cout << "destructor called\n";*/
		if (!is_leaf) {children.~vector();}
		/*std::cout << " destructor ends\n";*/
	}
};

int main() {
	Tree t;
	Tree u(t);
}

I am trying to implement a tree-like data structure in C++. Basically a Tree is either a data-containing leaf node or consists of one or more children subtree. I supposed a tagged union would best fit this situation. Because I used vector — which has non-trivial special member functions — to store the list of children, I had to provide the special member functions of Tree myself (pre-C++11 doesn't even allow it). I don't know how to do this properly so I just go with what mekes sense in my mind. The above code, when ran, has a runtime error but I couldn't figure out how it happens. Here is the output when uncommented:

default constructor called
copy constructor called
copy assignment called
destructor called
destructor called
destructor called

Then the error occurs. I have tried removing the if line in the destructor but then it just prints

...
destructor called
 destructor ends
destructor called
 destructor ends
...

infinitely. Replacing *this = t with "proper" construction doesn't help either.

I tried to run through a debugger but still don't know how and why the destructor was called. Currently I am in a state of utter confusion, don't know what part of C++ I'm missing or what to search now (I tried googling but no avail. And returning to cppreference just confuse me more). Please help. In case it matters, I'm using MinGW on Windows 10.

The original code is much longer and more complicated but this is a seperate minimum working example to ease debugging for me (and you).14.177.103.250 (talk) 08:32, 31 May 2018 (UTC)[reply]

For some reason I don't quite understand, constructing or destructing a vector of type T will sometimes create/destroy a T object. This causes and endless loop in your case. The simplest fix seems to be to let default trees be leaves, which makes more sense anyway 192.176.1.90 (talk) —Preceding undated comment added 14:53, 31 May 2018 (UTC)[reply]

Doesn't work. It just cause another infinite loop. Different from last time, but still inscrutable. Anyway, I already have a constructor taking int to create leaf, but not shown. That default constructor just fits more with the rest of my code. 14.177.103.250 (talk) 04:18, 1 June 2018 (UTC)[reply]

I suppose putting a vector into a union is calling for problems. Why don't you just put a vector of children as an ordinary member and implement the TreeNode::isALeaf() predicate with a simple inline test for children.empty()??? Then no need to explicitly call consrtuctor and destructor, which may easily go wrong. --CiaPan (talk) 15:53, 31 May 2018 (UTC)[reply]

Because it takes less space. In my real code, there're 4 data member in the union, so it kinda made sense to me. It irks a little when you know you'll only use one and initialize the remaining three for nothing. Although a bit wasteful, I will go with this solution for now because it's the easiest. I will check out your excellent solutions below when I need to save some space. Beside, while I could do as you suggested, I am still curious about why my code works the way it does — which might lead me to something new. I guess I'm expecting too much. Anyway, thanks. 14.177.103.250 (talk) 04:54, 1 June 2018 (UTC)[reply]

...or, instead of including a vector of nodes keep a pointer to a vector (defaulting to nullptr) and create a vector if necessary with explicit call to new:

	void TreeNode::AddAChild (TreeNode* node) {
		if (childrenptr == nullptr)
			childrenptr = new vector<TreeNode>;
		childrenptr->push_back (node);
	}

	bool TreeNode::IsALeaf() { return childrenptr == nullptr || childrenptr->empty(); }

and, of course, appropriate deletion routine:

	TreeNode::~TreeNode() {
		delete childrenptr;
	}

Or maybe you can use a smart pointer to take care automatically of destructing and deleting the optional object at appropriate time. --CiaPan (talk) 16:10, 31 May 2018 (UTC)[reply]

TreeView class [1] AboutFace 22 (talk) 16:49, 31 May 2018 (UTC)[reply]

@AboutFace 22: Not all trees belong to the Windows environment... --CiaPan (talk) 17:05, 31 May 2018 (UTC)[reply]

The assignment operator implementation contains at least one error, IMHO. In the conditional:

if (is_leaf = t.is_leaf)

you copy and at the same time you test the is_leaf property of the source object.

However, you do that too fast! As a result you loose information about the previous state of the current object.

When you assign the object t to *this you must take four cases into account:

both *this and t are leaves → you just copy the internal data;
both *this and t are internal nodes → you use the vector's copy constructor;
*this is a leaf, but t has children → you must 'manually' construct the destination vector before copying children;
*this has children, but t is a leaf → you need to destroy the children vector before copying the union's leaf member.

One more thing to take care about: does your vector contain children objects themselves or just references? This is important when you copy nodes, because you need to clone descendant nodes in the first case (and possibly track the clones and synchronize them later – or not, depending on the reason for cloning), or you need to track the number of references to each node object to delete them at appropriate time in the second case (avoid destroying objects prematurely if some references still exist, but don't abandon them unreferenced when no longer needed to avoid memory leaks). --CiaPan (talk) 07:03, 1 June 2018 (UTC)[reply]

Is this what you are talking about? Because it emits the same output as before.

Tree operator= (const Tree& t) {
	std::cout << "copy assignment called\n";
	if (is_leaf) {
		if (t.is_leaf) {
			leaf = t.leaf;
		} else {
			children = std::vector<Tree>(t.children.size());
			for (int i = 0; i < t.children.size(); ++i) {
				children[i] = t.children[i];
			}
		}
	} else {
		if (t.is_leaf) {
			children.~vector();
			leaf = t.leaf;
		} else {
			children = t.children;
		}
	}
	is_leaf = t.is_leaf;
	std::cout << " copy assignment ends\n";
	return *this;
}

14.177.103.250 (talk) 04:38, 2 June 2018 (UTC)[reply]

How could computers run 20 years ago with so little RAM?

If I'm correct RAM between the years '95 to '99, for a home computer, was usually something from 32MB to 128MB . However, back then, people already had browsers, PDFs, Word and Excel. How could they run with so little RAM? What's going wrong with today's computers? From the point of view of the user experience, how were things like for the users of the '90s compared to our present day? Are my 4GB RAM idle most of the time, when I'm just navigating the web, writing a text or doing similar stuff? --Doroletho (talk) 16:46, 31 May 2018 (UTC)[reply]

I'm sure there will be many comments about programs getting larger, but much of it is the operating system, which is stored in RAM. Every operating system has a minimum RAM requirement. That has been going up with every new version. It is based on what people have. The more RAM computers get, the more the operating system will need. 209.149.113.5 (talk) 17:15, 31 May 2018 (UTC)[reply]

Software was written much more compactly and efficiently in those days, and it had fewer bells and whistles and other add-ons that take up so much memory in modern computers. Going back further, I remember a timetabling program that ran in 128KB of RAM on a BBC computer. I made some very minor modifications to the program, but it took me a long time to decipher the very compact coding. There were modules that were loaded into memory from disk as and when needed. Dbfirs 17:22, 31 May 2018 (UTC)[reply]

They didn't have web browsers, or if they did, they were a lot smaller footprint. If they were browsing the web, they probably had one window open and tabbed browsing within windows hadn't appeared yet.

Also, Windows '95 is only just appearing in that timescale, so there might still be some 16 bit Windows 3.11 about.

These days, programs adapt dynamically to eat whatever is available to them. This laptop is 8GB, but a web browser (any) will still consume 2/3rd of that. Andy Dingley (talk) 18:35, 31 May 2018 (UTC)[reply]

They didn't have web browsers? Hofhof (talk) 18:43, 31 May 2018 (UTC)[reply]

They were available, very few people were using them until 1997. Few until 1999. Andy Dingley (talk) 19:09, 31 May 2018 (UTC)[reply]

NCSA Mosaic was released on 23 Jan 1993. LongHairedFop (talk) 20:14, 31 May 2018 (UTC)[reply]

"How were things like for the users of the '90s?" Slower, less capable, less automatic, less parallel. less resolution,…. Spell checkers were usually on demand instead of Word 95 doing it in the background or nowadays with autocorrect and grammar checkers. Games just have more in them, requiring bigger and faster machines

"Are my 4GB RAM idle most of the time?" Yes and no. For most things humans do at any one time, it is overkill. If you have hundreds of tabs with pages playing video ads or calculating bitcoin for someone and all the other apps you have open, you probably max things out. "Memory is free until you run out." The software stack is so big and there is resistance to reducing it so it keeps growing. The original Mac had 128K and could do WYSIWYG text editing, with occasional floppy swapping. Try landing on the moon in 1969 with only 4KB of RAM. StrayBolt (talk) 23:09, 31 May 2018 (UTC)[reply]

One thing about the Apollo Guidance Computer is that it had (I think) dozens of small programs for different phases of the mission. Bubba73 ^{You talkin' to me?} 03:57, 1 June 2018 (UTC)[reply]

About 45 programs, see this pdf. Bubba73 ^{You talkin' to me?} 04:20, 1 June 2018 (UTC)[reply]

They used to have a lot less memory than that. I used two computers that had 64KB (KB, not MB). Then I had the common 640KB. Programs were smaller and they dealt with less data. The minimum size that I could write for a DOS program in the 1980s was about 9KB. Now the minimum size for a Windows program is several megabytes - close to 500 times larger. I remember WordStar word processor for DOS being with 29KB or 39KB. See Software bloat. Bubba73 ^{You talkin' to me?} 02:17, 1 June 2018 (UTC)[reply]

The original VisiCalc executable was 27,520 byes: it can be downloaded from here. It won't run natively in Windows 10 but will run under DOS emulators such as DOSBox. AndrewWTaylor (talk) 09:00, 1 June 2018 (UTC)[reply]

The minimum size that I could write for a DOS program in the 1980s was about 9KB. – Bloatware! Here's the source code for a text-only terminal program that I wrote in 1991:

Extended content

; World's shortest comms program!
; Use MODE to set the comm port parameters then syntax is:  T comm_port
; Alt-X quits

; Requires DSR and CTS from the port

.radix  16

quitkey equ     2D00                    ;Alt-X

code    segment
assume  cs:code,ds:code,es:code,ss:code

org     0100

start:  mov     al,ds:[82]              ;get comm port
        sub     al,"1"
        cbw
        push    ax
rx:     pop     dx
        push    dx
        mov     ah,3                    ;check port for data
        int     14
        rcr     ah,1
        jnc     tx                      ;if nothing, check keyboard
        mov     ah,2                    ;read comm port
        pop     dx
        push    dx
        int     14
        mov     dl,al                   ;write to STDOUT
        mov     ah,2
        int     21
tx:     mov     ah,1                    ;check keyboard
        int     16
        jz      rx                      ;if nothing check comm port again
        mov     ah,0                    ;get key in AL
        int     16
        cmp     ax,quitkey              ;check for quit key
        pop     dx
        je      quit
        mov     ah,1                    ;send to comm port
        push    dx
        int     14
        jmp     rx                      ;check comm port again

quit:   ret

code    ends
end     start

It compiles (with Borland's TASM) to a 53-byte (fifty-three bytes) COM file. Text only, no graphics, but if you loaded ANSI.SYS first you could get colour.

Actually it's the smallest practical terminal program I've seen. If you hard code the port number and remove the need to exit the program, it can be even smaller.

Mitch Ames (talk) 13:31, 1 June 2018 (UTC)[reply]

That 9K was about the smallest that Turbo Pascal would produce. Bubba73 ^{You talkin' to me?} 00:44, 3 June 2018 (UTC)[reply]

The EICAR test file is this executable COM file:

X5O!P%@AP[4\PZX54(P^)7CC)7}$EICAR-STANDARD-ANTIVIRUS-TEST-FILE!$H+H*

PrimeHunter (talk) 20:14, 2 June 2018 (UTC)[reply]

@Mitch Ames: Out of curiosity, I typed out your program in my PC DOS 7 computer and assembled it with Eric Isaacson's A86 assembler. Sure enough, it assembled to a 53 byte COM program. When I ran it, at least it didn't crash, but it resulted in 1. each character typed overwrote the previous, 2. after 3 characters typed, a screenfull of repeat characters, necessitating an ALT-X exit (which worked). I see a push ax without a corresponding pop. It should be noted that this little program does not set any serial port parameters, such as 9600,8,N,1 or the Modem Control Register bits 0 (Data Terminal Ready) and 1 (Request To Send). Nor does it set FIFO Register bits 6 and 7 (minimum number of characters waiting in receive buffer required to generate an interrupt) or bit 0 (enable FIFO for transmit and receive). Akld guy (talk) 21:48, 2 June 2018 (UTC)[reply]

... PC DOS 7 ... – The program did work (within its stated limitations) on MS-DOS 3.3x. It's possible that it won't work correctly under later versions. The reference book that I used (Dettmann and Johnson's DOS Programmer's Reference, 3rd edition), which covers up to DOS 5, says of int 21, function 2, "Microsoft recommends that you longer use this function ... Support for this function may end at any time." (I used it because it requires fewer opcodes than the recommended replacement function 40h. I wasn't writing with a view to long term support either

)

I see a push ax without a corresponding pop. – push ax is followed immediately by pop dx, which transfers the port number from AX to DX, for use by int 14. Given that the pop is already used to restore DX after int 21, push is shorter than mov dx,ax.

It should be noted that this little program does not set any serial port parameters, – Hence the comment at the top about using MODE to do the set up. The way to get the "smallest" program was to do the bare minimum - as much as possible was left to the operating system, including initial setup with existing DOS commands. The program was written for size, not speed or ease of use, which is why it uses BIOS (int 14) and DOS (int 21) calls (and polling rather than interrupts) to do everything.

Mitch Ames (talk) 03:56, 3 June 2018 (UTC)[reply]

@Mitch Ames: Ah yes. push ax, pop dx, I was not accustomed to doing that, preferring mov dx,ax. Int 21 works in DOS 6.22 and my current PC DOS 7 as I have written Assembler code in both. Akld guy (talk) 23:29, 4 June 2018 (UTC)[reply]

Back with assembler on a DOS PC, I had a friend who could write programs that did something useful making a .COM file (a pre-Internet term) of about 200 bytes. Bubba73 ^{You talkin' to me?} 21:55, 2 June 2018 (UTC)[reply]

David Ahl said this while interviewing Donald Knuth, published in Creative Computing, Jan 1980, page 74: "I felt that when I was learning to program the IBM 650 and Bendix G-15 … you had 4K of usable core. The first minis, PDP-5 and PDP-6 were again 4K, and to go up to 8K was like having the world. I have kids working for me today who feel that if it doesn't have 48K you can't do anything with it." Bubba73 ^{You talkin' to me?} 00:43, 3 June 2018 (UTC)[reply]

.COM files have a maximum size of 64 kB. With Assembler, you can do a tremendous amount with that, especially if you reuse buffers over and over. Unfortunately, with the demise of the 1.44 MB floppy disk, programmers got lazy and create lots of one-time-use buffers. Akld guy (talk) 02:48, 3 June 2018 (UTC)[reply]

Well, the first computer that I programmed was an IBM 7094 and had a total of 32K of memory and occupied a large room. Robert McClenon (talk) 16:57, 8 June 2018 (UTC)[reply]

Scientific programmers, who had degrees in the physical sciences, said that a programmer was like a real gas, in that they would always take up the space that was available. Robert McClenon (talk) 16:59, 8 June 2018 (UTC)[reply]

How can I force Windows to show me files it's hiding?

I'm running Windows 7. I've just downloaded Python for Windows and the setup program put the executable in a directory called

C:\Users\TheUser\AppData\Roaming\Microsoft\Windows\Start Menu\Programs\Python 3.6\

When I try to look for that directory with either Explorer or the Command Prompt shell, it doesn't appear in the listing either Explorer or the shell "dir" command shows.

For example the directory C:\Users\TheUser\AppData\ doesn't appear at all (let alone its subdirectories).

Why is that? And how can I force Windows to display a true listing of the contents of directories instead of it hiding some directories and files?

Thanks. Basemetal 21:05, 31 May 2018 (UTC)[reply]

Windows 7

Select the Start button, then select Control Panel > Appearance and Personalization.

Select Folder Options, then select the View tab.

Under Advanced settings, select Show hidden files, folders, and drives, and then select OK. AboutFace 22 (talk) 22:25, 31 May 2018 (UTC)[reply]

Great. Thanks. It worked for Explorer. That does the job for all my practical requirements. Thanks. But I'm curious: the Command Prompt still refuses to show me those "hidden files, folders, and drives". Is there any way to change that? Thanks. Basemetal 22:57, 31 May 2018 (UTC)[reply]

dir /A:H is supposed to show you the hidden files. dir /AH may also work. references is "help dir" Graeme Bartlett (talk) 07:21, 1 June 2018 (UTC)[reply]

dir /AH shows only hidden files; dir /A shows all files (and directories), whatever their attributes. AndrewWTaylor (talk) 08:51, 1 June 2018 (UTC)[reply]

Many thanks to all three. Basemetal 13:03, 1 June 2018 (UTC)[reply]

Resolved

What does the .tar.gz.sig file do?

I'm running Windows 7. I'm trying to get source code of a program residing in this directory and I can see it is in the form of a tar archive (extension .tar.gz). Next to it there is a very small file with extension .tar.gz.sig. Can anyone tell me what it does? Do I need to download it also in order to unpack the archive? And one other question on tar: Is tar only used to compress source code or could there be executables in that tar archive? I'm looking for source code only. Thanks. Basemetal 21:17, 31 May 2018 (UTC)[reply]

It's probably a digital signature made using PGP or possibly GPG. You don't need it, if you trust that the .tar.gz file is genuine. But if you have it, then you can verify the signature to make sure no one has tampered with the .tar.gz file on its way to you.

(Could such an attacker also have tampered with the .sig file? Sure. But they can't generate a valid signature. Provided of course that you believe the public key you have for the signer.) --Trovatore (talk) 21:45, 31 May 2018 (UTC)[reply]

Thank you Trovatore. How about the other question: is tar used for source code only (not for binaries)? That is, am I certain to find source code only in the archive I've mentioned? Cause that's what I'm looking for. Thanks. Basemetal 13:06, 1 June 2018 (UTC)[reply]

No, from a technical perspective, tar can be used for any sort of data. There's no reason they couldn't put binaries in there. But in this sort of online repository, I think they usually don't. --Trovatore (talk) 18:19, 1 June 2018 (UTC)[reply]

Thanks. I asked the wrong question. Since tar does not in itself compress, just archives, as you say, it can be used for anything. What I was actually wondering was if it made sense to gzip binaries. (Generally speaking, not necessarily in this kind of ftp repository, which you say usually does not contain binaries). Basemetal 19:58, 1 June 2018 (UTC)[reply]

It depends on the sort of binary. Executable binaries tend to be highly compressible, though not as much as text. Binary formats that are designed to be compact, like JPEG, tend to be less compressible. Sometimes the compressed file will actually be slightly larger than the original. --Trovatore (talk) 20:24, 1 June 2018 (UTC)[reply]

Grazie Trovatore. Basemetal 20:38, 2 June 2018 (UTC)[reply]

how can a script kill its own offspring?

How can I write a bash script that does this?

command &
command &
command &
sleep 3600
kill everything spawned above

That is, let each of the spawned commands run (mostly sleeping) for an hour, then stop. —Tamfang (talk) 21:41, 31 May 2018 (UTC)[reply]

kill them using their job number:

  kill %1 
  kill %2
  kill %3

--Finlay McWalter··–·Talk 22:58, 31 May 2018 (UTC)[reply]

Are these numbers local to the script? Before this script runs, %1 could easily be something else. —Tamfang (talk) 23:39, 31 May 2018 (UTC)[reply]

Each shell process has its own job list. You can source a script into an existing shell (and even pass it arguments!), but if you run it normally (via shebang or manual bash foo.sh) it's separate. --Tardis (talk) 03:14, 1 June 2018 (UTC)[reply]

They're job numbers, not pids. -- Finlay McWalter··–·Talk 08:28, 1 June 2018 (UTC)[reply]

It worked, thanks. —Tamfang (talk) 18:38, 2 June 2018 (UTC)[reply]