配列とvector（動的可変長配列）

c++には、vectorという動的可変長配列がある。C++でも配列を宣言して使うことはできるが、vectorを使うのが一般的だと思っている。

c言語では、動的可変長配列がライブラリにないので、配列を使うことになるが、配列を宣言する時点で配列の次元を指定してメモリ領域を確保するため、十分な大きさの配列を最初に確保しておく必要があり、プログラム実行時の条件によっては、無駄にメモリを使ってしまう。

c++のvector

c++ではvectorがあるので、vectorを使うことが多い。理由は、

• 配列の次数を変数で指定できる。
• プログラム動作中にサイズを可変できる。
• vector宣言時に初期化できる。

などの利点があり、使いやすいから。こんな風に使うことが多い。

#include <bits/stdc++.h>
using namespace std;

int main() {
  int n;
  cin >> n;                     // n (variable) is set from stdin
  vector<int> a(n, 0);          // array a of n elements with 0
}

配列（関数内宣言）

C言語では、C++のvectorがないので、配列を使う。もちろん、C++でも配列は使える。配列は宣言時にその次元（要素数）を指定しないといけない。gccコンパイラの場合は、、この配列の次数を変数で指定することができ、プログラムの中で配列のサイズを決定できる。ただし、配列の次元を変数で指定する場合は、配列要素の初期化ができないため、必要に応じて、配列要素の初期化をしないといけない(配列の次元を定数で宣言する場合は、宣言時に配列の要素を初期化できる)。

#include <stdio.h>

int main() {
  int n;
  scanf("%d", 'n');
  int a[n];                     // declare array a of n elements
  for (int i = 0; i < n; i++) {
    a[i] = 0;                   // if needed, initialize with 0
  }
}

ただし、関数内で宣言する変数は、必要メモリ領域をスタックから確保するため、配列のサイズが大きすぎると領域確保に失敗して、プログラムが終了してしまう。

配列（グローバル宣言）

配列をグローバルで宣言すると、コンパイル時にメモリ領域を確保するので、関数内での配列宣言で領域確保に失敗するような大きなサイズの配列でも宣言することができる。

#include <stdio.h>

int a[1000000] = {0};         // delcare fixed size array a with 0

int main() {
  int n;
  scanf("%d", &n);
}

C言語で動的可変長配列

C言語の場合は、配列を使うと言ったが、malloc, reallocで、動的にメモリ領域を確保、開放するようにして、C++のvectorのように、動的可変長配列を実装することができる。

typedef struct vector {
  int *array;
  int size;
} Vector;

Vector *init_vector(int n) {
  Vector *vec = malloc(sizeof(Vector));
  if (n == 0) {
    vec->array = NULL;
    vec->size = 0;
  } else {
    vec->array = malloc(sizeof(int) * n);
    memset(vec->array, 0, sizeof(int) * n);
    vec->size = n;
  }
  return vec;
}

int get_vector(Vector *vec, int i) {
  if (i >= vec->size) {
    return -1;
  }
  return vec->array[i];
}

int set_vector(Vector *vec, int i, int x) {
  if (i >= vec->size) {
    return -1;
  }
  vec->array[i] = x;
  return 0;
}

以下の実行例では、初期化の時に配列の大きさを確保している。

int main() {
  int n;
  scanf("%d", &n);
  Vector *v = init_vector(n);
}

以下のような、push_back()、erase()関数を実装することによって、配列の大きさを動的に替えることができる。

void push_back(Vector *vec, int x) {
  if (vec->array == NULL) {
    vec->array = malloc(sizeof(int));
  } else {
    vec->array = realloc(vec->array, sizeof(int) * (vec->size + 1));
  }
  vec->array[vec->size] = x;
  vec->size += 1;
  return;
}

void erase_vector(Vector *vec, int i, int n) {
  int sz = vec->size;
  if (i + n > sz) {
    n = sz - i;
  }
  for (int j = i; j + n < sz; j++) {
    vec->array[j] = vec->array[j + n];
  }
  vec->array = realloc(vec->array, sizeof(int) * (sz - n));
  vec->size = sz - n;
  return;
}

速度比較

それぞれの配列に対して、n回（以下の速度計測においては、n=100000000）の処理をするプログラムの実行時間を計測してみる。

int main(int argc, char* argv[]) {
  int n = stoi(argv[1]);        // atoi() in case of C lang
  for (int i = 0; i < n; i++)
    a[i] = i;
  printf("%d\n", a[n-1]);
  for (int i = 0; i < n-1; i++) {
    int tmp = a[i];             //  swap without using library function
    a[i] = a[i+1]:
    a[i+1] = tmp;
  }
  printf("%d\n", a[n-1]);
}

結果はこちら。

※関数内での配列宣言では、n=100000000のメモリ領域確保に失敗した。

	C++ vector	配列（グローバル宣言）	動的可変長配列（実装）
1回目	real 0m1.641s	real 0m0.940s	real 0m1.710s
	user 0m0.015s	user 0m0.015s	user 0m0.031s
	sys 0m0.000s	sys 0m0.046s	sys 0m0.000s
2回目	real 0m1.564s	real 0m0.908s	real 0m01.699s
	user 0m0.015s	user 0m0.000s	user 0m0.015s
	sys 0m0.031s	sys 0m.0.31s	sys 0m0.015s
3回目	real 0m1.585s	real 0m0.889s	real 0m1.715s
	user 0m0.000s	user 0m0.031s	user 0m0.030s
	sys 0m0.015s	sys 0m0.000s	sys 0m0.015s