참고자료
배열 : https://learn.microsoft.com/ko-kr/cpp/cpp/arrays-cpp?view=msvc-170
constexpr : https://learn.microsoft.com/ko-kr/cpp/cpp/constexpr-cpp?view=msvc-170
1. Array
특징
- 인접한 메모리 영역 차지
생성 방식
- 스택 선언
constexpr size_t size = 1000;
double numbers[size]{ 0 };
numbers[0] = 1;
for (size_t i = 1; i < size; ++i)
{
numbers[i] = numbers[i - 1] * 1.1;
}
for (const auto n : numbers)
{
cout << n << " "; //1 1.1 1.21 1.331 ...
}- 힙 선언 (동적)
size_t size2 = 100;
int* numbers2 = new int[size2] {0};
numbers2[0] = 1;
for (size_t i = 1; i < size2; ++i)
{
numbers2[i] = 100;
}
int* p = numbers2;
for (size_t i = 0; i < size2; ++i)
{
cout << *(p++) << " "; //100 100 100 100 ...
}- stl array ->
#include <array>필요
array<int, 3> a1;
a1[0] = 100;
a1[1] = 200;
a1[2] = 300;추가
- 함수에 배열 전달
- 배열이 함수에 전달되면 첫번째 요소에 대한 포인터로 전달된다.
- 예시)
int Sum(const int *num, const size_t len) { int sum = 0; for (size_t i = 0; i < len; ++i) { sum += num[i]; } return sum; }
constexpr변수- 컴파일 시간에 초기화해야 한다.
- 컴파일 도중에 "반드시" 값이 결정되도록 할 때 사용
- 예시
constexpr float x = 42.0f;-> ok
constexpr int i;-> error (초기화 불가)
constexpr int k = i+1
size_t- 정의 :
typedef unsigned __int64 size_t; - 64비트일 때 8바이트 unsigned int
- 주로 배열 인덱싱 및 loop계산에 사용된다.
-> unsigned_int가 UINT_MAX를 초과하는 경우 예방?
- 정의 :
2. Vector
특징
- 어떤 자료형도 넣을 수 있는 동적 배열
- 연속된 메모리 공간에 위치
- 자동 메모리 관리, 어떤 요소에도 임의 접근 가능
생성 방식
std::vector<int> name1;
std::vector<int> name2(name1); : 복사 생성자
std::vector<int> name3(10); : 0으로 값 초기화
- vector 생성 후에
reserve()써서 속도 빠르게 하는 것 좋다.
기본 함수
push_back() : 삽입
pop_back() : 삭제
reserve() : 공간 할당 하기
capacity() : 할당된 요소의 공간 수
size() : 실제 들어있는 요소의 수
insert(iterator, value) : value를 특정 위치에 삽입
erase(iterator) : 특정 위치의 요소 삭제
assign(num, value) : vector를 value로 num 만큼 할당하기
swap(vector) : vector 교환하기
resize() :
clear() : 모든 요소 제거, 크기 0이지만, 용량은 그대로
사용 예시
#include <iostream>
#include <vector>
using namespace std;
int main()
{
vector<int> vec1;
vector<int> vec2;
vec1.reserve(10);
vec1.push_back(10);
vec1.push_back(20);
vec1.push_back(30);
vec2.assign(11, 100);
//순차적으로 출력
for (vector<int>::const_iterator it = vec1.begin(); it != vec1.end(); ++it)
{
cout << *it << endl; //10 20 30
}
cout << "\n";
//역으로 출력
for (vector<int>::reverse_iterator it = vec1.rbegin(); it != vec1.rend(); ++it)
{
cout << *it << endl; //30 20 10
}
cout << "\n";
//vector 교환
vec1.swap(vec2);
for (vector<int>::const_iterator it = vec1.begin(); it != vec1.end(); ++it)
{
cout << *it << endl; //100 100 100 100 100 100 100 100 100 100 100
}
//vector 지우기
vec1.clear();
cout << vec1.size() << " " << vec1.capacity() << endl; //0 11
cout << "\n";
//특정 위치 삽입
vector<int>::iterator iter = vec2.begin();
vec2.insert(iter + 1, 100);
for (vector<int>::const_iterator it = vec2.begin(); it != vec2.end(); ++it)
{
cout << *it << endl; //10 100 20 30
}
cout << "\n";
}추가
- 포인터 벡터
3. List
특징
- double linked list와 같은 구조
- 삽입과 제거 O(1), 메모리 연속으로 존재하지 않음
- 탐색이 느림, 임의 접근 불가능
사용 함수
push_front()
push_back()
사용 예시
#include <list>
#include <iostream>
using namespace std;
int main()
{
list<int> scores;
scores.push_back(10);
scores.push_back(20);
scores.push_front(30);
list<int>::const_iterator it = scores.begin();
for (; it != scores.end(); ++it)
{
cout << *it << endl; //30 10 20
}
}4. Map
특징
- key와 value의 쌍을 저장하는 자료구조
- key를 기준으로 정렬된다. -> 이진 탐색 트리 기반
- 시간복잡도 O(logN) -> 탐색 속도는 vector보다 빠르다.
- 만들면 자동으로 정렬된다.
- 해쉬맵이 아니다.
사용 함수
insert() : key와 value값 삽입
-> 이미 있는 key 값을 insert 하면 false 반환한다.
[] operator : 참조 반환
-> 없는 키를 쓰면 새 요소 삽입, 있는 키값이면 덮어쓰기
find() : key값을 찾으면 해당 key 가지는 iterator 반환
swap() : 두 map의 key와 value 바꾸기
clear() : map 비우기
erase() : 한 요소 제거
사용 예시
#include <map>
#include <string>
#include <iostream>
using namespace std;
int main()
{
map<string, int> Scores;
Scores.insert(pair<string, int>("A", 100));
Scores.insert(pair<string, int>("B", 80));
Scores.insert(pair<string, int>("C", 50));
Scores.insert(pair<string, int>("C", 10)); //false
Scores["D"] = 30;
cout << Scores["A"] << endl; //100
cout << Scores["C"] << endl; //50
cout << Scores["D"] << endl; //30
//복사 생성자
map<string, int> copyScores(Scores);
for (map<string, int>::iterator it = copyScores.begin(); it != copyScores.end(); ++it)
{
cout << it->first << " " << it->second << endl;
}
map<string, int>::iterator it = Scores.find("A");
if (it != Scores.end()) // 찾았을 때 -> 못찾으면 end iterator 반환
{
it->second = 99;
}
cout << Scores["A"] << endl; //99
Scores.swap(copyScores);
cout << copyScores["A"] << " " << Scores["A"] << endl; //99 100
}참고
- map에 내가 만든 class를 넣는 경우
- 해당 class의 key를 비교하는 operator나 compare 함수를 구현해야함
- 사용 예시
class Player
{
public:
Player(int s,int i, string n)
:Score(s)
,ID(i)
,Name(n)
{
}
bool operator<(const Player& other)const //operator 구현
{
return this->getScores() < other.getScores();
}
int getScores() const
{
return this->Score;
}
string getName() const
{
return this->Name;
}
private:
int Score;
int ID;
string Name;
};
class PlayerCompare //compare 함수 구현
{
public:
bool operator() (const Player& left, const Player& right) const
{
return (left.getScores() < right.getScores());
}
};
int main()
{
Player p1{ 100, 1, "AAA" };
Player p2{ 50, 2, "BBB" };
//operator 연산자
map<Player, string> test;
test.insert(pair<Player, string>(p1, "aaa"));
test.insert(pair<Player, string>(p2, "bbb"));
cout << test[p1] << " " << test[p2] << endl; // aaa bbb
//compare 함수
map<Player, string, PlayerCompare> test2;
test2.insert(pair<Player, string>(p1, "aaa"));
test2.insert(pair<Player, string>(p2, "bbb"));
for (map<Player, string>::iterator it = test2.begin(); it != test2.end(); ++it)
{
cout << it->first.getName() << ", " << it->second << endl; //BBB bbb AAA aaa
}
}5. Unordered_map
특징
- 정렬안된 map
- 해쉬로 구현되어서 일반 map 보다 빠르다.
- 특정값이 해쉬함수를 거쳐 index가 되고 bucket에 index를 통해 O(1)의 검색시간 가능하다.
- 그러나 bucket 때문에 메모리 사용량은 증가
- 해쉬 함수는 충돌이 나지 않게 만드는 것이 중요하다.
- 해쉬 충돌이 생기지 않는 해쉬맵
- Closed Addressing (Chaining)
- 충돌이 발생하면 같은 버킷에 여러 항목을 저장하는 방법
- Open Addressing
- 충돌이 발생하면 다른 빈 버킷을 찾는 방법
- Closed Addressing (Chaining)
