set 검색 결과

해당 글 7건
c++ set이나 map을 전체 순회하는 데 시간 복잡도는 얼마일까요?

질문이 하나 들어왔습니다. 아래에 있는 foo 함수의 시간 복잡도는 어떻게 되나요? 쉽지 않은 질문입니다. c++에서 map이나 set은 self balanced binary Tree로 되어 있습니다. 흔히 '균형 트리' 라고 이야기를 합니다. 중요한 것은 어느 기준 점을 기준으로 왼쪽은 작은 것이, 오른쪽은 큰 것이 저장이 되어 있다는 것입니다. set이나 map이 Binary Tree의 속성을 가진다는 것은 시간 복잡도를 계산하는 데 굉장히 중요한 정보입니다. 즉, root를 기준으로 작은 것은 L, 큰 것은 R 부분에 있습니다. 그렇다면, iterator를, s.begin()부터, s.end()에 도달할 때 까지, 순회한다고 생각해 봅시다. 즉, 작은 것부터 큰 순서대로 순회를 한다고 하면 어떻게 ..
자료알고/자료구조 2020. 1. 31. 01:11
반복자 무효화 : 어떠한 연산을 조심해야 할까요?

STL을 공부하시다 보면, 반복자 무효화라는 용어는 한 번 쯤 들어보셨으리라 생각합니다. 반복자는 순회, 탐색 등을 위해서 쓰는 녀석인데요. 이것이 어떠한 이유로 무효화가 될 수 있습니다. 보통, iterator가 가리키는 것이 삭제 되었을 때 무효화가 되는데요. vector와 같이, 동적 배열을 사용할 때는 그 이외에도 조심해야 할 부분들이 몇 가지 더 있어요. 예제 프로그램 1을 봅시다. 먼저, 이 프로그램을 생각해 봅시다. vector v에 원소를 200개 추가했습니다. 그리고, 이 때, 벡터의 시작 원소를 iter가 가리키게 했습니다. 그리고 난 다음에, v에다가 0부터 1999까지 또 추가를 합니다. 프로그램에는, 벡터에 remove 연산을 가하지 않았습니다. 그런데 결과가 의외입니다. 0 0 ..
레퍼런스/예제 2019. 8. 8. 18:47