Vector

Vector คืออะไร

ในภาษา C++ vector คือ Array พิเศษที่อยู่ใน Standard Template Library (STL) มันต่างจาก Array ธรรมดาตรงที่ vector จะเปลี่ยนขนาดได้เอง เพิ่มหรือลบข้อมูลได้ตลอดเวลา จึงเป็นโครงสร้างข้อมูลที่ได้รับความนิยมในการใช้เก็บข้อมูลที่ต่อเนื่องกัน (เช่นใน LeetCode ก็ใช้ vector ในการรับข้อมูลประเภท list)

Key Features หลัก std::vector

• Dynamic Size สามารถเปลี่ยนขนาดเพิ่มหรือลดจำนวนข้อมูลได้เอง
• Contiguous Storage ข้อมูลภายใน vector ถูกเก็บในหน่วยความจำที่เรียงต่อกัน เหมือนกับ array ทำให้เข้าถึงข้อมูลได้อย่างรวดเร็ว และใช้ pointer ในการทำงานได้
• Element Access เข้าถึงข้อมูลแต่ละชิ้นผ่านตัวย่อที่เหมือน array (index) หรือผ่าน function at() ซึ่ง function นี้จะตรวจสอบเพื่อป้องกันกรณีเข้าถึงข้อมูลเกินขนาดของ Vector ไป (index out of range)
• Memory Management Vector จัดสรรหน่วยความจำให้เองเมื่อต้องเพิ่มหรือลบข้อมูล ซึ่งทำให้ง่ายต่อการทำงานกับ Array ที่ขนาดเปลี่ยนแปลงตลอดเวลา (ไม่ต้องมานั่งจัดการ memory เอง)
• Utility Functions มี function ที่ช่วยอำนวยความสะดวก Vector case ต่างๆ เช่น ตรวจสอบขนาด (size()) ดูว่าว่างหรือไม่ (empty()) ลบข้อมูลทั้งหมด (clear()) เป็นต้น

นี่คือตัวอย่างการใช้งาน Vector

#include <iostream>
#include <vector>
using namespace std;

int main() {
  // Create a vector of integers
  vector<int> vec;

  // Add elements to the vector
  vec.push_back(10);
  vec.push_back(20);
  vec.push_back(30);

  // Access and print elements using a range-based for loop
  for (int i = 0; i < vec.size(); i++) {
    cout << vec[i] << " ";
  }
  cout << endl;

  // Remove the last element
  vec.pop_back();

  // Access an element by index
  cout << "Element at index 1: " << vec[1] << endl;

  // Get the size of the vector
  cout << "Size of vector: " << vec.size() << endl;

  return 0;
}

ผลลัพธ์

10 20 30 
Element at index 1: 20
Size of vector: 2

จาก code ด้านบน

• vector<int> vec; เป็นการสร้าง vector ชื่อ vec ไว้เก็บข้อมูลเลขจำนวนเต็มชนิด (int) ในตอนแรก vector นี้จะว่างเปล่า
• push_back คือฟังก์ชันสำหรับเพิ่มข้อมูลไปต่อที่ท้ายของ vector ในที่นี้เราดันเลข 10 20 30 ทีละอัน (ตามลำดับ)
• .size() เป็นฟังก์ชันดึงจำนวนสมาชิกใน vector มา ส่วน for loop ธรรมดาก็เพื่อวน loop ทีละตัวผ่านแต่ละสมาชิกใน vector
• ตัว [] ใช้ระบุตำแหน่งข้อมูล เช่น vec[1] ก็คือข้อมูลลำดับที่ 2 นั่นเอง ในบรรทัดนี้ for loop พิมพ์ 10 20 30 ออกมา เนื่องจากเราใส่ข้อมูลทั้ง 3 นี้เข้าไป
• .pop_back() เป็น function สำหรับเอาข้อมูลที่ถูกใส่ไว้ท้ายสุดออก หลังจากบรรทัดนี้ vector จะเหลือข้อมูลแค่ 10 และ 20 (และส่งผลทำให้ size เหลือ 2 ในตอนสุดท้ายออกมา)

Vector operation

นี่คือ operation ที่มีการใช้บ่อยๆใน Vector

1. Initialization

std::vector<int> vec1; // Empty vector of integers
std::vector<int> vec2 = {1, 2, 3, 4, 5}; // Initialization with a list
std::vector<int> vec3(5, 10); // Vector of size 5, each element initialized to 10

2. Adding Elements

vec1.push_back(6); // Adds an element to the end

3. Accessing Elements

int firstElement = vec2[0]; // Using subscript operator, no bounds checking
int secondElement = vec2.at(1); // Using .at() with bounds checking

4. Modifying Elements

vec2[0] = 10; // Modify first element
vec2.at(1) = 20; // Modify second element using .at()

5. Removing Elements

vec2.pop_back(); // Removes the last element

6. Size and Capacity

size_t numElements = vec2.size(); // Number of elements
size_t capacity = vec2.capacity(); // Capacity of the vector

7. Checking if Empty

bool isEmpty = vec1.empty(); // Returns true if the vector is empty

8. Clearing All Elements

vec2.clear(); // Removes all elements, size becomes 0

9. Iterators

auto it = vec2.begin(); // Iterator to the first element
vec2.insert(it, 15); // Insert 15 at the beginning
vec2.erase(vec2.begin()); // Erase the first element

10. Resize / Reserve

vec3.resize(10); // Changes the size to 10, adds elements if necessary
vec1.reserve(100); // Reserves space for at least 100 elements

11. Accessing the First and Last Elements

int first = vec2.front(); // First element
int last = vec2.back(); // Last element

Vector และ pointer

ใน C++ pointers และ vector มีความสัมพันธ์กันอยู่หลายจุด ซึ่งสะท้อนถึงความยืดหยุ่นและประสิทธิภาพที่ภาษา C++ มอบให้ในการจัดการกับหน่วยความจำและ Array ที่มีขนาดที่เปลี่ยนแปลงได้

เข้าถึงข้อมูล Vector: สามารถใช้ตัวชี้ (pointer) เพื่อเข้าถึงหรือเปลี่ยนแปลงข้อมูลใน vector ได้โดยตรง ฟังก์ชัน .data() ของ object vector จะตอบกลับค่าเป็นที่อยู่ของข้อมูลตัวแรกใน vector นั้น ทำให้เราทำงานอย่างเดียวกันกับที่ใช้ pointer เล่นงานอาร์เรย์ปกติได้

Iterators และ Pointers: หลายๆ ครั้ง iterator ของ vector ก็ทำหน้าที่คล้ายตัวชี้ โดยเฉพาะ vector จะเป็นประเภทที่เรียกว่า random access iterator ซึ่งจะยิงเพิ่ม ลดตัว iterator ด้วย ++ -- แล้วใช้ฟังก์ชัน dereference (*) เหมือน pointer เพื่อเข้าถึงข้อมูลใน vector เลย

ส่ง vectors และ pointers: สามารถส่ง vector ให้กับฟังก์ชันอื่นๆ เพื่อทำงานกับกลุ่มข้อมูลในลักษณะอัตโนมัติ และยังสามารถส่งตัวชี้ (pointer) เพื่อให้แก้ไขข้อมูลตัวใดตัวหนึ่งหรือแก้ไขอาร์เรย์โดยตรงก็ได้ แต่โดยทั่วไปจะนิยมใช้ vector มากกว่าในการส่งกลุ่มข้อมูลเพราะปลอดภัยกว่าเวลาใช้ pointer แบบดิบๆ (raw pointer arrays) นั่นเอง

Direct Memory Access

เข้าถึงข้อมูล Vector สามารถใช้ pointer เพื่อเข้าถึงหรือเปลี่ยนแปลงข้อมูลใน vector ได้โดยตรง function .data() ของ object vector จะตอบกลับค่าเป็นที่อยู่ของข้อมูลตัวแรกใน vector นั้น ทำให้เราทำงานด้วยวิธีเดียวกันกับที่ใช้ pointer ใน Array ปกติได้เลย

std::vector<int> vec = {1, 2, 3};
int* ptr = vec.data();
ptr[0] = 10; // Modifies the first element of vec

Iterators as Pointers

Iterators ในภาษา C++ เป็นเหมือน pointers แบบพิเศษ ซึ่งเราสามารถใช้กับโครงสร้างข้อมูลต่างๆ ที่มีอยู่ใน Standard Templates Library (STL) ได้ เช่น vector เป็นต้น (จริงๆมีอีกหลายตัว แต่เดี๋ยวเราจะยกตัวอย่างในอนาคตเพิ่มเติมกันอีกที)

จุดแข็งของ iterator อยู่ที่ทำให้เราควบคุมข้อมูลใน data structure ต่างๆได้ โดยอาศัยการ "อ้างอิงตำแหน่ง (reference)" แต่ในกรณีเช่น vector เราก็ยังใช้ iterators ได้คล้ายตัวชี้ในการวน loop ไปทีละตัวได้เช่นกัน

ดังตัวอย่างนี้

#include <iostream>
#include <vector>
using namespace std;

int main() {
  vector<int> vec = {1, 2, 3, 4, 5};

  // Iterator initialization, similar to obtaining a pointer to the first
  // element
  vector<int>::iterator it = vec.begin();

  // Dereferencing an iterator to access the first element, similar to using a
  // pointer
  cout << "First element (using iterator): " << *it << endl;

  // Modify the first element through the iterator
  *it = 10;
  cout << "Modified first element: " << vec[0] << endl;

  // Using iterators in a loop, similar to pointer arithmetic
  cout << "Elements in vector: ";
  for (vector<int>::iterator iter = vec.begin(); iter != vec.end(); ++iter) {
    cout << *iter << " "; // Dereference iterator to access element
  }
  cout << endl;

  // Using iterators to insert elements at a specific position
  it = vec.begin() + 2; // Points to the third element
  vec.insert(it, 20);   // Insert '20' before the third element

  // Using iterators to erase elements
  it = vec.begin(); // Reset iterator to the first element
  vec.erase(it);    // Erase the first element

  // Print the modified vector
  cout << "Modified vector: ";
  for (int elem : vec) {
    cout << elem << " ";
  }
  cout << endl;

  return 0;
}

ผลลัพธ์

First element (using iterator): 1
Modified first element: 10
Elements in vector: 10 2 3 4 5 
Modified vector: 2 20 3 4 5

อธิบายจาก code ด้านบน

• ตัว *it (iterator) ถูกใช้งาน โดยสั่งให้มันชี้ไปยังข้อมูลอันแรกของ vector ด้วยฟังก์ชัน vec.begin() ซึ่งจริงๆ ก็คล้ายการเอาที่อยู่ของข้อมูลตัวแรกใน Array มาเก็บใส่ให้ pointer
• ใช้ iterator เป็นตัววิ่งเข้าไปแก้ไขหรือเข้าถึงข้อมูลทีละตัวได้ ซึ่งเงื่อนไขของการวน loop ที่ใช้จะเป็น iter != vec.end() โดยจะบอกว่าเราทำวนลูปต่อไปเรื่อยๆ จนกว่า iter จะชี้ไปที่ตำแหน่งสุดท้าย ซึ่งก็น่าจะคล้ายกับเวลาเขียนเงื่อนไขวน loop สำหรับ pointer ว่าอย่าให้เกินความยาวของ Array นั่นเอง
• การใส่ (insert) หรือลบ (erase) ข้อมูลสามารถใช้ผ่าน iterators ได้เลย ฟังก์ชันทั้งสองจะสร้างผลลัพธ์ตรงตำแหน่งที่ iter ชี้ไปโดยตรงได้

Function Arguments

เราสามารถส่ง vector ให้กับ function อื่นๆ เพื่อทำงานกับกลุ่มข้อมูลได้ และยังสามารถส่ง pointer เพื่อให้แก้ไขข้อมูลตัวใดตัวหนึ่งหรือแก้ไข Array โดยตรงก็ได้ แต่โดยทั่วไปจะนิยมใช้ vector มากกว่าสำหรับการส่งกลุ่มข้อมูล เพราะปลอดภัยกว่าเวลาใช้กับ raw pointer arrays นั่นเอง

ตัวอย่างนี้จะมี function ที่ทำงานร่วมกับ vector โดยจะแก้ไขหรือเติมข้อมูลเข้าไปใน vector ผ่านวิธีที่เรียกว่า pointer arithmetic (หรือก็คือการบวกลบตัวชี้ เพื่อเปลี่ยนตำแหน่งที่ข้อมูลที่ตัวชี้นั้นชี้ไป) แสดงให้เห็นว่าสามารถรวมการใช้ตัวชี้ (pointer) และ vector เพื่อให้ผลลัพธ์ที่เราต้องการออกมาได้

#include <iostream>
#include <vector>
using namespace std;

// Function to add elements to the vector starting from its current size
void addElements(vector<int> &vec, int numElementsToAdd) {
  int initialSize = vec.size();
  // Resize the vector to accommodate the new elements
  vec.resize(initialSize + numElementsToAdd);

  // Get a pointer to the first element to be added
  int *ptr = vec.data() + initialSize;

  // Use the pointer to add new elements
  for (int i = 0; i < numElementsToAdd; ++i) {
    *(ptr + i) = initialSize + i; // Example value: start from the initial size
  }
}

// Function to print the elements of the vector
void printVector(const vector<int> &vec) {
  for (int i = 0; i < vec.size(); ++i) {
    cout << vec[i] << " ";
  }
  cout << endl;
}

int main() {
  vector<int> myVector;

  // Initially add some elements
  for (int i = 0; i < 5; ++i) {
    myVector.push_back(i);
  }

  cout << "Original vector: ";
  printVector(myVector);

  // Add more elements using the addElements function
  addElements(myVector, 5); // Add 5 more elements

  cout << "After adding elements: ";
  printVector(myVector);

  return 0;
}

จาก code ด้านบน

• ที่ main() เริ่มด้วยประกาศ vector ที่เก็บข้อมูลเลขจำนวนเต็ม (int) 5 ตัวตั้งแต่ 0 - 4
• จากนั้นจึงเรียกใช้ addElements เพื่อเพิ่มข้อมูลใน vector เข้าไปอีก 5 ตัว ซึ่งข้อมูลใหม่จะใส่ต่อจากอันสุดท้ายที่ใส่ตอนแรก เป็นการใช้ตัวชี้ pointer arithmetic ในการเพิ่มจำนวนสมาชิกใน vector ได้
• addElements ****function นี้เริ่มด้วยการใช้ .resize() เพิ่มขนาด vector ให้มีที่ว่างพอยัดข้อมูลที่เข้ามา จากนั้นคำนวณหาที่อยู่ ที่จะต้องเพิ่มข้อมูลใหม่โดยต้องเพิ่มจำนวน initial size ของ vector ลงในตัวชี้ (pointer) ที่ดึงมาจาก vec.data() เพราะข้อมูลใหม่อยู่ต่อจากของเดิมที่เคยจัดสรรเอาไว้ใน vec จากนั้นสามารถใช้ pointer arithmetic ใส่ข้อมูลที่เข้ามาต่อกัน
• printVector function นี้วน loop ทีละสมาชิกใน vector และสั่งพิมพ์ออกหน้าจอ เพื่อแสดงว่า vector ถูกขยายและมีการใส่ข้อมูลไปใหม่

Vector และ Loop

อีกเรื่องที่น่าสนใจสำหรับ Vector คือ วิธีการ loop นั้นนอกเหนือจากท่า Array ที่ใช้วน Loop ตามปกติ ยังสามารถใช้ library หรือท่าของ Standard สมัยใหม่ในการวน loop ออกมาได้ โดยท่าที่สามารถทำได้มีดังนี้

1. Classic For Loop

ท่ามาตรฐานท่าเดียวกันกับ Array โดยเป็นท่าที่ใช้ vec.size() มากำกับขนาดของการวน loop

vector<int> vec = {1, 2, 3, 4, 5};
for (size_t i = 0; i < vec.size(); ++i) {
  cout << vec[i] << " ";
}

2. Range-based For Loop (C++11 and later)

ท่าที่มีความยืดหยุ่นสูงกว่า ทำงานได้กับ data structure ชนิดต่างๆ ไม่จำเป็นว่าจะต้องเป็น vector สามารถใส่ค่าแบบโดยตรงจาก value ที่ออกมาในลูปไปในตัวแปรข้างนอกได้

vector<int> vec = {1, 2, 3, 4, 5};
for (int elem : vec) {
  cout << elem << " ";
}

3. Iterator Loop

เป็นการใช้ตัวแปรอิงกับ iterators (เหมือนตัวอย่างด้านบน pointer ก่อนหน้า) และทำการเลื่อน pointer ไปจนจบ Vector

vector<int> vec = {1, 2, 3, 4, 5};
// ฉบับ for loop
for (vector<int>::iterator it = vec.begin(); it != vec.end(); ++it) {
    cout << *it << " ";
}

// ฉบับ while loop
std::vector<int>::iterator it = vec.begin();
while (it != vec.end()) {
    std::cout << *it << " ";
    ++it;
}

// ฉบับตัวแปรแบบ read-only
for (vector<int>::const_iterator it = vec.cbegin(); it != vec.cend(); ++it) {
    cout << *it << " ";
}

4. Reverse Loop

ท่าสำหรับ กรณีต้องการวน loop เข้าถึงข้อมูลโดยเรียงจากท้าย vector ไปที่ข้อมูลตัวแรก เหมาะสมเมื่อต้องอ่านข้อมูลตามลำดับย้อนหลัง โดยไม่จำเป็นต้องใช้ท่าดึงค่าตาม index และวน loop ตาม index ได้

for (vector<int>::reverse_iterator it = vec.rbegin(); it != vec.rend(); ++it) {
    cout << *it << " ";
}

และนี่ก็คือ Vector และตัวอย่างการใช้งาน Vector ในแต่ละเคส