원소 삽입: insert 함수

https://www.cplusplus.com/reference/vector/vector/insert/

1. single element

   iterator insert (iterator position, const value_type& val);
   → position에 val을 삽입한 뒤에 해당 위치를 iterator로 반환한다.

2. fill

   void insert (iterator position, size_type n, const value_type& val);
   → position에 n개의 val를 삽입한다.

3. range

   template
   void insert (iterator position, InputIterator first, InputIterator last);
   → [first, lase) 범위의 원소들에 대한 복사본이 position에 삽입된다.

// inserting into a vector
#include <iostream>
#include <vector>
using namespace std;

int main()
{
    vector<int> v(3, 10); // 10 10 10
    vector<int>::iterator it;

    it = v.begin();

    // v의 시작 부분에 20 삽입
    it = v.insert(it, 20); // 20 10 10 10

    // v의 시작 부분에 30을 2번 삽입
    v.insert(it, 2, 30); // 30 30 20 10 10 10

    // "it" no longer valid, get a new one:
    it = v.begin();

    vector<int> v2(2, 40); // 40 40

    // v의 인덱스가 2인 위치에 v2의 전체 원소를 삽입
    v.insert(it + 2, v2.begin(), v2.end()); 
    // 30 30 '40 40' 20 10 10 10 

    int arr[] = { 51, 52, 53 };

    // v의 시작 부분에 arr의 전체 원소를 삽입
    v.insert(v.begin(), arr, arr + 3); 
    // '51 52 53' 30 30 40 40 20 10 10 10 

    cout << "v contains: ";
    for (it = v.begin(); it < v.end(); it++)
        cout << *it << " ";
    cout << "\n";

    return 0;
}

v contains: 51 52 53 30 30 40 40 20 10 10 10

원소 삭제: erase 함수

https://www.cplusplus.com/reference/vector/vector/erase/

1. position에 있는 원소 삭제 후, 해당 위치를 iterator로 반환

iterator erase (iterator position);

2. [first, last) 범위의 원소들 삭제 후, 마지막으로 삭제된 원소의 바로 다음 위치를 iterator로 반환

iterator erase (iterator first, iterator last);

// erasing from vector
#include <iostream>
#include <vector>
using namespace std;

int main()
{
    vector<int> v;

    // set some values (from 1 to 10)
    for (int i = 1; i <= 10; i++) 
        v.push_back(i);

    // erase the 6th element
    v.erase(v.begin() + 5);

    // erase the first 3 elements:
    v.erase(v.begin(), v.begin() + 3);

    cout << "v contains:";
    for (int i = 0; i < v.size(); i++)
        cout << ' ' << v[i];
    cout << '\n';

    return 0;
}

v contains: 4 5 7 8 9 10

cf) 벡터는 내부적으로 배열로 구현되어 있기 때문에, 마지막이 아닌 위치에 있는 요소를 삽입/삭제할 때 컨테이너의 모든 요소를 새로운 위치로 재배치 해야 한다. 즉, 한칸씩 앞으로 당기거나 뒤로 밀어야 하기 때문에 O(N)의 시간이 걸린다. 반면에, 리스트는 노드가 가리키는 링크만 바꿔주면 되기 때문에 O(1)의 시간만 걸린다. 따라서, 특정 위치에 원소를 삽입/삭제하는 연산은 배열보다 리스트가 더 효율적이다. 그렇지만, 리스트는 '데이터 필드'뿐만 아니라 다음 노드를 가리키는 '링크 필드'도 필요하기 때문에 배열보다 더 많은 메모리 공간을 사용한다.