high efficiency vector using right value reference and std::move

#include <iostream>
#include <cstdlib>
#include <cstring>
using namespace std;
class Element {
private:
    int number;
public:
    Element() : number(0) {
        cout << "ctor" << endl;
    }
    Element(int num) : number(num) {
        cout << "ctor" << endl;
    }
    Element(const Element& e) : number(e.number) {
        cout << "copy ctor" << endl;
    }
    Element(Element&& e) : number(e.number) {
        cout << "right value ctor" << endl;
    }
    ~Element() {
        cout << "dtor" << endl;
    }
    void operator=(const Element& item) {
        number = item.number;
    }
    bool operator==(const Element& item) {
        return (number == item.number);
    }
    void operator()() {
        cout << number;
    }
    int GetNumber() {
        return number;
    }
};

template<typename T>
class Vector {
private:
    T* items;
    int count;
public:
    Vector() : count{ 0 }, items{ nullptr } {

    }
    Vector(const Vector& vector) : count{vector.count} {
        items = static_cast<T*>(malloc(sizeof(T) * count));
        memcpy(items, vector.items, sizeof(T) * count);
    }
    Vector(Vector&& vector) :count{ vector.count }, items{ vector.items } {
        vector.items = nullptr;
        vector.count = 0;
    }
    ~Vector() {
    }
    T& operator[](int index){
        if (index<0||index>=count) {
            cout<<"invalid index"<<endl;
            return items[0];
        }
        return items[index];
    }
    int returnCount(){
        return count;
    }
    void Clear() {
        for (int i = 0; i < count; i++)
        {
            items[i].~T();
        }
        count = 0;
        items = nullptr;
    }

    void Add(const T& item) {
        T* newItems = static_cast<T*>(malloc(sizeof(T) * (count + 1)));
        int i;
        for (i = 0; i < count; i++)
        {
            new(&newItems[i])T(move(items[i]));
        }
        new(&newItems[count])T(move(item));
        for (int i = 0; i < count; i++)
        {
            items[i].~T();
        }
        count++;
        items = newItems;
    }
    bool Insert(const T& item,int index) {
        if (index < 0 || index >= count)
        {
            return false;
        }
        T* newItems = static_cast<T*>(malloc(sizeof(T) * (count + 1)));
        int i;
        for (i = 0; i < index; i++)
        {
            new(&newItems[i])T(move(items[i]));
        }
        new(&newItems[index])T(move(item));
        for (i = index; i < count; i++)
        {
            new(&newItems[i+1])T(move(items[i]));
        }
        for (i = 0; i < count; i++)
        {
            items[i].~T();
        }
        count++;
        items = newItems;
        return true;
    }
    bool Remove(int index) {
        if (index < 0 || index >= count)
        {
            return false;
        }
        T* newItems = static_cast<T*>(malloc(sizeof(T) * (count - 1)));
        int i;
        for (i = 0; i < index; i++)
        {
            new(&newItems[i])T(move(items[i]));
        }
        for (i = index + 1; i < count; i++)
        {
            new(&newItems[i-1])T(move(items[i]));
        }
        for (i = 0; i < count; i++)
        {
            items[i].~T();
        }
        count--;
        items = newItems;
        return true;
    }
    int Contains(const T& item) {
        for (int i = 0; i < count; i++)
        {
            if (items[i] == item)
            {
                return i;
            }
        }
        return -1;
    }
};

template<typename T>
void PrintVector(Vector<T>& v) {
    int count = v.returnCount();
    for (int i = 0; i < count; i++)
    {
        v[i]();
        cout << " ";
    }
    cout << endl;
}

int main() {
    Vector<Element> v;
    for (int i = 0; i < 4; i++) {
        Element e(i);
        v.Add(e);
    }
    PrintVector(v);
    Element e2(4);
    if (!v.Insert(e2, 10))
    {
        v.Insert(e2, 2);
    }
    PrintVector(v);
    if (!v.Remove(10))
    {
        v.Remove(2);
    }
    PrintVector(v);
    Element e3(1), e4(10);
    cout << v.Contains(e3) << endl;
    cout << v.Contains(e4) << endl;
    Vector<Element> v2(v);
    Vector<Element> v3(move(v2));
    PrintVector(v3);
    v2.Add(e3);
    PrintVector(v2);
    return 0;
}

output:

ctor
copy ctor
dtor
ctor
right value ctor
copy ctor
dtor
dtor
ctor
right value ctor
right value ctor
copy ctor
dtor
dtor
dtor
ctor
right value ctor
right value ctor
right value ctor
copy ctor
dtor
dtor
dtor
dtor
0 1 2 3 
ctor
right value ctor
right value ctor
copy ctor
right value ctor
right value ctor
dtor
dtor
dtor
dtor
0 1 4 2 3 
right value ctor
right value ctor
right value ctor
right value ctor
dtor
dtor
dtor
dtor
dtor
0 1 2 3 
ctor
ctor
1
-1
0 1 2 3 
copy ctor
1 
dtor
dtor
dtor

Memo on C Language Programming

Starting yesterday I have been reading the official manual of C programming language from GNU. I have finished 17 chapters out of 20-something chapters of the whole manual. I realized that the best way to learn an open-source stuff is indeed to read the documentation/help manual.

Yesterday I covered basic knowledge of the programming language such as type, expression, function, and pointer. It didn’t take much time because I have read other materials on C before. I did spend some time understanding pointers since in Java there is no explicit definition of pointer.

Today’s new materials include IO, String operation and “making” a program with multiple C source code files. I’m going to write down here things new to me.

 

  1. File IO:
#include <stdio.h>
#include <stdlib.h>

int main() {
	FILE *stream;
	stream = fopen("shit.dat", "w");
	int my_array[2][2] =
	{
		{1,2},
		{3,4}
	};
	size_t object_size = sizeof(int);
	size_t object_count = 4;

	if (stream == NULL) {
		printf("shit.dat could not be created\n");
		exit(0);
	}
	printf("file opened for writing\n");
	fwrite(&my_array, object_size, object_count, stream);
	fclose(stream);
	
	stream = fopen("shit.dat", "r");
	if (stream == NULL) {
		printf("shit.dat could not be read\n");
		exit(0);
	}
	printf("file opened for reading\n");
	fread(&my_array, object_size, object_count, stream);
	fclose(stream);

	for (int i = 0; i < 2; i++) {
		for (int j = 0; j < 2; j++) {
			printf("%d ", my_array[i][j]);
		}
		printf("\n");
	}
	return 0;
}

Most important functions for input/output with files would be fopen, fclose, fread, fwrite, getline and fprintf. According to the manual, it is suggested to use fread, getline and fwrite since they are safer than the rest, some of which are already deprecated. It’s worth noting that the second and the third parameters of fwrite and fread are of type size_t. Other than this, this part is pretty easy.

 

2. Combination of getline and sscanf

getline is a safe method, if you pass in an uninitialized string pointer, the program will create a buffer of a proper size for you and populate the variable. However, if you use methods like scanf instead, you may encounter buffer overflow errors, which can be very common. getline returns a line of text before a linebreak from a stream, which can be either stdin or a file.

Then, sscanf is used to read stuff of a specific type or a format from the string. This combination, according to the manual, is much better than using scanf alone, since it avoids many errors.

Example code:

#include <stdlib.h>
#include <stdio.h>

int main()
{
	int args_assigned = 0;
	size_t nbytes = 2;
	char *my_string;
	int int1, int2, int3;

	while (args_assigned != 3)
	{
		puts("Please enter three integers separated by whitespace.");
		my_string = (char *) malloc(nbytes + 1);
		getline(&my_string, &nbytes, stdin);
		args_assigned = sscanf(my_string, "%d %d %d", &int1, &int2, &int3);
		if (args_assigned != 3)
		{
			puts("Invalid input!");
		}
		else
		{
			printf("Three integers: %d %d %d\n", int1, int2, int3);
		}
	}
	return 0;
}

It doesn’t matter that my_string is initialized with a very small size: getline will take care of that.

 

3. ARGP

ARGP is such a strong tool!! With this, it’s very easy to parse parameters passed to the program and provide the users with usage explanations and documentations interactively.

The boss function is argp_parse, which takes four parameters: 1. parameter options, in a struct type, 2. a function to handle the option and parameter fields, 3. a string describing the arguments format, 4. a string that documents the program.

There are so many options available for customization. Although it’s hard to remember all of the parameter types and requirements, in actual development process I can just copy the old example piece of code and continue happily from there.

Example code:

#include <stdio.h>
#include <argp.h>

const char *argp_program_version = "argex 1.0";
const char *argp_program_bug_address = "<han.yu@duke.edu>";

/* This structure is used by main to communicate with parse_opt. */
struct arguments
{
	char *args[2];
	int verbose;
	char *outfile;
	char *string1, *string2;
};

/*
 * 	OPTIONS. Field 1 in ARGP.
 * 	Order of fields: {NAME, KEY, ARG, FLAGS, DOC}.
*/
static struct argp_option options[] = 
{
	{"verbose", 'v', 0, 0, "Produce verbose output"},
	{"alpha", 'a', "STRING1", 0, "Do something with STRING1 related to the letter A"},
	{"bravo", 'b', "STRING2", 0, "Do something with STRING2 related to the letter B"},
	{"output", 'o', "OUTFILE", 0, "Output to OUTFILE instead of to standard output"},
	{0}
};

/*
 * PARSER. Field 2 in ARGP.
 * Order of parameters: KEY, ARG, STATE.
*/
static error_t parse_opt (int key, char *arg, struct argp_state *state)
{
	struct arguments *arguments = state->input;
	switch (key)
	{
		case 'v':
			arguments->verbose = 1;
			break;
		case 'a':
			arguments->string1 = arg;
			break;
		case 'b':
			arguments->string2 = arg;
			break;
		case 'o':
			arguments->outfile = arg;
			break;
		case ARGP_KEY_ARG:
			if (state->arg_num >= 2)
			{
				argp_usage(state);
			}
			arguments->args[state->arg_num] = arg;
			break;
		case ARGP_KEY_END:
			if (state->arg_num < 2)
			{
				argp_usage(state);
			}
			break;
		default:
			return ARGP_ERR_UNKNOWN;
	}
	return 0;
}

/*
 * ARGS_DOC. Field 3 in ARGP.
 * A description of the non-option command-line arguments that we accept.
*/
static char args_doc[] = "ARG1 ARG2";

/*
 * DOC. Field 4 in ARGP.
 * Program documentation.
*/
static char doc[] = 
"argex -- A program to demonstrate how to code command-line options and arguments.\vFrom the GNU C Tutorial.";

/*
 * The ARGP structure itself.
*/
static struct argp argp = {options, parse_opt, args_doc, doc};

/*
 * The main function.
 * Notic how now the only function call needed to process all command-line options and arguments nicely is argp_parse.
*/
int main (int argc, char **argv)
{
	struct arguments arguments;
	FILE *outstream;
	char waters[] = "Some long sentence";

	/* Set argument defaults */
	arguments.outfile = NULL;
	arguments.string1 = "";
	arguments.string2 = "";
	arguments.verbose = 0;

	/* Where the magic happens */
	argp_parse(&argp, argc, argv, 0, 0, &arguments);

	/* Where do we send output? */
	if (arguments.outfile)
			outstream = fopen(arguments.outfile, "w");
	else
		outstream = stdout;

	/* Print argument values */
	fprintf(outstream, "alpha = %s\nbravo = %s\n\n", arguments.string1, arguments.string2);
	fprintf(outstream, "ARG1 = %s\nARG2 = %s\n\n", arguments.args[0], arguments.args[1]);

	/* If in verbose mode, pring song stanza */
	if (arguments.verbose)
		fprintf(outstream, "%s", waters);

	return 0;
}

When it runs it really behaves like a “legit” GNU open source software!

 

I also read about makefiles: its rules, targets and variables that can simplify the code. I guess tomorrow I’ll read more about C. If I finish this manual I’ll take a look at the GNU Make manual.

Anyway, it’s cool that a book originally written 30 years ago is still not outdated at all.