Dev/C,C++ (6) 썸네일형 리스트형 vector<int> 보다 vector<bool> 이 느리다? 문제를 풀다가 vector 로 요소 체크를 하면 통과하는데 vector 로 처리하니까 TLE가 발생했다.이게 뭔 개소리야가 절로나와서 찾아보니 bool의 저장 방식 떄문이었다.메모리 배치 및 엑세스 속도vector 의 경우내부적으로 int 타입의 배열과 비슷하게 배치된다.vector 의 경우메모리를 효율적으로 관리하기 위해 한 번에 여러개의 bool 값을 저장할 수 있는 bitfield로 구현된다. 즉, 하나의 정수에 여러 bool 값을 비트 단위로 저장하게 된다.그래서 만약 저장된 bool 값을 조작하려면 해당 비트를 조작하기 위한 비트마스크 연산이 추가로 필요하게 되어 오버헤드가 발생하기 때문에 vector은 속도가 저하게된다.결론은, bool 은 메모리 효율을 위해 시간 효율을 희생했다고 보면 된다.. C++ vector 초기화 방법 vector는 자유롭게 크기에 상관없이 데이터를 삽입할 수 있지만 초기화를 해놓고 행렬처럼 사용하고 싶을 수가 있다. 그럴 때 사용하는 방법이다. vector vec(3); //1 vector vec(3, -1); //2 1번 : 크기 3으로 모두 0으로 초기화 2번 : 크기 3으로 모두 -1로 초기화 vector vec(n, vector(m,-1)); 다차원 벡터 초기화. n행 m열로 초기화 시퀀스 컨테이너 - list 더블 링크드 리스트가 구현되어있는 라이브러리이다. 그러나 리스트 형태이기 때문에 iterator로 순회해야하고 배열 벡터 처럼 [] 조회는 불가능하다. 삽입 - list.push_back(a) - list.push_front(a) 삭제 - list.remove(a) * 중복된 원소까지 전부 삭제한다. - list.remove(*a) * 여기서 이는 iterater이다. 그 원소만 삭제한다. - pop_front() - pop_back() 탐색 find(list.begin(), list.end(), 원소) 찾으면 그 위치 주소, 아니면 마지막 주소 C++ 문자열 자르기 split / 문자열 <-> 정수 형 변환 C++로 PS를 하다보면 가장 짜증날 때가 문자열을 다룰때일 것이다. 문자열을 파싱할때, 문자열을 정수형으로 변환하거나 역변환할때 자바 파이썬 사용자들은 편한 방법을 사용할 수 있지만 C++ 유저들은 이것 또한 암기를 하고 있어야한다. 1. #include string stream 의 약자이다. 특이하게 cin >> 으로 입력하는 방식과 다르게 > tmp) { STR.push_back(tmp); } for (auto a : STR) cout tmp) { STR.push_back(tmp); } cout C++ 연관 컨테이너 set, mutiset set, map은 유사하지만 set은 map보다 작고 모든 삽입, 탐색, 삭제 속도 모두 set이 월등하다. 단, set은 map처럼 막 변수처럼 쓸수는 없고 이 key가 있는지 없는지만 판단 가능하다. 값을 확인하려면 포인터의 접근법을 사용해야하기 때문에 댕글링 포인터나 메모리 누수가 발생할 수 있어 정교한 코딩이 요구된다. 삽입 : insert O(logN) 삭제 : delete O(logN) 탐색 : find O(logN) set은 중복 key를 허용하지 않지만 mutiset은 포함한다, 그리고 set은 자동정렬이 된다. map의 다양한 사용법 - key, value 순으로 정렬, auto 반복문 기본적인 사용법: 선언 - map test; 삽입 - test.insert(make_pair(key, value)) 제거 - test.erase(key) ex) #include #include #include using namespace std; int main() { map test; test.insert(make_pair(1, 10)); test.insert(make_pair(2, 9)); test.insert(make_pair(3, 8)); test.insert(make_pair(4, 7)); test.insert(make_pair(5, 6)); cout 이전 1 다음
