C++ vector, array

LeemHyungJun·2022년 9월 23일

cpp

C++ Study

목록 보기

8/12

예시코드)
https://github.com/GbLeem/CPP_Study/tree/main/NoCode
53.cpp ~ 61.cpp

vector Intro

std::vector 특징
- dynamic size array
- sequence container
vector 함수
- size() : element의 갯수 반환
- emplace_back(n) : 맨 뒤에 n 삽입
- pop_back() : 맨 뒤의 element 삭제

#include<iostream>
#include<vector>

int main()
{
	std::vector<int>nums{ 0,1,2,3,4 };
	std::cout << nums.size() << std::endl; //5
	nums.emplace_back(5); //맨 뒤에 숫자 삽입
	nums.pop_back(); //맨 뒤에것 삭제

	//ranged for 방식으로 iterate
	for (const int& num : nums)
	{
		std::cout << num << std::endl; //0 1 2 3 4
	}
}

다른 object들도 vector에 넣을 수 있다.

#include<iostream>
#include<vector>

class Cat
{
public:
	explicit Cat(int age)
		:mAge{age}
	{}
	void speak() const
	{
		std::cout << "Cat " << mAge << std::endl;
	}
private:
	int mAge;
};

int main()
{
	std::vector<Cat>catVec;
	catVec.emplace_back(Cat{ 1 });
	catVec.emplace_back(Cat{ 2 });
	catVec.emplace_back(Cat{ 3 });
	catVec.emplace_back(Cat{ 4 });

	for (const auto& cats : catVec)
	{
		cats.speak();
	}
}

std::vector

vector의 time complexity
- random access : O(1)
- insert removal at the end : O(1)
- insert removal linear in distance : O(n)
vector의 구조
- nums는 vector array의 첫번째 공간을 가리키고 있고 vector의 사이즈를 알고 있다.
  -> 많은 경우 아니라면 emplace_back()과 pop_back()은 O(1)의 시간 복잡도를 가진다.
- 맨 앞에 새로운 element를 삽입하거나 삭제할 때 vector의 모든 원소를 뒤로 한칸씩 밀어주는 작업이 필요하므로 O(n)의 시간 복잡도를 가진다.
  -> O(n)의 시간 복잡도를 나타내는 경우는 좋은 경우가 아니므로 생각해보고 사용하는 것이 좋다.

#include<iostream>
#include<vector>

int main()
{
	std::vector<int>nums(10000, 1); //1을 10000개 넣음 
	nums.emplace_back(2); //O(1)
	nums.pop_back(); //O(1)

	nums.emplace(nums.begin(), 3); //O(n)
	nums.erase(nums.begin()); //O(n)
    
    return 0;
}

emplace_back() 최적화 사용하기
- cats.emplace_back(Cat{ "kitty",2 }); 처럼 사용하면 temp 객체가 생성되고 move operation이 한 번 작동한다. (필요없는 move operation)
  -> 아래 그림 참고
- cats.emplace_back("kitty",2); 를 사용할 경우 temp 객체가 생성되지 않고 바로 삽입한다.
  -> emplace_back()은 object의 refenece를 반환한다.(C++17)
  Cat& cat= cats.emplace_back("kitty", 2);

#include<iostream>
#include<string>
#include<vector>

class Cat
{
public:
	explicit Cat(std::string name, int age)
		:mName{ name }
		, mAge{ age }
	{}
	void speak() const
	{
		std::cout << "Cat " << mName << mAge << std::endl;
	}
private:
	std::string mName;
	int mAge;
};

int main()
{
	std::vector<Cat>cats;
	cats.emplace_back(Cat{ "cat0",0 });
	cats.emplace_back(Cat{ "cat1",1 });
    
	//cats.emplace_back(Cat{ "kitty",2 }); bad
    cats.emplace_back("kitty", 2); //better
    
    //참고
    Cat nabi{"nabi", 3};
    cats.emplace_back(nabi);// copy
	cats.emplace_back(std::move(nabi));// move
    
    return 0;
}

vector memory

emplack_back(), push(), pop()의 경우 앞에서 O(1)의 시간 복잡도라고 했지만, 100% 보장되는 것은 아니다.
-> 가끔보다 자주 O(n)이 된다..
vector의 size
-> 아무것도 없는 vector의 크기는 24 byte이다.
- heap 위에 있는 array의 시작을 가리키는 포인터(8byte)
- size : 현재 벡터에 들어있는 element의 갯수를 나타내는 변수(8byte)
- capacity : 벡터가 확보한 메모리의 크기를 나타내는 변수(8byte)
vector의 capacity
- 벡터가 확보한 크기 안에 삽입을 할 때에는 O(1)의 시간 복잡도가 나오지만, 확보된 크기보다 더 크기가 큰 데이터를 삽입하려면 O(n)의 시간 복잡도가 된다.
- 공간이 모자르면 새로 삽입할 데이터의 크기까지 생각해서 메모리 공간을 새로 만들고, 이전에 있던 데이터들을 모두 move한 후 새롭게 삽입 해야하기 때문이다.
- 해결 방법으로는 미리 reserve() 함수로 공간을 확보해두면 문제가 발생하지 않는다.

std::cout << nums.size() << std::endl; //0
nums.reserve(10000);
std::cout << nums.capacity() << std::endl; //10000

vector의 capacity 문제가 발생하는 예시

#include<iostream>
#include<vector>
#include<string>

class Cat
{
public:
	explicit Cat(std::string name)
		:mName{ std::move(name) }
	{
		std::cout << mName << " cat constructor" << std::endl;
	}
	~Cat()
	{
		std::cout << "cat destructor" << std::endl;
	}
	Cat(const Cat& other)
		:mName(other.mName)
	{
		std::cout << mName << " copy constructor" << std::endl;
	}
	Cat(Cat&& other)
		:mName(other.mName)
	{
		std::cout << mName << " move constructor" << std::endl;
	}
private:
	std::string mName;
};

int main()
{
	std::vector<Cat>cats;
	cats.emplace_back("kitty");
	cats.emplace_back("nabi");
	return 0;
	
	//<출력>
	//kitty cat constructor
	//nabi cat constructor
	//kitty copy constructor
	//cat destructor
	//cat destructor
	//cat destructor
}

위의 코드의 동작 모습
위의 코드를 개선하는 방법
1) move constructor를 noexcept로 만들면 copy constructor 대신 move constructor를 호출한다.
-> noexcept가 없으면 move constructor이 안전하지 않다고 생각해서 copy constructor를 사용한 것
-> 생각 할 것 : destructor, move constructor, move assignment는 noexcept를 붙이기
2) reserve를 통해 미리 공간을 확보한다. -> 가장 좋은 방법
cats.reserve(2);

vector loop

vector loop의 종류
- index base
- iterator base
- ranged base -> 가장 optimized 되어있다.

//index base
for (int i = 0; i < 1000; ++i)
{
	for (std::size_t idx = 0; idx < numsA.size(); ++idx)
	{
		numsA[idx] *= 2;
	}
}

//iterator base
for (auto iter = numsB.begin(); iter != numsB.end(); ++iter)
{
	(*iter) *= 2;
}

//ranged for loop
for (auto& num : numsC)
{
	num *= 2;
}

for loop안에서 벡터의 크기가 변하는 경우는 index base의 for loop를 사용해야 한다.
- iterator base를 사용할 때는 런타임 에러가 발생
  -> iter는 migrate하지 않은 array의 값들을 보면서 migrate한 array에 잘못된 값을 계속 넣는 과정을 실행한다.
  -> end()가 가리키는 곳은 이미 migrate한 곳이므로 잘못된 동작을 하고 있다.
- iterator base가 잘못된 동작을 하는 모습

erase, remove

벡터의 여러 element를 지우는 방법이다.
remove()는 iterator를 반환한다.
-> auto iter = std::remove(nums.begin(), nums.end(), 0);
-> remove는 O(n)의 시간 복잡도를 가진다.

#include<iostream>
#include<vector>
#include<string>

int main()
{
	std::vector<int>nums{ 0,1,0,1,0,1,0 };

	for (int num : nums)
	{
		std::cout << num << " "; //0 1 0 1 0 1 0
	}
	std::cout << std::endl;
    
	nums.erase(std::remove(nums.begin(), nums.end(), 0), nums.end());
    
	for (int num : nums)
	{
		std::cout << num << " "; //1 1 1
	}
	std::cout << std::endl;

	//람다 expression으로 짝수 삭제
	std::vector<int>nums2{ 0,1,2,3,4,5,6 };
    
	nums2.erase(std::remove_if(nums2.begin(), nums2.end(), [](int n)
		{
			if (n % 2 == 0)
				return true;
			return false; 
		}), nums2.end());

	for (int num2 : nums2)
	{
		std::cout << num2 << " "; //1 3 5
	}
    
	std::cout << std::endl;

std::array

std::array
- stack 공간에 allocate, compile 시간에 size 확보, fixed size
- fast
std::vector
- heap 공간에 allocate, runtime에 size 확보, flexible size
- slow (reserve()로 공간을 미리 확보하면 속도 보완 가능)
공통점 : 연속적인 메모리 공간 차지, random access 가능
C 스타일의 array 보다 C++ 의 std::array 쓰기
-> #include<array> 필요
-> std::array<int, 100> nums;

algorithms

sort
std::sort(시작, 끝, callable object);
-> callable object는 sorting 하는 방식을 선택
-> 안쓰면 오름차순

#include<iostream>
#include<algorithm>
#include<vector>

int main()
{
	std::vector<int>nums{ 1,3,4,5,100,2,66 };
	std::sort(nums.begin(), nums.end());

	for (auto num : nums)
	{
		std::cout << num << " "; //1 2 3 4 5 66 100
	}
	std::cout << std::endl;
    
	return 0;
}

stable_sort : 기준되로 sorting을 하되 기준 이외의 것은 stable하게 건들지 않고 놔둠
- {108, "Zaphod"},{32, "Arthur"},{108, "Ford"} 처럼 구성된 vector가 있을 때 숫자를 기준으로 stable_sort하면 중복된 숫자를 가진 것들은 원래 순서대로 정렬된다.
  -> {32, "Arthur"},{108, "Zaphod"},{108, "Ford"}
partial_sort : sort을 한 후 그중에서 top n을 뽑는 방식
nth_element : 벡터 자체의 순서를 변화시킴
min_element, max_element : 가장 작은, 큰 벡터의 값의 iterator를 반환
min_max_element: max와 min을 O(n)의 complexity로 찾아준다.
std::find() : ( )안에는 시작, 끝, 찾으려는 것 순서로 넣는다.
- std::distance() : ( )안에는 시작, 끝 순서로 넣는다.
  -> 시작으로부터 얼만큼 떨어진 인덱스인지 알려줌

#include<functional>
#include<vector>
#include<algorithm>
#include<iostream>

int main()
{
    const std::vector<int>nums{ 0,1,2,3,4 };

    const auto resultIter = std::find(nums.begin(), nums.end(), 2); //2를 찾음
    if (resultIter != nums.end())
    {
        std::cout << "idx: " << std::distance(nums.begin(), resultIter) << std::endl; //idx : 2 
    }
    else
    {
        std::cout << "no elem found" << std::endl;
    }
}

std::binary_search : sorting된 것들 중에서 찾을 때 빠른 방식
std::reduce & std::accumulate : return 값이 하나인 경우 사용(sum, product 등)
- accumulate : single thread
- reduce : parallel policy -> accumulate 보다 빠름

#include <iostream>
#include <vector>
#include <numeric>
#include <string>
#include <functional>

int main()
{
    std::vector<int> v{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

    int sum = std::accumulate(v.begin(), v.end(), 0);

    int product = std::accumulate(v.begin(), v.end(), 1, std::multiplies<int>());

    std::cout << "sum: " << sum << '\n'<< "product: " << product << '\n'; 
    // sum: 55 product: 3628800
}

N-dimensional array

2차원 array
std::array < std::array<int, 3>, 3> fixedMatrix;
2차원 vector
std::vector<std::vector<int>> dynamicMatrix(3, std::vector <int>(3));
2차원 데이터를 1차원 데이터로 만드는 것이 유리한 경우도 있다. (template 이용)

#include<array>
#include<vector>
#include<iostream>

template<typename T, int ROW, int COL>
class Matrix
{
public:
	Matrix(int ROW, int COL)
		:mMatrix(ROW* COL, 0)
	{
	}
	T& operator()(int rowIdx, int colIdx)
	{
		const int idx = rowIdx * COL + colIdx;
		return mMatrix[idx];
	}
private:
	std::vector<T>mMatrix;
};

int main()
{
	Matrix<int,10,10> mat(10, 10);
	mat(3, 3) = 3;
	mat(4, 3) = mat(3, 3) * 10;
	std::cout << mat(4, 3) << std::endl;
	return 0;
}

std::deque

deque : Double Ended Queue (맨 앞과 맨 뒤 둘 다 넣을 수 있다)
O(1)의 random access, 연속적인 데이터 저장은 아니다
-> by pointer reference
자주 사용하는 타입은 아니다.

#include <iostream>
#include <deque>

int main()
{
    std::deque<int> d = { 7, 5, 16, 8 };

    d.emplace_front(13);
    d.emplace_back(25);

    for (int n : d) 
    {
        std::cout << n << ' '; //13 7 5 16 8 25
    }
}

LeemHyungJun

이전 포스트

C++ Functional Programming

다음 포스트

C++ vector, array

C++ Study

vector Intro

std::vector

vector memory

vector loop

erase, remove

std::array

algorithms

N-dimensional array

std::deque

C++ Functional Programming

C++ list, stack, queue, heap

0개의 댓글