vector 와 array c++

Vector와 Array의 가장 큰 차이는 연속된 메모리 공간 위치이다.

Vector는 -> Heap에 allocation 되고 runtime에 메모리 공간이 할당된다.

runtime할당은 dynamic allocation(동적 메모리 할당) 된다.

 

Array는  -> Stack에 allocation 되고 Compile 시간에 할당된다.

Compile시간에 할당은 static memory allocation(정적 메모리 할당) 한다.

 

정적 메모리 할당이란 

메모리 할당 방법 중에 하나로, 메모리의 크기가 하드 코딩되어 있기 때문에 프로그램이 실행될 때 이미 해당 메모리의 크기가 결정되는 것이 특징이다.

사용하는 운영체제에 따라 각 데이터형에 약속된 기억공간의 크기가 있고, 지정된 만큼 프로그램을 실행하는 프로세서에 필요한 자원으로 할당시켜준다. 이런 것을 정적 할당이라고 한다. 즉, 프로그램 실행의 시작 부분에서 필요한 만큼 

미리 기억공간을 할당받고 시작하는 것을 의미한다.

• 장점: 해제하지 않음으로 인한 메모리 누수와 같은 문제를 신경 쓰지 않아도 된다. 정적 할당된 메모리는 실행 도중에 해제되지 않고, 프로그램이 종료할 때 알아서 운영 체제가 회수한다.
• 단점: 메모리의 크기가 하드 코딩되어 있어서 나중에 조절할 수 없다. 스택에 할당된 메모리이므로 동적 할당에 비해 할당받을 수 있는 최대 메모리에 제약을 받는다.

동적 메모리 할당

은 컴퓨터 프로그래밍에서 실행 시간 동안 사용할 메모리 공간을 할당하는 것을 말한다. 사용이 끝나면 운영체제가 쓸 수 있도록 반납하고 다음에 요구가 오면 재 할당을 받을 수 있다. 이것은 프로그램이 실행하는 순간 프로그램이 사용할 메모리 크기를 고려하여 메모리의 할당이 이루어지는 정적 메모리 할당과 반대된다.

• 장점: 상황에 따라 원하는 크기만큼의 메모리가 할당되므로 경제적이며, 이미 할당된 메모리라도 언제든지 크기를 조절할 수 있다.
• 단점: 더 이상 사용하지 않을 때 명시적으로 메모리를 해제해 주어야 한다.

Vector와 Array의 공통점

- 둘 다 Sequential Memory이며 Random Access를 지원한다

 

Vector 와 Array 의 사용빈도 있는 알고리즘

-Sorting 

sort ,  stabel_sort , patial_sort , nth_element

-min/max

min_element, max_element, minmax_element

-find

find, binary_search

-reduece

accumalate, reduce

 

 

 

Sort는 헤더 파일로 <algorithm>을 가지며

since c++11부턴 O(N·log(N))의  timecomplexity를 가진다.

 

 

Sort

 O(N·log(N)) 의 TimeComplexity를 가지며

배열을 오름차순으로 숫자를 정리한다.

ex) 1, 2, 3, 4, 5, 6, 7

 

Stable_Sort

sort처럼 오름 차순 정리가 되었다 그러나 Sort와 stable_sort의 다른 점은 

sort처럼 정렬이 되지만 기존에 Hardy와  Ford의 순서처럼 같은 값을 가진 것에 대해서는 순차적으로 출력하게 된다.

TimeComplexity또한 항상 O(N·log(N))으로 같은 sort와 다르게 O(n log(n)2) 를 가지기도 한다.

 

partial_sort

log(n) 보다 작은 (last-first) log (middle-first)  TimeComplexity를 가진다

partial_sort(s.begin(), s.begin() + 3, s.end()); 

가장 작은 원소부터 3가지만 정렬하겠다는 의미가 된다.

nth_element

nth_element 는 특정 값을 기준으로 작은 수는 그 수의 왼쪽으로 큰 수는 기준 값의 오른쪽으로 정렬된다 .

위 코드에서 특정값인 5를 기준으로 1부터 10의 수가 작은수는 왼쪽으로 큰 수는 오른쪽으로 정렬된 것을 볼 수 있다.

 

min_element

Time complexity는  가장 작은 수를 찾아 그 위치를 반환한다

 

max_element

TimeComplexity는 min_element 와 동일하며 min과 다르게 가장 큰 값의 찾아준다.

 

minmax_element

 

최솟값과 최댓값을 모두 찾아야 하는 경우에 min과 max를 모두 사용하면 o(2n)의 TimeComplexity를 가지게 된다.

그래서 o(n)의 TimeComplexity를 유지하면서 min의 값과 max값을 모두 경하는 경우 minmax_element를 사용한다.

find

뜻과 같이 찾는 동작을 수행한다

o(n)의 TimeComplexity를 가짐

찾는 값이 있는 경우

2라는 element위치를 찾은 것을 볼 수 있다.

 

 

 

운영중인 카톡방입니다.

https://open.kakao.com/o/gsMhUFie

C/C++/C# 언리얼/유니티 /질문