Murilo :P

C++, Computação, Programação, Web e afins :)

Posts Tagged ‘c

Arrays with negative indexes

with 2 comments

When we to deal with negative ranges in arrays and those ranges can be negative, we do shifts so we can use natural indexes. For example, if we’re given a range from -50 to 20, usually we allocate an array of 70 positions and when indexing an element we shift by +50 so the position -50 is actually stored on the position 0.

These days, while doing random stuff on the internet, I’ve figured that we can easily work with arrays not only starting from zero but starting from any integer we want. To illustrate that, I wrote this function which allocate sz elements of type T where the array’s first element is in min_index position:

template <typename T>
T* alloc(size_t sz, int min_index = 0)
{
	return (new T[sz]) - min_index;
}

An example of use:

int main()
{	
	char* p = alloc<char>(70, -50);
	
	p[-50] = 'h'; p[-49] = 'e'; 
	p[-48] = 'l'; p[-47] = 'l';
	p[-46] = 'o'; p[-45] = '\0';
	
	std::cout << &p[-50] << '\n';
	
	for (int i = -50; i < -45; ++i) {
		std::cout << p[i] << '\n';
	}
}

The result, as expected:

hello
h
e
l
l
o

Written by Murilo Adriano

29 de October de 2012 at 14:24

Posted in C/C++, Programação

Tagged with , ,

Feature turning into bug

with 2 comments

Team Phd na Área

Me and one of Unicamp teams

Background

A few days ago, after a sub-regional phase of ACM ICPC, one integrant of a team I’m coaching claimed that there was a bug in their C++ compiler. The team had to solve a geometrical problem, and, for that he implemented a class representing a point and an overload for operator*:

 

class point
{
 public:
     double x, y;

     point(double d) : x(d), y(d) {}
     point(const point& p) : x(p.x), y(p.y) {}     

     point operator*(const point& p)
     {
         // ...
         return result;
     }
};

After coding, he’ve compiled the code and tested with sample input tests. But the results were wrong. After some time debugging he found that the problem was happening because in some part of the code, he was calling point::operator* passing a double as argument and he didn’t implement that overload for operator*. The question was: why the compiler didn’t issued errors?

Implicit object construction

C++ has a feature which allow us to construct a object implicitly when the object’s type have a constructor which accepts one argument. For example, if you have a function which takes a std::string as argument, you can call that function passing a c-style string:

void printstr(std::string s)
{
    std::cout << s << std::endl;
}

// ...

printstr("Foo bar baz"); // Implicitly passes std::string("Foo bar baz");

The Google C++ Style Guide states:

Normally, if a constructor takes one argument, it can be used as a conversion. For instance, if you define Foo::Foo(string name) and then pass a string to a function that expects a Foo, the constructor will be called to convert the string into a Foo and will pass the Foo to your function for you.

So, what happened on the contestant program was something like:

point pt;
double d;

// ...

pt = pt * d; // doesn't find an operator* receiving a double
             // so, it is evaluated as pt = pt * point(d);

This feature can lead in many undesired conversions, so it is recommended to “turn off” this type of object construction by declaring constructors with one single argument explicit. The Google C++ Style Guide requires that all single argument constructors to be explicit, except in cases in which the class is a transparent wrapper for other class.

So, the modified code would be something like:

class point
{
 public:
     double x, y;

     explicit point(double d) : x(d), y(d) {}
     point(const point& p) : x(p.x), y(p.y) {}     

     // ...  
};

Some Links

Written by Murilo Adriano

18 de September de 2012 at 19:11

Fast and Easy Levenshtein distance using a Trie (in C++)

with 8 comments

I implemented this clever algorithm described on Steven Hanov’s blog in C++. Actually this algorithm is a bit different from the original because I wanted to know what is the least Levenshtein distance given a word.

#include <iostream>
#include <map>
#include <string>
#include <vector>
#include <algorithm>
#include <cctype>

/*
 * Algorithm: Edit distance using a trie-tree (Dynamic Programming)
 * Author: Murilo Adriano Vasconcelos <muriloufg@gmail.com>
 */

using namespace std;

// Trie's node
struct trie
{
	typedef map<char, trie*> next_t;

	// The set with all the letters which this node is prefix
	next_t next;

	// If word is equal to "" is because there is no word in the
	//	dictionary which ends here.
	string word;

	trie() : next(map<char, trie*>()) {}

	void insert(string w)
	{
		w = string("$") + w;
		
		int sz = w.size();
		
		trie* n = this;
		for (int i = 0; i < sz; ++i) {
			if (n->next.find(w[i]) == n->next.end()) {
				n->next[w[i]] = new trie();
			}

			n = n->next[w[i]];
		}

		n->word = w;
	}
};

// The tree
trie tree;

// The minimum cost of a given word to be changed to a word of the dictionary
int min_cost;

//
void search_impl(trie* tree, char ch, vector<int> last_row, const string& word)
{
	int sz = last_row.size();

	vector<int> current_row(sz);
	current_row[0] = last_row[0] + 1;

	// Calculate the min cost of insertion, deletion, match or substution
	int insert_or_del, replace;
	for (int i = 1; i < sz; ++i) {
		insert_or_del = min(current_row[i-1] + 1, last_row[i] + 1);
		replace = (word[i-1] == ch) ? last_row[i-1] : (last_row[i-1] + 1);

		current_row[i] = min(insert_or_del, replace);
	}

	// When we find a cost that is less than the min_cost, is because
	// it is the minimum until the current row, so we update
	if ((current_row[sz-1] < min_cost) && (tree->word != "")) {
		min_cost = current_row[sz-1];
	}

	// If there is an element wich is smaller than the current minimum cost,
	// 	we can have another cost smaller than the current minimum cost
	if (*min_element(current_row.begin(), current_row.end()) < min_cost) {
		for (trie::next_t::iterator it = tree->next.begin(); it != tree->next.end(); ++it) {
			search_impl(it->second, it->first, current_row, word);
		}
	}
}

int search(string word)
{
	word = string("$") + word;
	
	int sz = word.size();
	min_cost = 0x3f3f3f3f;

	vector<int> current_row(sz + 1);

	// Naive DP initialization
	for (int i = 0; i < sz; ++i) current_row[i] = i;
	current_row[sz] = sz;
	
	
	
	// For each letter in the root map wich matches with a
	// 	letter in word, we must call the search
	for (int i = 0 ; i < sz; ++i) {
		if (tree.next.find(word[i]) != tree.next.end()) {
			search_impl(tree.next[word[i]], word[i], current_row, word);
		}
	}

	return min_cost;
}

The modification for match all words within a given Leveshtein distance and returning that set is trivial. Just modify the line 72 for storing that word if its Leveshtein distance is less than or equal to a given distance.

For more details, read this: Fast and Easy Levenshtein distance using a Trie
See ya!

Written by Murilo Adriano

1 de February de 2011 at 21:46

Como programar em C Orientado a Objetos

with 14 comments

Olá, hoje eu vou dar um tempo na série “Coisas simples de se fazer em C++ que alguns ainda complicam” e irei falar sobre uma experiência minha tentando alguma maneira de programar em C orientado a objetos.

Sei que muitos vão pensar “pra quê isso?” ou dizer que é péssimo fazer isso ou coisa parecida, mas o intuito desse post é outro: é mostrar o que é possível fazer ou até mesmo enxergar alguma utilidade nisso. Nesse blog, procuro colocar coisas diferentes, curiosidades sobre programação e linguagens, porque acho que conteúdo “normal” já existem em muitos lugares na grande rede.

O que me instigou a fazer isso foi um post no CODARE “C: Escondendo o conteúdo de structs com tipos incompletos” de autoria do Thiago Santos, no qual ele cita sobre usar com orientação a objetos em C.

Li, achei interessante e quis, vamos dizer assim, dar um cara mais parecida de orientação a objetos ao que ele fez.

O primeiro passo foi pensar em como funcionam os famosos objetos.
Uma classe em uma linguagem orientada a objetos geralmente tem 2 tipos de elementos:

  • Elementos de classe: elementos (funções e variáveis estáticas) que só são criados uma vez, todos os objetos da classe tem acesso ao mesmo elemento.
  • Elementos de instância (ou objeto): elementos (atributos) que são criadas para cada objeto instanciado.

Ou seja:

class Animal
{
        int age;
        std::string specie;
        static int count;
public:
        int birthday();
};

No exemplo acima, age e specie são elementos de instância, ou seja, cada objeto têm o seus próprios. Já count e birthday() são de classe, pois todos os objetos dessa classe utilizarão o mesmo. O que ocorre no caso de funções é que na chamada da função, um ponteiro do objeto chamador é passado para a função. Isso faz com que não precise a cada instância de objeto criar uma nova função já que elas fazem a mesma coisa.

Algo como:

Animal animal, animal2;

//lembrando que é APENAS uma ilustração do que acontece
//não é assim que é realmente implementado mas é a mesma idéia
//uma função só para todos os objetos de uma classe

animal.birthday(); //vtable::animal::birthday(&animal);
animal2.birthday(); //vtable::animal::birthday(&animal2);

A função birthday() é a mesma para as duas chamadas, o que muda é o ponteiro para os dados de cada objeto.

A minha implementação seguiu a idéia do Thiago Santos: uma classe person que tem os atributos name e age funções para instanciar, imprimir o nome e idade e deletar o objeto.

Vamos então dar uma olhada no nosso headerperson.h:

#ifndef PERSON_H__
#define PERSON_H__

//Incomplete type declaration
typedef struct person_private person_private;

typedef struct person {
	//"private" data.
	person_private* data;

	//"class" functions
	void (*free)();
	void (*print)();
} person;

//instatiate a new person
person* new_person(const char*, int);

//pointer to the actual person in the context
person* __actual_person;

//sets the actual person
person* _(person* obj);

#endif

Nosso header contém a declaração incompleta de person_private leia aqui para saber o porquê, a definição da nossa “classe” person, as declarações das funções new_person() e _() e um ponteiro __actual_person.

Nossa “classe” person contém um ponteiro data para os dados que não poderão ser acessíveis através do objeto (name, age) além de ponteiros para funções (que serão nossos “métodos”).

A função new_person simplesmente instancia um objeto do tipo person.

O ponteiro __actual_person irá funcionar como o ponteiro passado para as funções de classe. Através do ponteiro saberemos qual objeto chamou a função.

A função _() seta o ponteiro __actual_person para que as funções sejam corretamente chamadas. Nota: não é thread safe. (hehehe)

Vamos ao nosso person.c:

#include "person.h"
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

//private data... visible only by the functions below
struct person_private
{
	char* name;
	int age;
};

//a "manual destructor"
void free_person()
{
	free(__actual_person->data->name);
	free(__actual_person->data);
	free(__actual_person);
       
        puts("Person sucessfuly freed!\nBye");
}

//prints 
void print_person()
{
	printf("%s -: %d\n", __actual_person->data->name,
		 __actual_person->data->age);
}

person* new_person(const char* name, int age)
{

	//Allocate the object	
	person* new = (person*)malloc(sizeof(person));
	new->data = (person_private*)malloc(sizeof(person_private));
	
	//Initialize the data
	new->data->name = (char*)malloc(strlen(name) * sizeof(char) + 1);
	strcpy(new->data->name, name);

	new->data->age = age;

	//Set the functions pointers
	new->print = print_person;
	new->free = free_person;
	
	return new;
}

//must call the objects with this function
person* _(person* obj)
{
	__actual_person = obj;
	return obj;
}

O que temos aí é a função _() que seta o objeto atual (__actual_person) para que possa ser utilizado a função com o objeto certo, a função new_person que funciona como nosso construtor, as outras duas funções que são os “métodos da classe” print e free e a definição da estrutura person_private que contém os atributos da classe.
Os comentários ajudam no resto :).

Vamos então ver o main.c que é o nosso teste:

#include <stdio.h>
#include "person.h"

int main()
{
	//Instantiates 2 persons
	person* person1 = new_person("Murilo", 21);
	person* person2 = new_person("Rovane", 47);
	
	//print
	_(person1)->print();
	_(person2)->print();
	
	//free
	_(person1)->free();
	_(person2)->free();
}

Eis o resultado:

murilo@blacksheep:~/programacao/cobject$ gcc main.c person.c
murilo@blacksheep:~/programacao/cobject$ ./a.out
Murilo -: 21
Rovane -: 47
Person sucessfuly freed!
Bye
Person sucessfuly freed!
Bye

Nota: deve-se usar sempre a função _() para utilizar o objeto.

Fiquei pensando se tem como fazer uma espécie de gerador de classes nesse formato no próprio C (com macros por exemplo). Vou procurar saber se existe algo a respeito, são 04h40min da mardugada não estou mais com boas idéias.

Qualquer sugestão, bug, idéia, reclamação, estamos aí!

Written by Murilo Adriano

5 de August de 2009 at 04:50

Posted in C/C++, Programação

Tagged with , , , , ,

O que são enums e como utilizá-los melhor em C++

with 16 comments

C++

O que são os enums (C e C++)

Um enum (enumeração) é um tipo definido pelo usuário (programador) que consiste em constantes do tipo int nomeadas.

Um jeito tradicional de se declarar constantes em C e C++ é o seguinte:

#define BRASIL 0
#define ITALIA 1
#define PORTUGAL 2
#define ALEMANHA 3

E eis a maneira de fazer o mesmo utilizando enums:

enum
{
        BRASIL,
        ITALIA,
        PORTUGAL,
        ALEMANHA
};

Pode-se, alternativamente, criar um tipo para seu enum:

enum Paises
{
        BRASIL,
        ITALIA,
        PORTUGAL,
        ALEMANHA
};

E declarar uma variável desse tipo com:

Paises pais; //C++ apenas
enum Paises pais; //C e C++

Num enum igual a esses acima, a primeira constante recebe o valor 0 e as subsequentes recebem o valor da constante anterior mais 1. Ou seja, BRASIL é 0, ITALIA é 1, PORTUGAL é 2 e ALEMANHA é 3.
Podemos também atribuir valores manualmente às constantes como em:

enum Paises
{
        BRASIL = 2,
        ITALIA,  //ITALIA é igual a 3 (2 + 1)
        PORTUGAL = 1,
        ALEMANHA  //ALEMANHA é igual a 2 (1 + 1)
};

Como podemos perceber no exemplo anterior, a mesma regra se aplica para os enums com valores manuais, o que não tiver um valor explicitamente inserido receberá o valor do anterior somado em 1. Percebemos também que podem haver constantes com o mesmo valor (BRASIL == ALEMANHA == 2).

Conversão

A conversão de uma constante de um enum para um inteiro por exemplo é feita automaticamente. Já o contrário não deve ser permitido pelo compilador.

enum Paises
{
        BRASIL,
        ARGENTINA,
        VENEZUELA
};

...

int inteiro = VENEZUELA + 2; //4
Paises pais = 3; //ERRO

Uma melhor maneira de usar enums em C++

Veja o exemplo:

enum Paises
{
        BRASIL,
        ITALIA,
        ALEMANHA
};

enum Uvas
{
        RUBI,
        ITALIA,
        UMOUTROTIPODEUVA
};

Isso irá ocasionar um erro porque ITALIA já foi definido. A saida do meu compilador (g++ 4.3.2) foi a seguinte:

murilo@blacksheep:~/$ g++ enums.cpp
enums.cpp:14: error: conflicting declaration ‘ITALIA’
enums.cpp:8: error: ‘
ITALIA’ has a previous declaration as ‘Paises ITALIA’

Mas e agora?? Eu quero ter dois enums diferentes que representam coisas diferentes mas que podem ter a mesma constante. Como?

A resposta é namespaces!
Em C++ podemos declarar nossos enums dentro de namespaces e assim termos as constantes em espaços de nomes diferentes. Nada de conflito agora hein g++!!!

namespace Paises
{
enum
{
BRASIL,
ITALIA,
ALEMANHA
};
}

namespace Uvas
{
enum
{
RUBI,
ITALIA,
UMOUTROTIPODEUVA
};
}

//*…*//
//Modo de uso:

std::cout << Uvas::ITALIA; std::cout << Paises::ITALIA; [/code] É isso aí galera, até a próxima.

Written by Murilo Adriano

29 de May de 2009 at 01:28

Posted in C/C++, Programação

Tagged with , , ,

Linguagens de programação – C++ – Direito de defesa

with 28 comments

C++Um dia desses passeando por blogs ví um post que me chamou a atenção. O título é Linguagens de programação – C++ e, claro, chamou minha atenção, não apenas por causa do post assim com também por causa dos comentários sobre o post.

O objetivo desse post não é gerar um flame, até porque não atacarei nenhuma linguagem, só dissertarei sobre fatos.

Read the rest of this entry »

Written by Murilo Adriano

14 de November de 2008 at 01:12

Posted in C/C++, Programação

Tagged with , , ,

Como converter um número para uma std::string e vice-versa

with 9 comments

Que a biblioteca <iostream> oferece inúmeras facilidades para manipular I/O nós já sabemos mas, como converter um valor para uma std::string?

A bliblioteca <iostream> nos permite converter facilmente qualquer coisa para uma std::string usando a seguinte sintaxe (o exemplo a seguir converte um double, mas você pode substituir por qualquer coisa imprimível usando o operador <<): Read the rest of this entry »

Written by Murilo Adriano

1 de October de 2008 at 00:41

Posted in C/C++, Programação

Tagged with , , , , ,