231201_DP
// 2156번 포도주 시식
/*
v x o o
? v x o
? ? v x
*/// 14501 퇴사
/*
N일에서부터 1일까지 최댓값을 업데이트하기
가능한지 체크
가능하면 그날 하기 + 한 뒤에 날부터 최댓값
안하기 i+1일 최댓값 그대로 쓰기
*/// 11052번 카드 구매하기
/*
dp[N]: N개를 갖기 위한 최댓값 update
dp[i-1] + v[1] vs v[i] X
가능한 숫자 조합이 전부 있어야 한다 X
0-i max + i의 값 vs dp[i]
*/// 11660번 구간 합 구하기 5
/*
누적 합 구하기 2차원 버전
1 2
3 4
4자리에 2 + 3 + 4 넣기
d[i-1][j] + d[i][j-1] + v[i][j]
왼쪽 위쪽 빼고 왼&&위 더하기 O
누적합 구할 때 왼&&위 겹쳐서 빼야하는 것 없었다
*/231202_다익스트라
// 1916번 최소비용 구하기
/*
노드 A-B만 원한다 그래도 다익스트라 쓰기...?
pq로 노드 더하면서 다른 노드에 대해서 전부 업데이트
결과 출력
최적화: pq에 넣어놨는데 이미 더 작은 값 있으면 체크 안하기
*/231204_Downscale buffer
Address UV
주소값 넘어갔을 때 처리
Wrap
타일붙이기
Clamp
마지막 픽셀 값 쓰기
HDR
렌더 타겟 float buffer로 사용한다
Downscale buffer
하드웨어가 지원하는 linear filter 사용
합성만 해도 가우시안 블러같이 나온다
// 3190번 뱀
/*
맵에 사과 놓기
while에서 초 카운트 하기
머리 방향에 따라 위치
사과 / 벽 / 몸
사과: 맵에서 체크해서 없애기, isApple = true
벽: 맵에서 체크해서 게임오버 하기
몸: 몸 모든 큐 빼서 돌면서 겹치는지 체크 게임오버하기
몸큐 돌면서 위치 옮겨주기
isApple이면 size 1일 때 마지막에 추가하기X
방향전환 배열에다가 모듈러로 +1 +3 해주기
몸큐에 꼬리-머리로 들어가 있어서 꼬리 넣는 순서가 잘못되었었다
*/231206_flattening
// 28. 가장 긴 회문 부분 문자열 출력하기
/*
flattening: std::vector<bool> table(len * len, false);
*/231211_Normal_TM
회전 행렬
Orthogonal Matrix
R^-1 == R^T == R(-seta)
역행렬 == 전치행렬 == -seta
Normal 벡터 TM
(M^-1)^T
역행렬하고 Transpose 한 값
면에 수직인 벡터이기 때문
// 2206번 벽 부수고 이동하기
/*
BFS +
0: 벽 안 부순 맵 이동 카운트
1: 벽 부순 맵 이동 카운트
*/231212_unordered_map bucket
map : red-black tree
검정 빨강으로 노드 색깔 분류해서 넣고 뺄 때 균형 유지한다
검정 깊이 같도록 유지한다
불균형 해지면 케이스에 따라 회전하기
unordered_map : bucket
replit 온라인 컴파일러에서는 해시로 모듈러 사용
→ 버킷 크기 * i + 1 해서 3000개 넣으면 다 1에 들어간다
비주얼 스튜디오에서는 다른 컴파일러로 해시가 되는 것 같다
m[i * bucketSize + 1] = 1;
13
29
59
127
257
541
1109
2357
5087
bucket #1 : 3000231213_deque
priority_queue : greater
function object 클래스로 () 오버로딩 했다
a > b 리턴한다
deque : 메모리 할당
고정된 사이즈 벡터로 구현된다
RedBlackTree Insert
넣은 다음에 조건 체크해서 회전한다
RedBlackTree delete
뺀 다음에 조건에 맞게 블랙 추가한다
231215발표데브루키TIL
https://docs.google.com/presentation/d/1i9RlhsHh1Ehl7TfJ89xuIqPeWOFwWVWCQGPWCgFB8qo/edit
TIL
Today I Learned
오늘 뭐 했는지 정리하기
23년의 TIL
C++
Modern C++
DSA
Graphics
Computer Science
Unreal
Project
C++
const
Function
Pointer / Reference
Constructor / Destructor
Class / Inheritance
Virtual Function
Modern C++
L / R Value
Template
Lambda
Smart Pointer
STL
Graphics
Graphics Pipeline
Transformation
Vertex / Mesh / Face / Normal
Texture / Normal Map
Computer Science
Compile
Execute
MultiThread
DSA
백준 문제풀기
DP
DFS / BFS
BackTracking
Floyd–Warshall / Dijkstra
Unreal
Udemy 강의 보면서 따라 만들기
Project
23.05.15 ~ 23.05.26
로봇은 실수하지 않아
23.07.31 ~ 23.08.25
잠에서 깨어날때까지 시간을 벌어줘
Tech Interview 2302 → 2310
https://github.com/SandyLee-00/TodayILearned/tree/main/TechInterview/2302
TODO
게임인재원
4Q프로젝트 수학 / 물리 / 충돌 파트 하기
이득우의 게임수학 참고해서 내 프로젝트 만들기
취업
The Modern C++ Challenge 코드 이해하기
리얼타임 렌더링 / 게임엔진 아키텍쳐 읽기
백준 Solved Class 4 문제 풀기
TechInterview 다시 채우기
기타
NDC 저장해 둔 영상 보기
231215_Combinatorial Explosion
Combinatorial Explosion
셰이더 Variant 키워드를 추가하는대로 조합의 경우의 수로 Varient 수가 늘어난다
Shader Variant
특정한 조건에 따라 동작이나 기능을 셰이더 코드에 도입하는 방법
Constant Buffer
VB IB 외에 상수를 전달할 방법
structured buffer → constant buffer : 성능 좋아진다
231217_DFS
// 16437번 양 구출 작전
/*
섬 많아서 벡터로 쓰기
각 S 노드에서 1 까지 DFS X 시간초과 났다
늑대 양 먹으면 사라지기
노드의 값, p의 child i 추가
dfs(1)
리프 늑대 0
리프 양 값 리턴
child node 값 갖고오기
현재 노드로 값 업데이트
값 체크해서 리턴하기
*/// 19542번 전단지 돌리기
/*
리프노드일 때 -D 리턴하기
child 노드 값 다 갖고오기
여러 개 거치는 노드 - -> 0으로 하기
par-child 둘 다 연결해서 다시 짰다
dfs로 S 루트 각 노드의 depth 구하기
현재 노드에서 child 다 돌기
max로 child들에서 리턴한 값 + 1
D보다 depth가 크면 방문해야하는 노드
*/231218_IPv4 데이터 형식 표현하는 함수 작성하기
// 7453번 합이 0인 네 정수
/*
3개는 그냥 고르기 4개째만 이진탐색으로 고르기 X
투포인터 + 이진탐색
벡터 2 + 2로 만들기
-> 4000^3 * log4000 X
16'000'000 * log16'000'000 O
이진탐색에서 찾은 위치가 더 크면
앞으로 가야하니까 end가 pos로 땡기기
이부분 조건 반대로 넣어놨었다
AB도 정렬 필요 캐시 히트
검색 결과 결과 값이 여러개 나올 경우 안했다
찾은 값 -- ++ 하면서 ret+= 1 하기 값 다 동일하게 들어올 경우 X
lower_bound, upper_bound로 위치 찾아서 개수 구하기
*/// 15. IPv4 데이터 형식 표현하는 함수 작성하기
/*
constexpr: 컴파일러가 컴파일하면서 컴파일타임에 상수로 바꿔준다
*this: 현재 객체 그대로 반환한다
>>: 32Bit를 8Bit씩 (== 1byte) 나누기 위해 24, 16, 8, 0으로 비트 이동한다
& 0xFF: 마지막 8Bit만 남긴다
|: 8Bit를 32Bit로 합친다
std::ios_base::failbit: stream의 상태를 나타내는 flag
array =: 그냥 =만 해도 배열 모든 원소 복사한다
{0}: data의 모든 요소를 0으로 초기화
friend: ostream이 ipv4의 private 멤버에 접근할 수 있게 해준다
ostream& operator<<: unsigned char로 하면 ASCII 코드로 출력되므로 int로 형변환
*/231219_Blur
Radial Blur
픽셀 위치에서 블러 시작점 방향으로 샘플링
시작점과 픽셀의 거리에 따라 Blur 가중치 계산
Full Scene Motion Blur
픽셀의 깊이값 → 3차원 World 좌표로 변환 (viewMT, proj MT 역행렬)
Depth 값 필요
Bloom
DownSample 한다음에 Gaussian blur
→ 원본에 Gaussian 하는 것보다 연산량이 줄어든다
Render Target
미리 GPU 메모리 잡아놓고 쓴다
new delete 연산 너무 느리다
Null check
new 했는데 메모리 못 줄 수 있다
Pixelate 픽셀화
픽셀의 uv 좌표를 불연속하게 만든다
Posterize 포스터처럼 보이기
Color 값 rgb를 불연속하게 만든다
// 1238번 파티
/*
플워로 모든 최단 경로 구하기
N -> X -> N
최댓값 구하기
31퍼에서 틀렸다고 나온다 왜지...?
결과값에 X->X가 MAX로 되어있어서 인 것 같다
i->k max이면 안돌게 최적화
*/231220_Deferred Rendering
Deferred Rendering (Light Pre Pass)
Scene Geometry / Lighting 분리한다
Geometry Pass → Lighting Pass
Geometry Pass
Object의 Geometry 정보(Position, Normal, Material) 를 Geometry Buffer에 저장한다
Lighting Pass
각 픽셀에 대한 Lighting 계산을 실행
Forward Rendering
모든 Object, 모든 Light 에 대한 Lighting 계산을 각 픽셀에 대해 직접 수행
MRT (Multiple Render Targets)
그래픽카드에서 MRT 지원해야 한다
231223_Searching
Linear
O(n)
LinearSearch(array, key)
for each item in the array
if item == value
return its indexBinary
O(log n)
do until the pointers low and high meet each other.
mid = (low + high)/2
if (x == arr[mid])
return mid
else if (x > arr[mid]) // x is on the right side
low = mid + 1
else // x is on the left side
high = mid - 1231226_PostProcessing
DOF (Depth Of Field)
카메라 렌즈에서 비출 때만 존재하는 현상
depthmap으로 초점과 픽셀 거리로 blur 적용한다
Depth
Z버퍼에 들어있는 픽셀의 z 값
Blur
한 픽셀에 대해 계산을 할 때 주변의 픽셀에서 값을 갖고와서 가중치를 매겨 한 픽셀의 값을 갖는다
SmoothStep
linear가 아니라 부드러운 보간을 한다
Hermite 보간을 리턴한다
LUT (Look Up Table)
텍스쳐에서 색깔 가져온다
Light Shaft (God Ray)
Radial Blur와 동일
light가 그려진 buffer에 Radiaul Blur 적용해서 합성한다
Edge Detect Filter
값이 급격하게 변하는 부분만 남긴다
카툰 렌더링 외곽선 그리기
Cube Map
환경을 6개 큐브 면에 그려서 표현한다
231227_unordered_map_GCC
https://github.com/gibsjose/cpp-cheat-sheet/blob/master/Data Structures and Algorithms.md
https://www.programiz.com/cpp-programming/unordered-map
https://www.programiz.com/dsa/hash-table
https://blog.ilvokhin.com/libstdc++-std-unordered-map/
Hash Table
O(1)
Key를 Hashing 해서 값이 있는 메모리에 바로 접근한다
chainedHashSearch(T, k)
return T[h(k)]
chainedHashInsert(T, x)
T[h(x.key)] = x //insert at the head
chainedHashDelete(T, x)
T[h(x.key)] = NILHash Table - **Linear Probing +** **Division Method**
// Implementing hash table in C++
#include <iostream>
#include <list>
using namespace std;
class HashTable
{
int capacity;
list<int> *table;
public:
HashTable(int V);
void insertItem(int key, int data);
void deleteItem(int key);
int checkPrime(int n)
{
int i;
if (n == 1 || n == 0)
{
return 0;
}
for (i = 2; i < n / 2; i++)
{
if (n % i == 0)
{
return 0;
}
}
return 1;
}
int getPrime(int n)
{
if (n % 2 == 0)
{
n++;
}
while (!checkPrime(n))
{
n += 2;
}
return n;
}
int hashFunction(int key)
{
return (key % capacity);
}
void displayHash();
};
HashTable::HashTable(int c)
{
int size = getPrime(c);
this->capacity = size;
table = new list<int>[capacity];
}
void HashTable::insertItem(int key, int data)
{
int index = hashFunction(key);
table[index].push_back(data);
}
void HashTable::deleteItem(int key)
{
int index = hashFunction(key);
list<int>::iterator i;
for (i = table[index].begin();
i != table[index].end(); i++)
{
if (*i == key)
break;
}
if (i != table[index].end())
table[index].erase(i);
}
void HashTable::displayHash()
{
for (int i = 0; i < capacity; i++)
{
cout << "table[" << i << "]";
for (auto x : table[i])
cout << " --> " << x;
cout << endl;
}
}
int main()
{
int key[] = {231, 321, 212, 321, 433, 262};
int data[] = {123, 432, 523, 43, 423, 111};
int size = sizeof(key) / sizeof(key[0]);
HashTable h(size);
for (int i = 0; i < size; i++)
h.insertItem(key[i], data[i]);
h.deleteItem(12);
h.displayHash();
}Hash Function
key로 idx에 접근하는 값 만드는 함수
Collision Resolution
해시값이 같을 때 하나의 버킷에 데이터 또 쓰면 덮어써진다 충돌 발생했을 때 문제 해결하기
Separate Chaining
버킷 뒤에 데이터 쭉 연결시켜서 넣는다
Open Addressing
빈 곳 있을 때까지 찾아보고 넣는다
Load Factor
해시 테이블에서 차 있는 버킷 수 / 전체 버킷 수
GCC's libstdc++ implementation
_HashTable
Nodes
Hash Table
Data Layout
* Each _Hashtable data structure has:
*
* - _Bucket[] _M_buckets
* - _Hash_node_base _M_before_begin
* - size_type _M_bucket_count
* - size_type _M_element_count
*
* with _Bucket being _Hash_node_base* and _Hash_node containing:
*
* - _Hash_node* _M_next
* - Tp _M_value
* - size_t _M_hash_code if cache_hash_code is true
*
* In terms of Standard containers the hashtable is like the aggregation of:
*
* - std::forward_list<_Node> containing the elements
* - std::vector<std::forward_list<_Node>::iterator> representing the buckets
*
* The non-empty buckets contain the node before the first node in the
* bucket. This design makes it possible to implement something like a
* std::forward_list::insert_after on container insertion and
* std::forward_list::erase_after on container erase
* calls. _M_before_begin is equivalent to
* std::forward_list::before_begin. Empty buckets contain
* nullptr. Note that one of the non-empty buckets contains
* &_M_before_begin which is not a dereferenceable node so the
* node pointer in a bucket shall never be dereferenced, only its
* next node can be.
*
* Walking through a bucket's nodes requires a check on the hash code to
* see if each node is still in the bucket. Such a design assumes a
* quite efficient hash functor and is one of the reasons it is
* highly advisable to set __cache_hash_code to true.
*
* The container iterators are simply built from nodes. This way
* incrementing the iterator is perfectly efficient independent of
* how many empty buckets there are in the container.
*
* On insert we compute the element's hash code and use it to find the
* bucket index. If the element must be inserted in an empty bucket
* we add it at the beginning of the singly linked list and make the
* bucket point to _M_before_begin. The bucket that used to point to
* _M_before_begin, if any, is updated to point to its new before
* begin node.
*
* On erase, the simple iterator design requires using the hash
* functor to get the index of the bucket to update. For this
* reason, when __cache_hash_code is set to false the hash functor must
* not throw and this is enforced by a static assertion.
*
* Functionality is implemented by decomposition into base classes,
* where the derived _Hashtable class is used in _Map_base,
* _Insert, _Rehash_base, and _Equality base classes to access the
* "this" pointer. _Hashtable_base is used in the base classes as a
* non-recursive, fully-completed-type so that detailed nested type
* information, such as iterator type and node type, can be
* used. This is similar to the "Curiously Recurring Template
* Pattern" (CRTP) technique, but uses a reconstructed, not
* explicitly passed, template pattern._Hash_node_base
/**
* struct _Hash_node_base
*
* Nodes, used to wrap elements stored in the hash table. A policy
* template parameter of class template _Hashtable controls whether
* nodes also store a hash code. In some cases (e.g. strings) this
* may be a performance win.
*/
struct _Hash_node_base
{
_Hash_node_base* _M_nxt;
_Hash_node_base() noexcept : _M_nxt() { }
_Hash_node_base(_Hash_node_base* __next) noexcept : _M_nxt(__next) { }
};_Hash_node_value_base
/**
* struct _Hash_node_value_base
*
* Node type with the value to store.
*/
template<typename _Value>
struct _Hash_node_value_base
{
typedef _Value value_type;
__gnu_cxx::__aligned_buffer<_Value> _M_storage;
_Value*
_M_valptr() noexcept
{ return _M_storage._M_ptr(); }
const _Value*
_M_valptr() const noexcept
{ return _M_storage._M_ptr(); }
_Value&
_M_v() noexcept
{ return *_M_valptr(); }
const _Value&
_M_v() const noexcept
{ return *_M_valptr(); }
};_Hash_node_code_cache
해시 값 캐싱 로직
/**
* Primary template struct _Hash_node_code_cache.
*/
template<bool _Cache_hash_code>
struct _Hash_node_code_cache
{ };
/**
* Specialization for node with cache, struct _Hash_node_code_cache.
*/
template<>
struct _Hash_node_code_cache<true>
{ std::size_t _M_hash_code; };Hash Table
private:
__buckets_ptr _M_buckets = &_M_single_bucket;
size_type _M_bucket_count = 1;
__node_base _M_before_begin;
size_type _M_element_count = 0;
_RehashPolicy _M_rehash_policy;
// A single bucket used when only need for 1 bucket. Especially
// interesting in move semantic to leave hashtable with only 1 bucket
// which is not allocated so that we can have those operations noexcept
// qualified.
// Note that we can't leave hashtable with 0 bucket without adding
// numerous checks in the code to avoid 0 modulus.
__node_base_ptr _M_single_bucket = nullptr; * In terms of Standard containers the hashtable is like the aggregation of:
*
* - std::forward_list<_Node> containing the elements
* - std::vector<std::forward_list<_Node>::iterator> representing the bucketsInsert
_M_insert_unique
// Insert v if no element with its key is already present.
template<typename _Key, typename _Value, typename _Alloc,
typename _ExtractKey, typename _Equal,
typename _Hash, typename _RangeHash, typename _Unused,
typename _RehashPolicy, typename _Traits>
template<typename _Kt, typename _Arg, typename _NodeGenerator>
auto
_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
_Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
_M_insert_unique(_Kt&& __k, _Arg&& __v,
const _NodeGenerator& __node_gen)
-> pair<iterator, bool>
{
if (size() <= __small_size_threshold())
for (auto __it = begin(); __it != end(); ++__it)
if (this->_M_key_equals_tr(__k, *__it._M_cur))
return { __it, false };
__hash_code __code = this->_M_hash_code_tr(__k);
size_type __bkt = _M_bucket_index(__code);
if (size() > __small_size_threshold())
if (__node_ptr __node = _M_find_node_tr(__bkt, __k, __code))
return { iterator(__node), false };
_Scoped_node __node {
__node_builder_t::_S_build(std::forward<_Kt>(__k),
std::forward<_Arg>(__v),
__node_gen),
this
};
auto __pos
= _M_insert_unique_node(__bkt, __code, __node._M_node);
__node._M_node = nullptr;
return { __pos, true };
}_M_insert_unique - iterator
template<typename _Key, typename _Value, typename _Alloc,
typename _ExtractKey, typename _Equal,
typename _Hash, typename _RangeHash, typename _Unused,
typename _RehashPolicy, typename _Traits>
auto
_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
_Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
_M_insert_unique_node(size_type __bkt, __hash_code __code,
__node_ptr __node, size_type __n_elt)
-> iterator
{
const __rehash_state& __saved_state = _M_rehash_policy._M_state();
std::pair<bool, std::size_t> __do_rehash
= _M_rehash_policy._M_need_rehash(_M_bucket_count, _M_element_count,
__n_elt);
if (__do_rehash.first)
{
_M_rehash(__do_rehash.second, __saved_state);
__bkt = _M_bucket_index(__code);
}
this->_M_store_code(*__node, __code);
// Always insert at the beginning of the bucket.
_M_insert_bucket_begin(__bkt, __node);
++_M_element_count;
return iterator(__node);
}해시 테이블 버킷 수는 소수
// Return a prime no smaller than n.
std::size_t
_Prime_rehash_policy::_M_next_bkt(std::size_t __n) const
{
// Optimize lookups involving the first elements of __prime_list.
// (useful to speed-up, eg, constructors)
static const unsigned char __fast_bkt[]
= { 2, 2, 2, 3, 5, 5, 7, 7, 11, 11, 11, 11, 13, 13 };
if (__n < sizeof(__fast_bkt))
{
if (__n == 0)
// Special case on container 1st initialization with 0 bucket count
// hint. We keep _M_next_resize to 0 to make sure that next time we
// want to add an element allocation will take place.
return 1;
_M_next_resize =
__builtin_floor(__fast_bkt[__n] * (double)_M_max_load_factor);
return __fast_bkt[__n];
}
// Number of primes (without sentinel).
constexpr auto __n_primes
= sizeof(__prime_list) / sizeof(unsigned long) - 1;
// Don't include the last prime in the search, so that anything
// higher than the second-to-last prime returns a past-the-end
// iterator that can be dereferenced to get the last prime.
constexpr auto __last_prime = __prime_list + __n_primes - 1;
const unsigned long* __next_bkt =
std::lower_bound(__prime_list + 6, __last_prime, __n);
if (__next_bkt == __last_prime)
// Set next resize to the max value so that we never try to rehash again
// as we already reach the biggest possible bucket number.
// Note that it might result in max_load_factor not being respected.
_M_next_resize = size_t(-1);
else
_M_next_resize =
__builtin_floor(*__next_bkt * (double)_M_max_load_factor);
return *__next_bkt;
}Find
숫자 작을 때 - linear search
if (size() <= __small_size_threshold())
{
for (auto __it = begin(); __it != end(); ++__it)
if (this->_M_key_equals(__k, *__it._M_cur))
return __it;
return end();
}숫자 클 때 - bucket search
__hash_code __code = this->_M_hash_code(__k);
std::size_t __bkt = _M_bucket_index(__code);
return const_iterator(_M_find_node(__bkt, __k, __code));_M_find_node
__node_ptr
_M_find_node(size_type __bkt, const key_type& __key,
__hash_code __c) const
{
__node_base_ptr __before_n = _M_find_before_node(__bkt, __key, __c);
if (__before_n)
return static_cast<__node_ptr>(__before_n->_M_nxt);
return nullptr;
}_M_find_before_node
// Find the node before the one whose key compares equal to k in the bucket
// bkt. Return nullptr if no node is found.
template<typename _Key, typename _Value, typename _Alloc,
typename _ExtractKey, typename _Equal,
typename _Hash, typename _RangeHash, typename _Unused,
typename _RehashPolicy, typename _Traits>
auto
_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
_Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
_M_find_before_node(size_type __bkt, const key_type& __k,
__hash_code __code) const
-> __node_base_ptr
{
__node_base_ptr __prev_p = _M_buckets[__bkt];
if (!__prev_p)
return nullptr;
for (__node_ptr __p = static_cast<__node_ptr>(__prev_p->_M_nxt);;
__p = __p->_M_next())
{
if (this->_M_equals(__k, __code, *__p))
return __prev_p;
if (!__p->_M_nxt || _M_bucket_index(*__p->_M_next()) != __bkt)
break;
__prev_p = __p;
}
return nullptr;
}Erase
숫자 작을 때 - linear search
if (size() <= __small_size_threshold())
{
__prev_n = _M_find_before_node(__k);
if (!__prev_n)
return 0;
// We found a matching node, erase it.
__n = static_cast<__node_ptr>(__prev_n->_M_nxt);
__bkt = _M_bucket_index(*__n);
}숫자 클 때 - bucket search
else
{
__hash_code __code = this->_M_hash_code(__k);
__bkt = _M_bucket_index(__code);
// Look for the node before the first matching node.
__prev_n = _M_find_before_node(__bkt, __k, __code);
if (!__prev_n)
return 0;
// We found a matching node, erase it.
__n = static_cast<__node_ptr>(__prev_n->_M_nxt);
}_M_erase
template<typename _Key, typename _Value, typename _Alloc,
typename _ExtractKey, typename _Equal,
typename _Hash, typename _RangeHash, typename _Unused,
typename _RehashPolicy, typename _Traits>
auto
_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
_Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
_M_erase(true_type /* __uks */, const key_type& __k)
-> size_type
{
__node_base_ptr __prev_n;
__node_ptr __n;
std::size_t __bkt;
if (size() <= __small_size_threshold())
{
__prev_n = _M_find_before_node(__k);
if (!__prev_n)
return 0;
// We found a matching node, erase it.
__n = static_cast<__node_ptr>(__prev_n->_M_nxt);
__bkt = _M_bucket_index(*__n);
}
else
{
__hash_code __code = this->_M_hash_code(__k);
__bkt = _M_bucket_index(__code);
// Look for the node before the first matching node.
__prev_n = _M_find_before_node(__bkt, __k, __code);
if (!__prev_n)
return 0;
// We found a matching node, erase it.
__n = static_cast<__node_ptr>(__prev_n->_M_nxt);
}
_M_erase(__bkt, __prev_n, __n);
return 1;
}_M_erase - iterator
template<typename _Key, typename _Value, typename _Alloc,
typename _ExtractKey, typename _Equal,
typename _Hash, typename _RangeHash, typename _Unused,
typename _RehashPolicy, typename _Traits>
auto
_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
_Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
_M_erase(size_type __bkt, __node_base_ptr __prev_n, __node_ptr __n)
-> iterator
{
if (__prev_n == _M_buckets[__bkt])
_M_remove_bucket_begin(__bkt, __n->_M_next(),
__n->_M_nxt ? _M_bucket_index(*__n->_M_next()) : 0);
else if (__n->_M_nxt)
{
size_type __next_bkt = _M_bucket_index(*__n->_M_next());
if (__next_bkt != __bkt)
_M_buckets[__next_bkt] = __prev_n;
}
__prev_n->_M_nxt = __n->_M_nxt;
iterator __result(__n->_M_next());
this->_M_deallocate_node(__n);
--_M_element_count;
return __result;
}Cache Unfriendliness
RAM에 메모리가 불연속적으로 올라와 있다
노드가 쓸 공간을 각자 힙에 잡고 포인터로 연결만 해두었다
reference and iterator stability
standard에서 호환되어야 한다
Separate chaining
각 버킷에 쭉 데이터 연결하는 방식으로 쓴다
231228_BinarySearch
// 2110번 공유기 설치
/*
간격을 최대로 할 수 있는 범위 이분탐색으로 정하기
정한 간격 이상으로 해당 공유기 전부 놓을 수 있는지 찾기
통과되면 간격 넓히기 안되면 간격 줄이기
해당 거리로 놓는 것이 유효한지 체크 못했다
1번째 집 꼭 놓는다
*/// 2957번 이진 탐색 트리
/*
30만까지 들어온다 ->포인터 안쓰고 배열 인덱스만 갖고 있기 X
포인터 쓰기 싫다... 다른 언어 어떻게 구현...? 일단 할수있는걸로 만들어보고 힌트 보기
시간초과 났다: 쭉 들어올 때 경우 넣는데 30만 * 30만 걸린다
-> 직접 구현해서 돌리면서 카운트 X
insert 할 때 동작...?
*/