[C++] 자료구조 :: STL Array & STL Vector

chooha·2024년 12월 27일

자료구조

목록 보기
1/2

< 배열 >

▸ 정의

: 메모리 상에 원소를 연속으로 배치한 자료구조

▸ 성질

  • O(1)에 k번째 원소를 확인/변경 가능

  • 다른 자료구조와 다르게 추가적으로 소모되는 메모리의 양(overhead)이 거의 없음

  • Cache hit rate가 높음
    : 메모리 상에 데이터들이 붙어있기 때문

  • 메모리 상에 연속한 구간을 잡아야해서 할당에 제약이 걸림

▸ 기능

  • 임의의 위치에 원소 추가/제거 = O(n)
    : 추가한 위치의 뒤쪽 원소들이 한 칸씩 밀려야하기 때문에
    제거 또한 제거한 위치의 뒤쪽 원소들이 한 칸씩 앞으로 당겨져야 하기 때문에 동일

  • 임의의 위치에 있는 원소 확인/변경 = O(1)

  • 원소를 끝에 추가 = O(1)

  • 마지막 원소 제거 = O(1)

1. STL Array

▸ 정의

: 고정된 크기의 배열을 담고 있는 컨테이너

▸ 변수 선언

#include <array>

std::array<int, 3> myArray;

array의 길이는 고정 배열 선언처럼 컴파일 타임에 설정해야 함

▸ 초기화

std::array<int, 5> myArray = {9, 7, 3, 5, 1}; // initialization list
std::array<int, 5> myArray2 {9, 7, 5, 3, 1};  // uniform initialization
std::array<int, 5> myArray;
myArray = { 0, 1, 2, 3, 4 };
myArray = { 9, 8, 7 }; // elements 3 and 4 are set to zero!

▸ 원소 접근

myArray[2] = 6;

myArray.at(1) = 6;  // array element 1 valid, sets array element 1 to value 6
myArray.at(9) = 10; // array element 9 is invalid, will throw error(std::out_of_range)

일반 배열처럼 첨자 연산자를 사용해서 배열의 원소에 접근할 수 있지만, 유효 범위 검사를 하지 않으므로 잘못된 index가 제공되면 stack overflow 발생
→ at()함수를 사용하면 이를 방지할 수 있음 (첨자 연산자보다는 느리지만, 안전)

▸ 멤버 함수

  • fill()

    	std::array<int, 5> arr;
	arr.fill(3);  // arr 은 {3,3,3,3,3}

    배열의 원소들을 인자로 전달된 값으로 채움

  • empty()
    크기가 0인지 아닌지 확인

  • size()

    int len = myArray.size();

    array는 함수에 전달될 때 포인터로 형 변환되지 않기 때문에 size()함수는 함수 내에서 호출되더라도 정상적으로 작동함

    💡 std::array는 항상 참조로 전달
    : 함수로 전달될 때(성능상의 이유로) 컴파일러가 배열의 복사본을 만드는 것을 방지하기 위함

    💡 size() & sizeof()
    : 표준 라이브러리에서는 "size"라는 용어는 배열의 길이를 의미하므로 sizeof() 연산자의 결과와 혼동하면 안됨
    → sizeof() 결과는 배열 요소 자료형의 크기 * 배열 길이임

  • front(), back()
    각각 첫 번째와 마지막 원소의 참조자를 리턴
    만일, 배열의 크기가 0이라면, 해당 함수를 호출하는 작업은 정의되지 않은 작업임

  • begin(), cbegin()
    시작점을 나타내는 반복자를 리턴
    cbegin()의 경우 상수 반복자를 리턴

  • end(), cend()
    끝을 나타내는 반복자를 리턴
    end()의 경우 맨 마지막 원소 바로 다음을 나타냄

  • rbegin(), crbegin()
    역참조 반복자의 시작점을 리턴
    역참조시에 보통 맨 마지막 원소를 나타냄

  • rend(), crend()
    역참조 반복자의 끝점을 리턴

  • data()
    array 내부 데이터 배열에 대한 포인터를 반환

2. STL Vector

▸ 정의

: 배열과 거의 동일한 기능을 수행하는 자료구조

▸ 생성자

#include <vector>
std::vector<int> vec; // 빈 벡터 생성

std::vector<int> vec1 = {1, 2, 3}; // 초기화 리스트

std::vector<int> vec2(5); // 크기가 5이고 모든 값이 0인 벡터 생성
std::vector<int> vec3(5, 2); // 크기가 5이고 모든 값이 2인 벡터 생성

std::vector<int> vec4(vec1); // 복사 생성자

std::vector<int> vec5(vec1.begin(), vec1.begin()+2); // vec5 = {1, 2} 범위 기반 생성자

▸ 원소 접근

: array와 동일

▸ 멤버 함수

  • push_back()

    	std::vector<int> vec;
	vec.push_back(1); // vec = {1}
	vec.push_back(2); // vec = {1, 2}

    벡터의 끝에 원소 추가

  • pop_back()

    	std::vector<int> vec = {1, 2, 3};
	vec.pop_back(); // vec = {1, 2}

    벡터의 끝에 있는 원소 제거

  • size()
    벡터의 크기 반환

  • empty()
    벡터가 비어있는지 여부를 확인

  • resize()

    	std::vector<int> vec = {1, 2, 3};
	vec.resize(5); // vec = {1, 2, 3, 0, 0}
	vec.resize(2); // vec = {1, 2}

    벡터의 크기를 변경

  • insert()

    	std::vector<int> vec = {1, 2, 3};
	vec.insert(vec.begin() + 1, 4); // vec = {1, 4, 2, 3}

    벡터의 특정 위치에 원소 삽입

  • erase()

    	std::vector<int> vec = {1, 2, 3};
	vec.erase(vec.begin() + 1); // vec = {1, 3}
	vec.erase(vec.begin() + 1, vec.end()); // vec = {1}

    벡터의 특정 위치에 있는 원소를 제거
    ❗ 벡터의 특성 상 시간이 많이 걸리므로 사용하지 않는게 좋음

  • front(), back()
    벡터의 첫 번째, 마지막 원소를 반환

  • begin()
    벡터의 첫번째 원소를 가리키는 iterator를 반환

  • end()
    벡터의 마지막 요소 다음 위치를 가리키는 iterator를 반환
    ex. vec = {1, 2, 3}에서 vec.end()는 실제로 vec의 마지막 원소인 3이 아니라 그 다음 위치를 가리키게 됨

  • clear()
    벡터의 모든 원소를 제거
    벡터의 사이즈는 0이 되지만, 용량(capacity)은 그대로 유지됨

    💡 만약 벡터가 차지하는 메모리를 완전히 해제하고 싶다면
    swap()을 사용하여 빈 벡터와 swap하면 됨
    이렇게 하면 기존 벡터가 차지했던 메모리는 모두 해제됨 

    	vector<int> vec {1, 2, 3};
	vec.clear(); // size = 0, capacity = 3
	vector<int>().swap(vec); // vec의 메모리를 해제하고, 빈 벡터와 swap
	// vec는 더 이상 메모리를 차지하지 않음

  • data()

    	std::vector<int> vec = {1, 2, 3};
	int* ptr = vec.data();

	std::cout << ptr[0] << std::endl; // 1 출력

    벡터의 내부 데이터 배열에 대한 포인터를 반환
    벡터의 첫번째 원소를 가리키는 포인터를 제공하여 c스타일의 접근이 가능하게 해줌
    벡터에 저장된 원소의 타입에 따라서 T* 포인터 타입이 반환됨

  • emplace_back()

    	struct MyStruct
	{
    	MyStruct(int x, double y) : x(x), y(y) {}
    	int x;
    	double y;
	};

	std::vector<MyStruct> myVec;
	myVec.emplace_back(1, 3.14); // 결과는 myVec.push_back(MyStruct(1, 3.14));와 같음

    벡터의 끝에 원소를 추가하는 함수

    💡 push_back() & emplace_back()
    : push_back()은 원소를 추가하기 위해 임시 객체를 만들어 생성, 이동, 소멸하는 과정이라면
    emplace_back()은 객체 생성에 필요한 인자를 받아서 함수 내에서 객체를 직접 "in-place"로 생성하므로 별도의 객체 복사나 이동이 필요없게 해줌
    ❗특히 생성 비용이 큰 객체들을 벡터에 추가할 때 성능 향상을 가져올 수 있지만, 암시적 형변환으로 인한 예상치 못한 문제가 발생할 수 있으므로 주의해서 사용해야 함

▸ Vector에서 특정 값 찾기

  • find() 
    	find(start_iterator, end_iterator, value_to_find)
    <algorithm> 헤더에 정의된 std::find()함수는 시퀀셜 컨테이너(배열, 벡터, 리스트 등)의 시작과 끝 iterator를 인자로 받아, 지정된 값과 같은 첫번째 원소를 찾는 함수
    - 해당 값이 컨테이너에 존재하지 않는다면 끝 iterator를 반환
    - 해당 값을 찾은 경우, 해당 iterator를 사용해 원소에 직접 접근하거나 시작 iterator를 빼서 해당 값이 위치한 index를 알 수 있음
< 참고 자료 >

실전 알고리즘
모두의 코드 std::array
소년코딩 std::array
vector 사용법

profile
chooha
다음 포스트

[C++] 자료구조 :: STL Map & STL Set

0개의 댓글