[C++] STL 순차 컨테이너 STL Sequence Container (Vector, List)

드디어 컨테이너 챕터로 넘어간다 !!

STL Sequence Container은 객체를 sequential oreder (순차적) 으로 저장하는 데이터 구조이다

 

Sequence Containers	Type of Iterator Supported	description
vector (implemented as a dynamic array)	Random Access	동적 배열로 구현된 자료구조, 배열과 유사한 선형구조로 데이터를 연속적으로 저장하여 동적으로 크기를 조절할 수 있음. 데이터 삽입, 삭제가 잦은 경우에는 적절하지 않음.
list (implemented as a doubly-linked list)	Bidirectional	이중 연결 리스트로 구현된 자료구조, 각 요소가 이전 요소와 다음 요소의 주소를 가지고 있고 데이터를 순차적으로 저장함. 데이터 삽입 삭제가 잦을 경우에는 빠른 성능을 보이지만, 임의의 위치에 있는 요소에 접근할때는 효용성이 떨어짐.

 

* Random Access : 배열의 요소를 임의의 위치에서 직접 액세스 할 수 있는 기능 

-> 인덱스 연산자(sunscript operator) 를 사용하여 배열의 특정요소에 액세스 : array[i]

---

vector container

• implemented as a dynamic array : 동적배열로 구현됨. array와 유사하게 연속적인 메모리 공간에 요소를 저장하고 필요에 따라 크기를 동적으로 조정할 수 있음.
• can access elements randomly (임의적으로 접근)
• 기본생성자(default constructor)이외에도 다양한 생성자를 포함 -> 다양한 방법으로 vector을 초기화하고 생성가능
• size -> number of elements / capcity -> how much memeory is allocated to contain elements.

---

기본 생성자 default constructor

.reserve()

vector<int> vector1; //capacity = 0
vector1.reserve(20);
//reserve() sets an initial capacity for the vector = 20
vector1.push_back(10); //capacity = 1
vector1.push_back(20); //capacity = 2

 

 

복사 생성자 copy constructor

vector<int> vector2(vector1);
vector<int> vector3 = vector1;

 

초기화 리스트 생성자 initializer list constructor

vector<int> vector4{ 130, 750, 259, 1234};
vector<int> vector5 = {234, 54, 5634, 65};
// set size and capacity right away + with specific elements!!

 

범위 생성자 Range constructor

vector<int> vector5 {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
vector<int> vector6 (vector5.begin() + 2, vector5.begin() +6);
//vector6 becomes : 30 40 50 60

• (20, 50) "closed range" => 20 30 40 50 
• [20, 50] "open range" => 30 40 
• [20, 50) "half open range" => 30 40 50

vector capacity 

• vector grows automatically; by default their capacity is increased as needed
• tho do not shrink automatically; maintain the same capacity 

#include <iostream>
#include <vector>

int main() {
    std::vector<int> vec; 
    
    std::cout << "Initial capacity: " << vec.capacity() << std::endl;
    
    for (int i = 0; i < 10; ++i) 
    {
        vec.push_back(i); //vector capacity automatically grows
        std::cout << "Size: " << vec.size() << ", Capacity: " << vec.capacity() << std::endl;
    }
    
    return 0;
}

 

elements를 저장할 공간이 없을경우... -> 동적배열이 생성 (dynamic array) -> 모든 elements가 새로운 배열에 복사됨

 

Inserting Elements

iterator insert(const_iterator position, cosnt value_type& val);
		//넣고싶은 position, 넣고싶은 single element
iterator insert(const_iterator position, size_type n, const value_type& val);
		//넣고싶은 position, 넣고싶은 횟수, 넣고싶은 single element
iterator insert(const_iterator position, initializer_list<value_type> il);
		//넣고싶은 position, 넣고싶은 initializer list object

vector<int> vector1 = {10, 20, 30, 40};
vector1.insert(vector1.begin() + 2, 100); // 10 20 100 30 40
vector1.insert(vector1.begin() + 2, 3, 100); // 10 20 100 100 100 30 40 
vector1.insert(vector1.begin() + 2, {1, 2, 3, 4}); // 10 20 1 2 3 4 30 40

 

Subscript Operator 첨자 연산자 

vector<int> vector1 = {1, 2, 3, 4, 5};
vector1[2] = 999;

//vector1 is 1 2 999 4 5

 

Other STL vector functions

front() / back() / begin() / end() / erase() / pop_back() 

vector<string> names = { "Ted", "Sue", "Bob", "Jill"};
// Return the first element.(/= .begin())
cout << names.front() << "\n"; //Ted
// Return the last element.(/= .end())
cout << names.back() << "\n"; //Jill 
// Delete "Bob".
names.erase(names.begin() + 2); // vector is: Ted Sue Jill
// Delete the last element.(which is Jill)
names.pop_back(); // vector is: Ted Sue

---

list container

• implemented as a doubly-linked list : 이중연결리스트로 구현됨. 이는 연속적인 메모리 공간에 요소를 저장하지않는다는 말과 같음.. ->  리스트의 각요소는 다음 요소를 가리키는 포인터를 포함하고 있으므로, 요소를 추가하거나 제거할때 메모리를 재할당 할 필요가 없음. 따라서 리스트는 동적으로 크기를 조정하는데에 효율적이다. 
• has no random access (임의적으로 접근 불가능!!!!) -> ++iter, --iter 은 가능하지만 (iter +2) 는 불가능!!!!
• 첨자 연산자 사용불가 ! (subscript operator) 
• slist(singly-linked-list) 도 존재함 ㅎ

---

기본 생성자 default constructor

* By default, an empty list will be created of size 0.

list<int> list1;
list1.push_back(10);
list1.push_back(80);
list1.push_back(54); // list is now: 10 80 54
list1.push_front(3);
list1.push_front(9); // list is now: 9 3 54 80 10

복사 생성자 copy constructor

list<int> list2(list1); //list1이 그대로 복사된 list2생성
list<int> list3 = list1;

초기화 리스트 생성자 initializer list constructor

list<int> list4{ 130, 750, 259, 1234};
list<int> list5 = {234, 54, 5634, 65};
// set size and capacity right away + with specific elements!!

 

범위 생성자 Range constructor

list<int> list5 {10, 20, 30, 40};
list<int>::iterator iter = list5.begin();
++iter;
++iter;

list<int> list6(iter, list5.end());

//list6 contains : 30 40 
//list cannot use list5.begin() + 2!!!! 임의적 접근 불가능!

 

For loop to Increment

list<int> aList = { 1, 2, 3, 4, 5, 6, 7, 8 };
auto iter = aList.begin(); // iter은 1
for (int i = 0; i < 6; ++i) // 총 6 번 반복 
	++iter; // 1에서 시작해서 2 3 4 5 6 7 (6번반복) 
cout << *iter; // will print 7

 

Transferring elements

list::splice()

void splice(const_iterator position, list& x);
void splice(const_iterator position, list& x, const_iterator first, const_iterator last);

list<int> nums1 = { 5, 4, 3, 2, 1};
list<int> nums2 = { 77, 66, 55}; 
nums1.splice(++nums1.begin(), nums2); //nums1 is : 5 77 66 55 4 3 2 1 , num2 is empty
nums1.splice(nums1.begin(), ++nums2.begin(), nums2.end()); //nums1 is : 66 55 5 4 3 2 1 , nums2 is 77

Merging lists

void sort();
void merge(list& x);

list<int> nums5 = { 1, 7, 3, 4, 5};
list<int> nums6 = { 999, 888, 777};
list<int> nums7 = { 89, 23, 874};
nums5.sort(); // nums5 is : 1 3 4 5 7
nums6.sort(); // nums6 is : 777 888 999
nums5.merge(nums6) // nums5 is : 1 3 4 5 7 777 888 999, num6 is empty

//what happens if we do not sort the list? 
nums7.merge(nums6); // nums7 is : ...졸라 복잡해짐. 그냥 sort하자 ㅎ

Other STL list functions

push_front() / pop_front() / reverse() / sort() / remove() 

list<int> scores = { 24, 76, 99, 87 };
// Add a new element to the front.
scores.push_front(75); // list is: 75 24 76 99 87
// Delete the front element.
scores.pop_front(); // list is: 24 76 99 87
// Reverse the order of elements.
scores.reverse(); // list is: 87 99 76 24
// Sort the list.
scores.sort(); // list is: 24 76 87 99
// Delete a given element in the list.
scores.remove(87); // list is: 24 76 99

 

---

Returning Iterators

std::vector::erase
iterator erase(const_iterator position);

vector<int> v = {1, 4, 5, 2, 3};
v.erase(v.begin() + 3;); // v is : 1 4 5 3

vector<int> v = {1, 4, 5, 2, 3};
vector<int>::iterator iter = v.erase(v.begin() + 3); 
	/* 먼저 v.begin() + 3을 통해 인덱스가 3인 요소에 대한 반복자를 얻고, 
   	 v.erase() 함수를 사용하여 해당 요소를 삭제합니다. 
   	 이 반복자는 삭제된 요소의 위치를 가리키게 됩니다. */
v.insert(iter, 100); // v is : 1 4 5 100 3

 

Q. iter이 인덱스가 3인 요소에 대한 반복자를 얻고, 그걸 삭제함. 그럼 위치값(position)을 기록하고, 그  value는nullptr 이 되는건가?? 

A. 

 

끗 ! 어렵다 ..