参照のポインタについて

[教えてboy]

プログラミングの勉強を始めたばかりなので勘違いかもしれませんが
元のコード

コード:

#include <iostream>
#include <string>
#include<queue>
using namespace std;
enum {S = 0, A, B, C, D, E, F, G};

//#define CV

#define N 7
#define M 4


#ifndef CV
#define is_empty1() buff.empty()
#endif



// 隣接リスト
int adjacent[N + 1][M] = {
  {S},
  {B, C, S},
  {A, C, D, S},
  {A, B, E, S},
  {B, E, F, S},
  {C, D, G, S},
  {D, S},
  {E, S},
};

// 経路
typedef struct {
  int path[N];
  int len;
} Path;

// 現在地点を求める
int top(Path *p)
{
  return p->path[p->len - 1];
}

// 経路に頂点が含まれているか
bool visited(Path *p, int x)
{
  for (int i = 0; i < p->len; i++) {
    if (p->path[i] == x) return true;
  }
  return false;
}

// 経路の表示
void print_path(Path *p)
{
  for (int i = 0; i < p->len; i++){
    cout<<(char)('A'+p->path[i]-1);
  } 
  cout<<endl;
}

// キュー
#define Q 64

#ifdef CV
Path buff[Q];
int  front, rear;
#else
queue<Path>buff;
#endif

#ifdef CV
// 初期化
void init_queue(int start)
{
  buff[0].path[0] = start;
  buff[0].len = 1;
  rear = 1;
}
#else
void init_queue(int start){
    Path p;
    buff.push(p);
    buff.front().path[0]=start;
    buff.front().len=1;
}

#endif

#ifdef CV 
// データの取り出し
Path *deq(void)
{
  return &buff[front++];
}
#else
//参照のポインタを返してしまっている。
Path *deq(void){
    Path *p=&buff.front();
    buff.pop();
    return p;
}
#endif

#ifdef CV
// データの追加
void enq(Path *p, int x)
{
  buff[rear] = *p;
  buff[rear].path[p->len] = x;
  buff[rear++].len++;
}
#else
void enq(Path*p,int x){
    buff.push(*p);
    buff.back().path[p->len]=x;
    buff.back().len++;
}
#endif

#ifdef CV
// キューは空か
bool is_empty1(void)
{
  return front == rear;
}
#endif

// 幅優先探索
void bfs(int start, int goal)
{
  init_queue(start);
  while (!is_empty1()) {
    Path *p = deq();
    int x = top(p);
    if (x == goal) {
      print_path(p);
    } else {
      for (int i = 0; i < M; i++) {
        int y = adjacent[x][i];
        if (y == 0) break;
        if (!visited(p, y)) enq(p, y);
      }
    }
  }
}

int main(void)
{
  bfs(A, G);
  return 0;
}

ではgccではうまくいくのに
vc++コンパイラのcl.exeではうまくいかないので悩んでいたところ
デバッガで値を追ってみたところ
上記のコードのように参照のポインタを返してしまっていたことが問題だったようです。
そこで下記のコードのようにいったん値をほかの変数に格納してからそのポインタを返すようにしたところうまくいきました。

コード:

#include <iostream>
#include <string>
#include<queue>
using namespace std;
enum {S = 0, A, B, C, D, E, F, G};

//#define CV

#define N 7
#define M 4


#ifndef CV
#define is_empty1() buff.empty()
#endif



// 隣接リスト
int adjacent[N + 1][M] = {
  {S},
  {B, C, S},
  {A, C, D, S},
  {A, B, E, S},
  {B, E, F, S},
  {C, D, G, S},
  {D, S},
  {E, S},
};

// 経路
typedef struct {
  int path[N];
  int len;
} Path;

// 現在地点を求める
int top(Path *p)
{
  return p->path[p->len - 1];
}

// 経路に頂点が含まれているか
bool visited(Path *p, int x)
{
  for (int i = 0; i < p->len; i++) {
    if (p->path[i] == x) return true;
  }
  return false;
}

// 経路の表示
void print_path(Path *p)
{
  for (int i = 0; i < p->len; i++){
    cout<<(char)('A'+p->path[i]-1);
  } 
  cout<<endl;
}

// キュー
#define Q 64

#ifdef CV
Path buff[Q];
int  front, rear;
#else
queue<Path>buff;
#endif

#ifdef CV
// 初期化
void init_queue(int start)
{
  buff[0].path[0] = start;
  buff[0].len = 1;
  rear = 1;
}
#else
void init_queue(int start){
    Path p;
    buff.push(p);
    buff.front().path[0]=start;
    buff.front().len=1;
}

#endif

#ifdef CV 
// データの取り出し
Path *deq(void)
{
  return &buff[front++];
}
#else
//値のポインタを返すようにすればよい。
Path deq_p;
Path *deq(void){
    deq_p=buff.front();
    buff.pop();
    return &deq_p;
}
#endif

#ifdef CV
// データの追加
void enq(Path *p, int x)
{
  buff[rear] = *p;
  buff[rear].path[p->len] = x;
  buff[rear++].len++;
}
#else
void enq(Path*p,int x){
    buff.push(*p);
    buff.back().path[p->len]=x;
    buff.back().len++;
}
#endif

#ifdef CV
// キューは空か
bool is_empty1(void)
{
  return front == rear;
}
#endif

// 幅優先探索
void bfs(int start, int goal)
{
  init_queue(start);
  while (!is_empty1()) {
    Path *p = deq();
    int x = top(p);
    if (x == goal) {
      print_path(p);
    } else {
      for (int i = 0; i < M; i++) {
        int y = adjacent[x][i];
        if (y == 0) break;
        if (!visited(p, y)) enq(p, y);
      }
    }
  }
}

int main(void)
{
  bfs(A, G);
  return 0;
}

これはgccとcl.exeが違うのは明らかですが
これはgccとcl.exeで参照のポインタの扱いが違うということでいいんでしょうか？
gccでうまくいってしまうせいですごく悩むことになりましたが
どなたか知っている方お教えいただけないでしょうか。
あとｃ言語でのソースを参考に対応させながら書いたのでコードがぐちゃぐちゃでみにくくて
すいません。(;´Д｀)

[あんどーなつ]

質問の答えではないのですが、

Path *deq(void);
void enq(Path *p, int x);

というインターフェースからはやばい臭いが結構します。

queue<Path> buff;
は、Pathのポインタの集まり（コレクション）ではなく、Pathの集まりです。
つまり、sizeof(Path) = (N+1) * sizeof(int)バイトのデータをそのままコピーして扱います。
なので、queueを使うならば

Path deq(void);
void enq(Path p, int x);

が正しいです。もし、データをコピーしたくない場合は、

queue<Path*> buff;

としなければならないでしょう。この場合、new, deleteするのに神経を使うのであまりお勧めはしないです。

[みけCAT]

sizeof(Path) = (N+1) * sizeof(int)バイトのデータをそのままコピーして扱います。
なので、queueを使うならば

Path deq(void);
void enq(Path p, int x);

が正しいです。

deqではいいかもしれませんが、enqでは無駄なコピーを避けるために参照を使った方がいい気がします。

コード:

void enq(const Path& p, int x);

[みけCAT]

queue::pop - C++ Reference
によると、pop()ではコンテナのpop_front()が呼び出されます。
queue - C++ Reference
によると、std::queueの標準のコンテナはstd::dequeです。
deque::pop_front - C++ Reference
によると、この関数は最初の要素を取り除き、それを破棄し、それを指しているポインタ(など)を無効にします。
CTR51-CPP. Use valid references, pointers, and iterators to reference elements of a container - CERT C++ Coding Standard - CERT Secure Coding Standards
によると、無効になったポインタを使用すると未定義動作になることがあります。

これはgccとcl.exeが違うのは明らかですが
これはgccとcl.exeで参照のポインタの扱いが違うということでいいんでしょうか？

未定義動作なので、コンパイラ間で挙動が違うことを含め何が起こってもおかしくありません。
余計なことは考えず、未定義動作を起こさないようにしましょう。
この具体例で何が起こっているかがどうしても気になるなら、アセンブリコードを読んで解析してもいいかもしれません。

[教えてboy]

コード:

Path *deq(void){
    Path *p=&buff.front();
    buff.pop();
    return p;
}

ではつまり
参照がどうのこうのではなく
buff.pop()で無効になる対象のポインタを返してしまっていたので
無効になった後のポインタのアクセスがうまくいかなかったのですね。

コードを直してみました。

コード:

#include<iostream>
#include<queue>
using namespace std;

enum { S = 0, A, B, C, D, E, F, G };

#define N 7
#define M 4

// 隣接リスト
int adjacent[N + 1][M] = {
	{ S },
	{ B, C, S },
	{ A, C, D, S },
	{ A, B, E, S },
	{ B, E, F, S },
	{ C, D, G, S },
	{ D, S },
	{ E, S },
};

// 経路
typedef struct {
	int path[N];
	int len;
} Path;

// 現在地点を求める
int top(const Path  &p)
{
	return p.path[p.len - 1];
}

// 経路に頂点が含まれているか
bool visited(const Path &p, int x)
{
	for (int i = 0; i < p.len; i++) {
		if (p.path[i] == x) return true;
	}
	return false;
}

// 経路の表示
void print_path(const Path &p)
{
	for (int i = 0; i < p.len; i++) {
		cout << (char)('A' + p.path[i] - 1);
	}
	cout << endl;
}

queue<Path>buff;

//初期化
void init_queue(int start) {
	Path p;
	buff.push(p);
	buff.front().path[0] = start;
	buff.front().len = 1;
}

//データの取り出し
Path deq(void) {
	Path deq = buff.front();
	buff.pop();
	return deq;
}

//データの追加
void enq(Path &p,int x) {
	buff.push(p);
	buff.back().path[p.len] = x;
	buff.back().len++;
}

// 幅優先探索
void bfs(int start, int goal)
{
	init_queue(start);
	while (!buff.empty()) {
		Path  p = deq();
		int x = top(p);
		if (x == goal) {
			print_path(p);
		}
		else {
			for (int i = 0; i < M; i++) {
				int y = adjacent[x][i];
				if (y == 0) break;
				if (!visited(p, y)) enq(p, y);
			}
		}
	}
}

int main() {
	bfs(A, G);
	return 0;
}

あんどーなつさん、みけCATさんご指摘ありがとうございました。
上記のコードでまずいところがあればご指導よろしくお願いします。

[教えてboy]

さっきテストしてみましたが
未定義動作をなくしたら
buff.push(*p)で渡したものはきちんと独立するようになりました。
未定義動作があると何やら同じものをさすようになってしまうみたいです。
もうすこし実力がついたらみけCATさんの言うように
アセンブリを勉強して動作を調べてみたいと思います。
丁寧な回答ありがとうございました。