C++プログラミング・データ構造の実装

C++プログラミングの基礎・データ構造の実装をご紹介します。
ここで紹介するサンプルコードを使用することで、多次元の配列データを1次元の配列データとして扱うことができます。

1 多次元データと１次元データ
2 用途・どんな時に使えるの？
3 データ構造
4 実装の解説
- 4.1 サンプルコード
5 参考

多次元データと１次元データ

多次元データを1次元データへ変換する方法を説明します。

多次元データとは多次元の配列で定義されたデータのことです。例えばchar num[2][3];のように２次元配列で定義されます。１次元データとは１次元の配列で定義されたデータのことです。例えばchar num[2];のように１次元の配列で定義されます。

多次元配列を１次元配列で表現することは可能であり、またその逆も可能です（私が経験した現場ではこれらの変換処理をシリアライズと呼んでいました）。

用途・どんな時に使えるの？

主に以下の処理を行う際に使用します。

プロセス間通信で共有メモリを用いたデータの送受信

他のプロセスのメモリマップが自プロセスと異なるため、共有メモリを使用する際は多次元データを使うことができません。そのため共有メモリを使用する際に多次元データを１次元データへ変換する必要があります。

データ構造

例えば以下のような世界陸上のデータ構造があります。これは多次元配列で定義することができます。

「世界陸上」に対して「種目」は複数の関係であり、「種目」は「種目名」と「参加者」をもっています。「種目」に対して「参加者」は０かそれ以上の関係であり、「参加者」は「名前」と「参加記録」をもっています。

この多次元データを１次元データにで表すと以下のようになります。

分かりやすくするため「型」「バイト」「データ」の順に示しています。

データのはじめに「種目」の数を示すデータを割り当てます。このデータのサイズはintなので4です。次に「種目名」のデータを割り当てます。「種目名」はstringであるためサイズを可変とします。

「参加者」は複数存在することになるため、「参加者」の数を示すデータを割り当てます。サイズはintなので4です。「参加者」が持つ「名前」「参加記録」のデータを割り当てます。両者ともにstringなのでサイズは可変です。その後は同じように「種目」の数と「参加者」の数だけ割り当てていきます。

「データサイズ　＋　データ」という構成で一次元配列へ割り当てていきます。なお可変長のstringについてはサイズ指定しておりません。
これはNULL終端を保証することで、NULL終端までをstringのデータであることを示すことができるためです。

このような構成でデータを割り当てることで多次元データを１次元データで表現することができます。

実装の解説

C++で実装したサンプルコードを解説します。
このサンプルコードは世界陸上へ参加する100m選手とマラソン選手のデータを多次元配列へ格納し、多次元配列を１次元配列へ変換した後に多次元配列と１次元配列の中身を表示します。

多次元配列は構造体で定義されている「種目」をlistで定義します。また「種目」で定義している「参加者」もlistで定義しています。

display_multidimensionall_array関数で種目毎に格納した参加選手のデータをイテレータを使って表示します。

convert_multi_to_one_dim関数で多次元配列から１次元配列へ変換します。
変換する前にget_max_data_size関数で多次元配列のデータサイズを計算します。可変長のstringがあるためNULL終端を考慮して+1のサイズで計算します。計算した最大サイズ分の１次元配列のデータを確保します。

convert_multi_to_one_dim関数では「種目の個数」「種目名」「参加者の個数」「名前」「参加記録」を１次元配列へ格納します。データを格納する毎に、格納したデータのサイズをoffsetへ加算し、次のデータの格納先を指定します。

display_one_dimensional_array関数で１次元配列の中身を表示します。
１次元配列の先頭の４バイトは「種目の個数」なので、取り出した「種目の個数」だけfor文を使って残りのデータを取り出します。次のデータは「種目名」のため athletes_type_name = &binary_data[offset]; でstringのデータを取り出します。

なおNULL終端を保証しているため、サイズ指定をしなくてもデータがNULLまでコピーしてくれます。注意としてoffsetにサイズを加算する際は、NULL終端分を足して加算します(+1)。

あとは同じように「参加者の個数」を取り出し、for文で「名前」「参加記録」を取り出すだけです。

■ ExDataStructure.cpp

// ExDataStructure.cpp : コンソール アプリケーションのエントリ ポイントを定義します。
//

#include "stdafx.h"
#include "logout.h"
#include "define_common.h"
using namespace hukusuke;

/* 100mの情報を登録 */
void regist_athletes_sprint(list<TR_EVENTS>& list_events) {

	// ■ 選手設定.
	TR_ATHLETES ath_bolt;
	ath_bolt.name = "Usain Bolt";
	ath_bolt.record = "9.58";

	TR_ATHLETES ath_gatlin;
	ath_gatlin.name = "Justin Gatlin";
	ath_gatlin.record = "9.74";

	TR_ATHLETES ath_sani;
	ath_sani.name = "Sani Brown";
	ath_sani.record = "10.05";

	// ■ 種目名と参加者を登録
	TR_EVENTS events;
	events.name = "100m";
	events.list_athletes.push_back(ath_bolt);
	events.list_athletes.push_back(ath_gatlin);
	events.list_athletes.push_back(ath_sani);

	// ■ 種目へ登録
	list_events.push_back(events);

	return;
}

/* マラソンの情報を登録 */
void regist_athletes_marathon(list<TR_EVENTS>& list_events) {

	// ■ 選手設定.
	TR_ATHLETES ath_kipruto;
	ath_kipruto.name = "Kipruto";
	ath_kipruto.record = "2:02:57";

	TR_ATHLETES ath_kawauchi;
	ath_kawauchi.name = "Kawauchi";
	ath_kawauchi.record = "2:08:14";

	TR_ATHLETES ath_takaoka;
	ath_takaoka.name = "Takaoka";
	ath_takaoka.record = "2:06:16";

	// ■ 種目名と参加者を登録
	TR_EVENTS events;
	events.name = "42.195km";
	events.list_athletes.push_back(ath_kipruto);
	events.list_athletes.push_back(ath_kawauchi);
	events.list_athletes.push_back(ath_takaoka);

	// ■ 種目へ登録
	list_events.push_back(events);

	return;
}

/* データ最大サイズの算出 */
int get_max_data_size( list<TR_EVENTS> list_events) {

	int max_size = 0;
	max_size += sizeof(list_events.size());	// 種目数のサイズを加算.
	for (list<TR_EVENTS>::iterator iter_events = list_events.begin(); iter_events != list_events.end(); ++iter_events) 
	{
		max_size += strlen(iter_events->name.c_str()) + 1;		// 種目名のサイズを加算(NULL終端含む).
		max_size += sizeof(iter_events->list_athletes.size());	// 参加者数のサイズを加算.
		
		for (list<TR_ATHLETES>::iterator iter_athletes = iter_events->list_athletes.begin(); iter_athletes != iter_events->list_athletes.end(); ++iter_athletes) 
		{
			max_size += strlen(iter_athletes->name.c_str()) + 1;	// 参加者の名前のサイズを加算(NULL終端含む).
			max_size += strlen(iter_athletes->record.c_str()) + 1;	// 記録のサイズを加算(NULL終端含む).
		}
	}
	return max_size;
}

/* 多次元配列を1次元配列へ変換 */
void convert_multi_to_one_dim(list<TR_EVENTS> list_events, char* binary_data ) {

	int offset = 0;
	int tr_events_size = list_events.size();
	
	// ■ 種目数を設定.
	memcpy( &binary_data[offset], &tr_events_size, sizeof(tr_events_size)); offset += sizeof(tr_events_size);
	
	for (list<TR_EVENTS>::iterator iter_events = list_events.begin(); iter_events != list_events.end(); ++iter_events) 
	{	
		// ■ 種目名を設定.
		memcpy(&binary_data[offset], &iter_events->name[0], strlen(iter_events->name.c_str()) + 1); 
		offset += strlen(iter_events->name.c_str()) + 1;
		
		// ■ 参加者数を設定.
		int tr_athletes_size = iter_events->list_athletes.size();
		memcpy(&binary_data[offset], &tr_athletes_size, sizeof(tr_athletes_size)); offset += sizeof(tr_athletes_size);

		for (list<TR_ATHLETES>::iterator iter_athletes = iter_events->list_athletes.begin(); iter_athletes != iter_events->list_athletes.end(); ++iter_athletes) 
		{
			// ■ 参加者の名前を設定.
			memcpy(&binary_data[offset], &iter_athletes->name[0], strlen(iter_athletes->name.c_str()) + 1);
			offset += strlen(iter_athletes->name.c_str()) + 1;

			// ■ 参加者の記録を設定.
			memcpy(&binary_data[offset], &iter_athletes->record[0], strlen(iter_athletes->record.c_str()) + 1);
			offset += strlen(iter_athletes->record.c_str()) + 1;
		}
	}
}

/* 一次元配列の表示 */
void display_one_dimensional_array(char* binary_data) {

	int offset = 0;
	int tr_events_size = 0;
	
	memcpy( &tr_events_size, &binary_data[offset], sizeof(tr_events_size));
	offset += sizeof(tr_events_size);

	for (int i = 0; i < tr_events_size; ++i) 
	{
		// ■ 種目名を表示.
		string athletes_type_name;
		athletes_type_name = &binary_data[offset];	// NULL終端までコピーされる.
		offset += strlen(athletes_type_name.c_str()) + 1;
		LOG_OUTPUT(" [%s]", athletes_type_name.c_str());

		int tr_athletes_size =0;
		memcpy(&tr_athletes_size, &binary_data[offset], sizeof(tr_athletes_size));
		offset += sizeof(tr_athletes_size);
		for (int j = 0; j < tr_athletes_size; ++j)
		{
			// ■ 参加者名と参加記録を表示.
			string athletes_name;
			athletes_name = &binary_data[offset];	// NULL終端までコピーされる.
			offset += strlen(athletes_name.c_str()) + 1;

			string athletes_record;
			athletes_record = &binary_data[offset];	// NULL終端までコピーされる.
			offset += strlen(athletes_record.c_str()) + 1;

			LOG_OUTPUT(" + name: %16s, record: %8s", athletes_name.c_str(), athletes_record.c_str());
		}
	}
	return;
}

/* 多次元配列を表示. */
void display_multidimensionall_array(list<TR_EVENTS> list_events) {

	for (list<TR_EVENTS>::iterator iter_events = list_events.begin(); iter_events != list_events.end(); ++iter_events)
	{
		// ■ 種目名を表示.
		LOG_OUTPUT(" [%s]", iter_events->name.c_str());

		for (list<TR_ATHLETES>::iterator iter_athletes = iter_events->list_athletes.begin(); iter_athletes != iter_events->list_athletes.end(); ++iter_athletes)
		{
			// ■ 参加者名と参加記録を表示.
			LOG_OUTPUT(" + name: %16s, record: %8s", iter_athletes->name.c_str(), iter_athletes->record.c_str());
		}
	}
	return;
}

/* Main関数 */
int main(void)
{
	LOG_OUTPUT("Start.");
	list<TR_EVENTS>	list_events;			// 世界陸上の種目リスト.
	list_events.clear();

	regist_athletes_sprint(list_events);	// 100mの情報を登録
	regist_athletes_marathon(list_events);  // マラソンの情報を登録

	// ■ 多次元配列を表示.
	LOG_OUTPUT("+------Multidimensional array-----+");
	display_multidimensionall_array(list_events);
	LOG_OUTPUT("+---------------------------------+");

	// ■ 多次元配列を1次元配列へ変換.
	char* binary_data;
	int max_data;
	max_data = get_max_data_size(list_events);	// 多次元配列の最大数を取得.
	
	binary_data = new char[max_data];
	memset(binary_data, 0, max_data);

	convert_multi_to_one_dim(list_events, binary_data);	// 変換.

	// ■ 1次元配列を表示.
	LOG_OUTPUT("+------One-dimensional array------+");
	display_one_dimensional_array(binary_data);
	LOG_OUTPUT("+---------------------------------+");

	// ■ 後処理.
	if (NULL != binary_data) { delete binary_data; binary_data = NULL; }

	LOG_OUTPUT("Terminate.");
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

// ExDataStructure.cpp : コンソールアプリケーションのエントリポイントを定義します。

#include "stdafx.h"

#include "logout.h"

#include "define_common.h"

using namespace hukusuke;

/* 100mの情報を登録 */

void regist_athletes_sprint(list<TR_EVENTS>& list_events) {

// ■ 選手設定.

TR_ATHLETES ath_bolt;

ath_bolt.name = "Usain Bolt";

ath_bolt.record = "9.58";

TR_ATHLETES ath_gatlin;

ath_gatlin.name = "Justin Gatlin";

ath_gatlin.record = "9.74";

TR_ATHLETES ath_sani;

ath_sani.name = "Sani Brown";

ath_sani.record = "10.05";

// ■ 種目名と参加者を登録

TR_EVENTS events;

events.name = "100m";

events.list_athletes.push_back(ath_bolt);

events.list_athletes.push_back(ath_gatlin);

events.list_athletes.push_back(ath_sani);

// ■ 種目へ登録

list_events.push_back(events);

return;

}

/* マラソンの情報を登録 */

void regist_athletes_marathon(list<TR_EVENTS>& list_events) {

// ■ 選手設定.

TR_ATHLETES ath_kipruto;

ath_kipruto.name = "Kipruto";

ath_kipruto.record = "2:02:57";

TR_ATHLETES ath_kawauchi;

ath_kawauchi.name = "Kawauchi";

ath_kawauchi.record = "2:08:14";

TR_ATHLETES ath_takaoka;

ath_takaoka.name = "Takaoka";

ath_takaoka.record = "2:06:16";

// ■ 種目名と参加者を登録

TR_EVENTS events;

events.name = "42.195km";

events.list_athletes.push_back(ath_kipruto);

events.list_athletes.push_back(ath_kawauchi);

events.list_athletes.push_back(ath_takaoka);

// ■ 種目へ登録

list_events.push_back(events);

return;

}

/* データ最大サイズの算出 */

int get_max_data_size( list<TR_EVENTS> list_events) {

int max_size = 0;

max_size += sizeof(list_events.size()); // 種目数のサイズを加算.

for (list<TR_EVENTS>::iterator iter_events = list_events.begin(); iter_events != list_events.end(); ++iter_events)

{

max_size += strlen(iter_events->name.c_str()) + 1; // 種目名のサイズを加算(NULL終端含む).

max_size += sizeof(iter_events->list_athletes.size()); // 参加者数のサイズを加算.

for (list<TR_ATHLETES>::iterator iter_athletes = iter_events->list_athletes.begin(); iter_athletes != iter_events->list_athletes.end(); ++iter_athletes)

{

max_size += strlen(iter_athletes->name.c_str()) + 1; // 参加者の名前のサイズを加算(NULL終端含む).

max_size += strlen(iter_athletes->record.c_str()) + 1; // 記録のサイズを加算(NULL終端含む).

}

return max_size;

}

/* 多次元配列を1次元配列へ変換 */

void convert_multi_to_one_dim(list<TR_EVENTS> list_events, char* binary_data ) {

int offset = 0;

int tr_events_size = list_events.size();

// ■ 種目数を設定.

memcpy( &binary_data[offset], &tr_events_size, sizeof(tr_events_size)); offset += sizeof(tr_events_size);

for (list<TR_EVENTS>::iterator iter_events = list_events.begin(); iter_events != list_events.end(); ++iter_events)

{

// ■ 種目名を設定.

memcpy(&binary_data[offset], &iter_events->name[0], strlen(iter_events->name.c_str()) + 1);

offset += strlen(iter_events->name.c_str()) + 1;

// ■ 参加者数を設定.

int tr_athletes_size = iter_events->list_athletes.size();

memcpy(&binary_data[offset], &tr_athletes_size, sizeof(tr_athletes_size)); offset += sizeof(tr_athletes_size);

for (list<TR_ATHLETES>::iterator iter_athletes = iter_events->list_athletes.begin(); iter_athletes != iter_events->list_athletes.end(); ++iter_athletes)

{

// ■ 参加者の名前を設定.

memcpy(&binary_data[offset], &iter_athletes->name[0], strlen(iter_athletes->name.c_str()) + 1);

offset += strlen(iter_athletes->name.c_str()) + 1;

// ■ 参加者の記録を設定.

memcpy(&binary_data[offset], &iter_athletes->record[0], strlen(iter_athletes->record.c_str()) + 1);

offset += strlen(iter_athletes->record.c_str()) + 1;

}

/* 一次元配列の表示 */

void display_one_dimensional_array(char* binary_data) {

int offset = 0;

int tr_events_size = 0;

memcpy( &tr_events_size, &binary_data[offset], sizeof(tr_events_size));

offset += sizeof(tr_events_size);

for (int i = 0; i < tr_events_size; ++i)

{

// ■ 種目名を表示.

string athletes_type_name;

athletes_type_name = &binary_data[offset]; // NULL終端までコピーされる.

offset += strlen(athletes_type_name.c_str()) + 1;

LOG_OUTPUT(" [%s]", athletes_type_name.c_str());

int tr_athletes_size =0;

memcpy(&tr_athletes_size, &binary_data[offset], sizeof(tr_athletes_size));

offset += sizeof(tr_athletes_size);

for (int j = 0; j < tr_athletes_size; ++j)

{

// ■ 参加者名と参加記録を表示.

string athletes_name;

athletes_name = &binary_data[offset]; // NULL終端までコピーされる.

offset += strlen(athletes_name.c_str()) + 1;

string athletes_record;

athletes_record = &binary_data[offset]; // NULL終端までコピーされる.

offset += strlen(athletes_record.c_str()) + 1;

LOG_OUTPUT(" + name: %16s, record: %8s", athletes_name.c_str(), athletes_record.c_str());

}

return;

}

/* 多次元配列を表示. */

void display_multidimensionall_array(list<TR_EVENTS> list_events) {

for (list<TR_EVENTS>::iterator iter_events = list_events.begin(); iter_events != list_events.end(); ++iter_events)

{

// ■ 種目名を表示.

LOG_OUTPUT(" [%s]", iter_events->name.c_str());

for (list<TR_ATHLETES>::iterator iter_athletes = iter_events->list_athletes.begin(); iter_athletes != iter_events->list_athletes.end(); ++iter_athletes)

{

// ■ 参加者名と参加記録を表示.

LOG_OUTPUT(" + name: %16s, record: %8s", iter_athletes->name.c_str(), iter_athletes->record.c_str());

}

return;

}

/* Main関数 */

int main(void)

{

LOG_OUTPUT("Start.");

list<TR_EVENTS> list_events; // 世界陸上の種目リスト.

list_events.clear();

regist_athletes_sprint(list_events); // 100mの情報を登録

regist_athletes_marathon(list_events); // マラソンの情報を登録

// ■ 多次元配列を表示.

LOG_OUTPUT("+------Multidimensional array-----+");

display_multidimensionall_array(list_events);

LOG_OUTPUT("+---------------------------------+");

// ■ 多次元配列を1次元配列へ変換.

char* binary_data;

int max_data;

max_data = get_max_data_size(list_events); // 多次元配列の最大数を取得.

binary_data = new char[max_data];

memset(binary_data, 0, max_data);

convert_multi_to_one_dim(list_events, binary_data); // 変換.

// ■ 1次元配列を表示.

LOG_OUTPUT("+------One-dimensional array------+");

display_one_dimensional_array(binary_data);

LOG_OUTPUT("+---------------------------------+");

// ■ 後処理.

if (NULL != binary_data) { delete binary_data; binary_data = NULL; }

LOG_OUTPUT("Terminate.");

return 0;

}

■ define_common.h

#pragma once
#include <string>
#include <list>
using namespace std;

/* 参加者 */
struct TR_ATHLETES{
	string name;	// 参加名
	string record;	// 参加記録
};

/* 種目 */
struct TR_EVENTS {
	string name;						// 種目名
	list<TR_ATHLETES> list_athletes;	// 参加者のリスト.
};

#pragma once

#include <string>

#include <list>

using namespace std;

/* 参加者 */

struct TR_ATHLETES{

string name; // 参加名

string record; // 参加記録

};

/* 種目 */

struct TR_EVENTS {

string name; // 種目名

list<TR_ATHLETES> list_athletes; // 参加者のリスト.

};

サンプルコード

Visual C++ 2017で作成したサンプルコードをGitHubで公開しています。
GitHub – ExDataStructure

実行結果は以下の通りです。
多次元配列の中身と１次元配列の中身が同じであるため、正しく変換できていることが確認できます。

[170] Start.
[178] +------Multidimensional array-----+
[160]  [100m]
[162]  + name:       Usain Bolt, record:     9.58
[162]  + name:    Justin Gatlin, record:     9.74
[162]  + name:       Sani Brown, record:    10.05
[160]  [42.195km]
[162]  + name:          Kipruto, record:  2:02:57
[162]  + name:         Kawauchi, record:  2:08:14
[162]  + name:          Takaoka, record:  2:06:16
[180] +---------------------------------+
[191] +------One-dimensional array------+
[133]  [100m]
[149]  + name:       Usain Bolt, record:     9.58
[149]  + name:    Justin Gatlin, record:     9.74
[149]  + name:       Sani Brown, record:    10.05
[133]  [42.195km]
[149]  + name:          Kipruto, record:  2:02:57
[149]  + name:         Kawauchi, record:  2:08:14
[149]  + name:          Takaoka, record:  2:06:16
[193] +---------------------------------+
[198] Terminate.