2.2 - (3) Data Structure

1. Array

• Format : T A[N]

  • T : Data Type
  • N : Length

• Array size : Sizeof(T) x N Bytes

• Contiguously allocated region

• Does not do bound checking
  

• Two-Dimensional Nested Array

  

  • Format : T A[R][C]
  • All levels in one contiguous block
  • Row-Major ordering
  • Elements are contiguous
  • Array size : R x C x Sizeof(T) Bytes
  • How to calculate address
    -> A[i][j] : A + (i x C x K) + (j x K), where K is required bytes

• Multi-Level Array

  

  • Format : T *A[N], where T is data type, N is length
  • First level in one contiguous block
    -> Each element in first level points another subarray
    -> Address of each level array is not contiguous
  • Each element is a pointer (8 bytes)

• Nested array VS Multi-level array

  Nested Array	Multi-level Array
  needs consecutive memory space	only needs the size of memory that pointer points
  access once to get a value	access twice to get a value

---

2. Struct

• 정의 : 서로 다른 종류의 자료형을 하나의 이름으로 묶어서 사용할 수 있는 변수
• Typedef를 통해 재정의가 가능하다.
• "." operator를 통해 접근이 가능하다.
  
  
  
• 구조체 배열의 멤버도 직접접근이 가능하다.
  
  
  
• 포인터로 연결되어있을 경우 "." Operator OR Arrow Operator를 사용하여 접근이 가능하다.
  
  
  
• 구조체 내의 멤버들은 연속된 영역안에서 할당되게 된다.
  
  -> Fields ordered according to declaration order even if another ordering would be more compact!

• 구조체 정의는 main() 함수 밖과 안에서 모두 선언할 수 있지만 main() 함수 안에서 정의하면 main() 함수 밖에서는 구조체를 사용할 수 없다.

  • 변수이므로 스택영역에 할당된다.
    따라서, 메인 함수가 return되게 된다면 사라지게 된다.
    

---

3. Memory Alignment

• Must have an address that is a multiple of k

• Memory Alignment를 통해 Memory access 횟수를 줄일 수 있다.
  -> Each structure has alignment requirement Kmax, where Kmax is the largest alignment of any element.
  

• Unaligned Data

  

• After alignment
  
  -> 3 bytes, 4 bytes are padding data.
  -> 낭비되는 memory를 최소화 하기 위해 Padding data 또한 최소화하는 것이 목적!
  
  

• 선언 순서를 바꿈으로써 memory 효율성을 증가시킬 수 있다.
  

• Example