• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

electron++

STL e a classe string

9 mensagens neste tópico

Já li algures que a STL e a classe String do C++ são lentos...

é mesmo verdade ou é mais um hoax?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Define lentos...

Independentemente da definição de lento, por mais lentos que sejam, não me recordo de ver alguém a fazer optimização em aplicações mexendo na STL ou em Strings...

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Em relação a classe string já me disseram que é mais lenta do que usar os tradicionais vectores de char...

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

E' bastante mais lenta que o classico char *.

Se o teu programa fizer trabalho pessado de manipulação de strings, o melhor e' fazer tudo "a' unha".

Uma vez exprementei por ao lado implementacoes iguais, uma em c (com char *) e outra em c++ (com std::string), que geravam todas as combinações de strings de determinado tamanho:

char *:         42.68user 0.18system 0:54.35elapsed 78%CPU
std::string:  220.73user 0.62system 4:22.38elapsed 84%CPU

Fazem exatamente a mesma coisa, e' claro que este e' um exemplo extremo, a menos que de facto um programa manipule bastante strings a versatibilidade da std::string compensa, mas se precisares de poder bruto...

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Se estás a falar em arrays de char, é natural que seja ligeiramente mais rápido, dado o processamento interno para garantir a existência de espaço, os cálculos para determinar o tamanho, etc. Mas essa diferença de velocidade é negligenciável, porque no fim existem muitas facilidades e comodidades no uso de strings STL relativamente às strings de C, as quais poderão poupar processamento a médio prazo. É uma questão de decidir se são necessárias ou não.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

eu tou bastante habituado ao vectores de char mas o C++ tem muitas vantagens realmente...

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Tudo o que implementes por ti tem a tendência a ser (ligeiramente) mais rápido porque não tens todas as preocupações na implementação como acessos a posições inválidas ou mudança de tamanho dos vectors por exemplo. Uma coisa que desaconselho é a classe "priority_queue", por experiência própria, sei que é bastante mais lenta do que utilizar as funções "push_heap" e "pop_heap" da biblioteca "algorithm" (esta biblioteca tem muitos algoritmos e muito úteis).

Para casos em que todos os décimos de segundo contem, usa implementações à lá C. Senão usa a STL. Normalmente o código fica muito reduzido e fácil de detectar erros.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Para concursos eu estava a pensar em usar a STL.

Existem algoritmos que dão muito jeito, ex: Pesquisa Binária

Não é que uma pesquisa binária seja difícil de implementar, antes pelo contrário mas já é o suficiente para nos roubar uns preciosos 5 minutos...

Por isso implementar tudo "à lá C" não se pode dizer que é uma solução muito rentável em concursos...

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

O lower_bound e upper_bound acho que são muito mais úteis do que a pesquisa binária.

Em problemas de strings com limites baixos ou em que recebas strings como input mas depois trabalhes sobre outra coisa, o uso de stl não deve ser problema. Exemplo: ler um grafo onde os nós são dados como os nomes das cidades - "Porto Lisboa 300" representando uma ligação do porto para lisboa com custo 300. Eu costumo usar nestes casos um map<string,int> onde coloco os nomes das cidades como chave e obtenho o seu indice no grafo.

edit: fica aqui um exemplo de parte da minha solução para deste problema.

int main()
{
int nc , i , j , ind ,  n , e , c;
map<string,int>::iterator it;
string a , b;
cin >> nc;
while (nc--) {
	cin >> n >> e;
	g.init(n);   // inicializar o grafo com "n" vertices
	map<string,int> m;  // map com os indices das cidades

	ind = 0;
	while (e--) {
		cin >> a >> b >> c;
		it = m.find(a);                 // obtem o indice da cidade 'a'. senão existir adiciona-a ao map
		if ( it == m.end())
			m[a] = i = ind++;
		else
			i = it->second;
		it = m.find(b);
		if ( it == m.end())
			m[b] = j = ind++;
		else
			j = it->second;
		g.addEdge( i , j, c );  // adicionar edge  i->j com peso c ao grafo g
	}
	if (nc)
		printf("%d\n\n", kruskal(g));   // algoritmo de kruskal para calcular a minimum spanning tree
	else
		printf("%d\n", kruskal(g));
}
return 0;
}

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!


Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.


Entrar Agora