본문 바로가기

C

 (101)
c++ list와 vector 비교 실무에서는 99% Vector를 쓴다고 보면 된다. Time Complexity Find Random Access Insertion/Deletion I/D back Vector O(N) O(1) O(n) O(1) List O(N) O(1) O(1) O(1) 각 연산에 대한 Time complexity를 보면 List가 좋아 보인다. 하지만 메모리는 연속 격자 구조 이기에 Vector가 훨씬 빠르다. List는 메모리가 여기 저기 흩어져 있다. 그리고 연속 구조가 아니기 때문에 병렬 프로그래밍이 어렵다. List는 emplace back, emplace front 명령이 있고 emplace(iterator, value)로 해당 위치에 value를 입력할 수 있다. 그리고 merge와 splice를 활용해서..
c++ set,map,unorded_set,unordered_map 정리 set, map은 트리 구조여서 O(log(n))으로 remove,insertion,access가 가능하다. 또한 sorted 되어 있다. 그리고 별도로 comparision operator를 정의해야 한다. unordered_set, unordered_map은 hash를 사용하여 O(1)로 가능하다. 이름과 같이 unordered이기 때문에 sort는 불가능하다. 그러나 사이즈가 커지면 O(n)의 복잡도로 rehashing이 일어날 수 있다. 이를 방지하기 위해서 reserve로 메모리를 미리 확보해야 한다. 또한 ==operator와 hashing 구조체를 별도로 구현해야 한다. 그리고 unoredred_map의 코드를 첨부한다. set과 unordered_set은 Key만 고려하면 되고 map과 u..
c++ unordered_set 사용 기록 unordered set을 사용하기 위해서는 직접 hash 구조체와 operator==를 정의해 주어야 한다. hash 구조체를 namespace std에 지정하면 별도로 hash 구조체를 안 넣어줘도 된다. unordered set은 time complexity가 O(1)이다. 코드 >> 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 8..
c++ map 사용 방법 map은 Key value 관계로 데이터를 저장한다. set과 마찬가지로 Key 값이 중복되면 저장이 잘 안된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 #include #include #include int main() { std::map numPairs; numPairs.emplace(2, 102); numPairs.emplace(3, 103); numPairs.emplace(4, 104); numPairs.emplace(5, 105); // 1이 중복이라 추가 안 됨; numPa..
c++ set, multiset, 커스텀 비교 함수, 커스텀 클래스 set은 search, removal, insertion을 logn time complexity로수행 가능하다. set을 사용할때 custom한 함수를 넣어서 비교를 할 수있다. 다만 중복 되면 입력이 잘 안된다. 따라서 중복이 되는 데이터를 다룰 때는 multiset을 사용하도록 하자 그리고 클래스를 넣을 수도 있는데 꼭 비교 operator를 넣어 주도록 하자 코드 >> 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 6..
c++ stl deque 설명, 성능상 이슈 deque은 vector와 다르게 삽입, 제거 과정을 o(1)에 할 수 있다. 이게 가능한 이유는 deque는 벡터를 여러 공간에 저장하기 때문이다. 하지만 메모리 관점상 좋지 않다. (코딩테스트 할 때는 도움이 될지 모르겠다) 굳이 필요한 경우가 아니라면 vector를 사용하도록 하자. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 #include #include int main() { std::deque d = { 7,5,16,8 }; //o1 time complexity d.push_front(13); d.emplace_back(15); d.push_back(25); d.emplace_back(16); for (int n : d) { std::cout
c++ vector, array 다차원 배열, 2d array를 1d처럼, 성능 주의점 Vector의 다차원 배열은 Array와 메모리 구조가 다르다. Vector가 만약 2*2 배열이라면 행에 해당하는 부분은 stack에 저장되며 stack 저장되는 것은 상위 vector의 pointer, size, capacity이다. 이후 하위 vector는 힙에 저장되며 힙에 vector의 pointer, size, capacity가 저장된다. 하위 벡터의 pointer가 다시 자료가 존재하고 있는 heap을 가르키게 된다. 그리고 벡터가 띄엄띄엄 존재하면 성능상 손해다. 따라서 1d로 벡터를 만들어주는 클래스를 만들었다. 다차원 배열의 for loop을 위해서는 cache 방향으로 for loop 을 해야 한다. 성능 차이가 꽤 크다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1..
c++ vector sort, stable_sort, partial_sort, nth_element, minmax, find, accumulate 코드 c++ vector, sort, stable_sort, minmax, find, accumulate 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112..

티스토리툴바