std :: vector dimension, "tetris"도형을 사용할 수 있습니까?

Question

안녕하세요, 나는 C에서 벡터의 사용에 대한 질문이 + +, 난 무작위 모션으로 컨테이너를 통해 입자 운동을 시뮬레이션의 문제에 노력하고 있습니다. 입자를 추가하거나 제거해야 할 필요가 있습니다. 특정 기준을 충족시키지 못하거나이 기준을 충족시키지 못했을 때 벡터 클래스를 매우 편리하게 사용할 수있었습니다. 그러나 C++을 처음 접했을 때 고려해야 할 효율성 문제가있었습니다.

정의한 2D 배열이 직사각형 또는 사각형으로 제한됩니까? 각 컨테이너에 입자의 위치 만 저장하면됩니다. 제가 두려워하는 것은 매트릭스가 다음과 같이 보일 것입니다 :

| | | | |

| | | | |

| | | | |

| | | | |

4x4 케이스의 경우. 각 빈/컨테이너의 입자 위치와 빈이 빈과 다른 빈의 수를 입력하면 다음과 같은 것이 가능한지 궁금합니다.

| | | | | 제 1 빈의 4 개의 입자

| | | 제 2 저장소의 2 개의 입자, 점유 된 메모리는 상기보다 2 배 작음

| | | | | | | | | | | | | | | | | 이 세 번째 빈에있는 많은 등등.

또한 행 (행 크기 줄이기)의 요소를 제거하거나 행 (행 크기 증가)의 요소를 추가하거나 또는 알고리즘을 구현하는 방법에 따라 열을 추가해야 할 것입니다. 미리 경고 할 수 있다면 감사하겠습니다. 여러 차원의 벡터를 처리 할 때 일반적인 실수가 있다면 나는

Answer 1

당신은 벡터의 벡터 사용할 수 있습니다 : 프로그래밍 언어에 새로운되고, 하나를 만들 확신으로 : 처음에는 vector<vector<Particle> >

Answer 2

을 때를 "2D 배열 ... 제한된 ... 직사각형 또는 사각형"에 대해 묻습니다. "들쭉날쭉 한"배열 (직사각형이 아니지만 고정 된 "높이 t "이고 행당 변수"너비 "가 있음).

그러나 "tetris" shapes (tetraminos)은 특히 톱니 모양 배열에 적합하지 않습니다. 그것은 내가 실제로 당신이 a sparse array을 원한다고 생각하게 만듭니다. 즉, 파티클의 위치 만 저장하고 비 파티클의 위치는 저장하지 않는 것입니다.

가장 쉬운 방법은 그리드를 건너 뛰고 점유 된 공간/입자의 위치 목록을 직접 유지하는 것입니다.

struct Position 
{ 
    float X; 
    float Y; 
}; 

// ... 

std::vector<Position> particles; // std::list works too... 

그러나 일반 목록은 일부 목적에 매우 효율적이지 않습니다. 예를 들어, 시뮬레이션에서 주어진 볼륨/영역에 얼마나 많은 입자가 있는지 알아 내기 위해 공간적으로 색인 된 액세스가 필요한 경우, 희박한 채우기를 허용하는 a space partitioning data structure을 사용해야합니다.

사람들은 일반적으로 직사각형 그리드를 사용하여 설명하는 방식으로이 작업을 수행 한 다음 격자 표 셀에 포함 된 입자의 각 그리드 위치에 목록을 저장합니다. 그러나 이것은 사용되지 않는 그리드 셀을 "낭비"시킵니다. 희소 한 인구 문제를 해결하지는 못합니다.

공간 인덱싱 및 스파 스 인구 통계를 모두 지원하는 널리 사용되는 데이터 구조는 a quadtree입니다.