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

Marfig

Comparaçao de stack iterators consecutivos.

14 mensagens neste tópico

Ok... passei o fim de semana todo nisto. Estou cansado, lá descobri o bug, mas preciso de uns gurus C++ para discutir o assunto... Eu não sei se isto é um erro específico do g++, do C++ Standard ou simplesmente há algo que me está a escapar. O código em que estou a trabalhar é complexo, portanto reduzi o problema ao código mais simples que possa colocar aqui...

Em tenho dois vectores do mesmo tipo e pretendo processá-los por ordem. Primeiro o vector foo, depois o vector bar...

vector<T> foo, bar;

T pode ser built-in ou user-defined. Não interessa.

for (vector<T>::iterator iter = foo.begin(); iter != bar.end(); ++iter) {

  if ( iter == foo.end() ) iter = bar.begin();

  /* trata iter */

}

Á partida não existe nada de errado neste código. Afinal, eu posso comparar iterators de dois objectos diferentes, o standard diz que sim (24.1(6) e 24.1.3(1) parecem-me os mais relevantes).

Mas esta lógica que usei para num mesmo for() processar dois vectores deu-me uma das maiores dores de cabeça dos últimos tempos. O que se passa é que se foo e bar são alocados um a seguir ao outro no stack, foo.end() == bar.begin() devolve true!!!

Mas não poderia nunca porque - e passo a citar 24.1.3(1) - "If a and b are equal, then either a and b are both dereferenceable or else neither is dereferenceable." Ora, foo é definitivamente dereferenceable, mas bar não é. Portanto nunca poderiam ser iguais de acordo com o standard.

Ora isto coloca um problema sério. É que o standard é claro em definir que eu posso comparar dois iterators de diferentes objectos (e nós sabemos o útil que isso pode ser em alguns casos raros), mas não faz provisões para este potencial problema de alocação - ou pelo menos eu não encontrei essa informação em lado nenhum. Portanto parece-me existir um bug no standard e o g++ está a proceder correctamente ao retribuir true. Mas por outro lado, o standard é claro em 24.1.3(1), só que não vejo como é que um compilador poderia alguma vez implementar este ponto.

Discutam, por favor.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Hmm, não tenho muita experiência com iteradores em C++, e isto parece-me um caso complexo.

Experimenta com o compilador Visual C++, a ver o que dá. :(

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

O problema e transversal a outros compiladores ao que me parece. Só testei no Watcom e no Visual C++ 2005 Express.

O problema é o facto de que se os dois vectors são consecutivos, naturalmente foo.end() e bar.begin() apontam para o mesmo endereço ( bar.at(0) ). Ora não se pode pedir a um compilador para alocar vectores com padding para evitar esta situação, portanto o problema parece-me ser do standard que deve tornar a comparação entre iterators de vários objectos, undefined behavior. Parece-me a única opção viável. Mas a meu ver o standard portanto contém um bug uma vez que não faz esta provisão.

É que inclusivamente estive a olhar para o código da STL e a tentar imaginar formas da library implementar os seus containers (pelo menos os que implementam forward iterators) de modo a evitarem que objectos fossem alocados imediatamente uns a seguir aos outros. A solução existe, passa pela alocação de memória através de member functions como reserve(). Mas este é um processo que não responde ao problema de uma forma directa uma vez que obriga à alocação excessiva e aumenta a carga em memória.

O que decidi fazer por enquanto é passar a tratar comparação entre iterators de objectos diferentes como undefined behavior, uma vez que sinceramente cada vez mais me convenço que isto é um bug no standard. Mas gostaria de saber outras opiniões.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Eu ainda não consegui perceber exactamente qual é o problema, e depois deste post ainda fiquei mais confuso :\

Que foo.end()==bar.begin() seja verdade, parece-me minimamente aceitável, mas não me pareceu que fosse este o problema... O se é este o problema, ainda não percebi onde é que ele se levanta.

No primeiro post, tinhas falado em foo.end()==bar.end(), o que a devolver verdade, levantaria problemas. Mas acho que não faz qualquer sentido isto acontecer. Aqui, não vejo onde é que a alocação dos vectores levanta problemas.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

No primeiro post, tinhas falado em foo.end()==bar.end(),

Oops. Meu erro. Já corrigi no primeiro post. O texto correcto é:

[...]a seguir ao outro no stack, foo.end() == bar.begin() devolve true!!!

O problema aqui Rui, é que este resultado não obedece a 24.1.3(1) - "If a and b are equal, then either a and b are both dereferenceable or else neither is dereferenceable.". Como podes reparar, foo.end() não é dereferenceable, mas bar.begin() é. Deveria devolver false.

Agora imagina que os dois vectors não estão alocados um a seguir ao outro. Então o resultado da expressão acima seria sempre false. Ou seja, uma avaliação determinística dos dois iterators é dependente da sua posição no stack. Ora, isto tem um nome... undefined behavior. Mas não é isso que o standard diz em 24.1(6):

"An iterator j is called reachable from an iterator i if and only if there is a finite sequence of applications of the expression ++i that makes i == j. If j is reachable from i, they refer to the same container."

Portanto se chegas a j através de i, então ambos pertencem ao mesmo container... mas o que tens aqui é uma situação em que se os dois containers são consecutivos (e isto só acontece quando são consecutivos) em que i == j, pese embora i e j pertençam a dois containers distintos. Portanto o resultado também não obedece a 24.1(6).

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Para o caso qualquer T serve. User defined ou built-in. Podes por exemplo testar com int.

Em todo o modo já obtive resposta para isto num email para o Josuttis a semana passada.

É realmente um erro do standard na sua opinião que não específica a comparação entre iterators de objectos diferentes como sendo undefined. O texto não faz esta referência o que, por omissão, declara a operação como correcta.

A solução claro está é - e de acordo com as suas próprias palavras - "don't try to outsmart the compiler and don't ever try to be too clever. Split the loop". :cheesygrin:

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

À primeira vista não estava a ver o facto de foo.end() ser igual a bar.begin() fica uma dica para o futuro :cheesygrin:

portanto o problema parece-me ser do standard que deve tornar a comparação entre iterators de vários objectos, undefined behavior. Parece-me a única opção viável. Mas a meu ver o standard portanto contém um bug uma vez que não faz esta provisão.

Adiante. Como é que achas possível implementar isso? Como é que ao implementar o operador de comparação, consegues saber que os 2 iteradores apontam para objectos diferentes? Eu creio que no fundo, um iterador só tem o endereço de memória do objecto...

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Adiante. Como é que achas possível implementar isso? Como é que ao implementar o operador de comparação, consegues saber que os 2 iteradores apontam para objectos diferentes? Eu creio que no fundo, um iterador só tem o endereço de memória do objecto...

É. Realmente não me parece que seja possível. Os iterators teriam que guardar informação sobre o objecto a que se referem e isso iria contra qualquer coisa. :cheesygrin: Não sei bem o quê assim de repente, mas estou certo que algum príncipio seria derrotado. Bom, iria aumentar substancialmente a sua alocação em memória. Isso era certo.

No fim é um problema do standard que esperemos deixará mais claro no C++0x que a operação é undefined e não se deve portanto comparar iterators de objectos diferentes.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Engraçado. O Visual Studio 2008 Professional não deixa passar esse "erro". Em modo debug, uma asserção falha na 1ª passagem do ciclo for. Ele testa se os contentores são iguais, e se não forem lança alguns erros e termina a execução.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Ah. Interessante. Mais uma razão para talvez fazer o upgrade para o 2008. Tenho um post algures aqui nos grupos do C++ sobre o VC++ 2008...

O código passa no gcc e VC++ 2005.

Da lista, quais os erros que te parecem mais relevantes, TheDark?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

O 1º:

http:

ao navegar pelo call stack vai adar aqui:

Err01CallStack1.png

e o 2º:

http:

leva directamente ao mesmo sitio da imagem anterior:

[/img]

Faltam as imagens, estou com dificuldades no upload para o imgshack, quando conseguir enviar meto tudo aqui.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Está a guardar uma referência ao container. Interessante...

Não vale a pena preocupares-te mais TheDark. Obrigado. Já deu para perceber como o faz. E a julgar pela macro a referência só é guardada em modo Debug.

Muito apropriado. A única coisa a apontar é o facto de considerar isto um assert fail. Correcto, correcto, seria um warning e não um erro. Mas mais uma vez devendo ser isto undefined behavior o compilador é livre de escolher o modo como quer lidar com o problema.

E para todos os efeitos posso sempre retirar a definição _HAS_ITERATOR_DEBUGGING naqueles raros casos em que preciso realmente de comparar iterators diferentes.

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