Lập trình C/C++

Vector trong C++

Posted on by Đỗ Thành
10
Th1
View: 68

Giới thiệu về std::vector trong C++

std::vector là một trong những container phổ biến nhất của thư viện chuẩn C++ (<vector>). Nó là một mảng động có khả năng tự động thay đổi kích thước. Dưới đây là các đặc điểm chính của std::vector:

  • Kích thước của std::vector có thể tự động tăng hoặc giảm.
  • Các phần tử được lưu trữ liên tiếp trong bộ nhớ, giống như mảng thông thường.
  • Hỗ trợ truy cập chỉ mục nhanh (O(1)).
  • Cung cấp nhiều phương thức tiện ích để thao tác với dữ liệu.

Cách sử dụng cơ bản

Để sử dụng std::vector, bạn cần bao gồm thư viện:

#include <vector>
#include <iostream>

int main() {
    std::vector<int> vec;  // Tạo một vector lưu các số nguyên
    vec.push_back(10);     // Thêm phần tử vào cuối
    vec.push_back(20);
    vec.push_back(30);

    // In ra các phần tử
    for (int val : vec) {
        std::cout << val << " ";
    }
    return 0;
}

Các phương thức chính của std::vector

Phương thứcMô tả
push_back(value)Thêm phần tử value vào cuối vector.
pop_back()Xóa phần tử cuối cùng.
size()Trả về số lượng phần tử trong vector.
capacity()Trả về dung lượng hiện tại của vector.
empty()Kiểm tra vector có rỗng hay không.
resize(new_size)Thay đổi kích thước vector. Nếu tăng kích thước, các phần tử mới sẽ được gán giá trị mặc định.
clear()Xóa tất cả các phần tử trong vector.
insert(pos, value)Chèn phần tử value vào vị trí pos.
erase(pos)Xóa phần tử tại vị trí pos.
begin() và end()Trả về iterator đầu và iterator cuối của vector.
front() và back()Truy cập phần tử đầu tiên và phần tử cuối cùng.
at(index)Truy cập phần tử tại vị trí index (có kiểm tra phạm vi).

Khởi tạo std::vector

Dưới đây là một số cách khởi tạo std::vector:

#include <vector>

int main() {
    std::vector<int> vec1; // Vector rỗng
    std::vector<int> vec2(5); // Vector với 5 phần tử mặc định (0)
    std::vector<int> vec3(5, 10); // Vector với 5 phần tử, mỗi phần tử có giá trị 10
    std::vector<int> vec4{1, 2, 3, 4, 5}; // Khởi tạo từ danh sách phần tử
    std::vector<int> vec5(vec4); // Sao chép từ vector khác
    return 0;
}

Duyệt qua std::vector

  1. Dùng vòng lặp for thông thường
for (size_t i = 0; i < vec.size(); i++) {
    std::cout << vec[i] << " ";
}

Dùng range-based for

for (int val : vec) {
    std::cout << val << " ";
}

Dùng iterator

for (auto it = vec.begin(); it != vec.end(); ++it) {
    std::cout << *it << " ";
}

Lợi ích và hạn chế của std::vector

Lợi ích:

  • Dễ sử dụng và linh hoạt.
  • Hỗ trợ quản lý bộ nhớ tự động.
  • Cung cấp nhiều phương thức mạnh mẽ.

Hạn chế:

  • Hiệu suất có thể giảm khi thêm/xóa nhiều phần tử ở đầu hoặc giữa vector (do phải dời dữ liệu).
  • Sử dụng bộ nhớ không hiệu quả nếu dung lượng lớn nhưng chỉ sử dụng ít phần tử.

Một số ví dụ

Xóa các phần tử thỏa điều kiện

#include <vector>
#include <algorithm>

int main() {
    std::vector<int> vec{1, 2, 3, 4, 5, 6};
    vec.erase(std::remove_if(vec.begin(), vec.end(),
                             [](int x) { return x % 2 == 0; }),
              vec.end());
    for (int val : vec) {
        std::cout << val << " ";
    }
    return 0;
}

Sắp xếp vector

#include <vector>
#include <algorithm>

int main() {
    std::vector<int> vec{5, 3, 8, 1, 4};
    std::sort(vec.begin(), vec.end()); // Sắp xếp tăng dần
    return 0;
}

Một số ví dụ

Tính tổng các phần tử lớn hơn một giá trị cho trước

#include <iostream>
#include <vector>

int main() {
    std::vector<int> vec{1, 5, 8, 12, 3, 7};
    int X = 6;

    int sum = 0;
    for (int val : vec) {
        if (val > X) {
            sum += val;
        }
    }
    std::cout << "Tổng các phần tử lớn hơn " << X << " là: " << sum << std::endl;
    return 0;
}

Đảo ngược vector

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> vec{1, 2, 3, 4, 5};
    std::reverse(vec.begin(), vec.end());

    for (int val : vec) {
        std::cout << val << " ";
    }
    return 0;
}

Xóa các phần tử trùng lặp

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> vec{1, 2, 2, 3, 4, 4, 5};
    std::sort(vec.begin(), vec.end());
    vec.erase(std::unique(vec.begin(), vec.end()), vec.end());

    for (int val : vec) {
        std::cout << val << " ";
    }
    return 0;
}

Chèn phần tử vào vị trí thích hợp trong vector đã sắp xếp

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> vec{1, 3, 4, 7, 9};
    int X = 5;

    auto pos = std::lower_bound(vec.begin(), vec.end(), X);
    vec.insert(pos, X);

    for (int val : vec) {
        std::cout << val << " ";
    }
    return 0;
}

Xóa các phần tử thỏa mãn điều kiện

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> vec{1, 2, 3, 4, 5, 6};
    vec.erase(std::remove_if(vec.begin(), vec.end(), [](int x) { return x % 2 == 0; }), vec.end());

    for (int val : vec) {
        std::cout << val << " ";
    }
    return 0;
}

Tìm phần tử có tần suất xuất hiện nhiều nhất

#include <iostream>
#include <vector>
#include <map>

int main() {
    std::vector<int> vec{1, 2, 2, 3, 3, 3, 4};
    std::map<int, int> freq;

    for (int val : vec) {
        freq[val]++;
    }

    int max_freq = 0;
    int most_common = 0;
    for (auto& [key, value] : freq) {
        if (value > max_freq) {
            max_freq = value;
            most_common = key;
        }
    }

    std::cout << "Phần tử xuất hiện nhiều nhất: " << most_common 
              << " (tần suất: " << max_freq << ")" << std::endl;
    return 0;
}

Gộp hai vector đã sắp xếp thành một vector sắp xếp

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> vec1{1, 3, 5};
    std::vector<int> vec2{2, 4, 6};
    std::vector<int> result(vec1.size() + vec2.size());

    std::merge(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), result.begin());

    for (int val : result) {
        std::cout << val << " ";
    }
    return 0;
}

Tìm tập hợp giao của hai vector

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> vec1{1, 2, 3, 4};
    std::vector<int> vec2{3, 4, 5, 6};
    std::vector<int> result;

    std::sort(vec1.begin(), vec1.end());
    std::sort(vec2.begin(), vec2.end());
    std::set_intersection(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), std::back_inserter(result));

    for (int val : result) {
        std::cout << val << " ";
    }
    return 0;
}

Dịch vòng các phần tử trong vector

#include <iostream>
#include <vector>
#include <algorithm>

void rotate_right(std::vector<int>& vec, int k) {
    k = k % vec.size(); // Dịch vòng
    std::rotate(vec.rbegin(), vec.rbegin() + k, vec.rend());
}

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

    for (int val : vec) {
        std::cout << val << " ";
    }
    return 0;
}

Phân loại vector thành hai vector con

#include <iostream>
#include <vector>

int main() {
    std::vector<int> vec{1, 2, 3, 4, 5, 6};
    std::vector<int> even, odd;

    for (int val : vec) {
        if (val % 2 == 0) {
            even.push_back(val);
        } else {
            odd.push_back(val);
        }
    }

    std::cout << "Vector số chẵn: ";
    for (int val : even) {
        std::cout << val << " ";
    }
    std::cout << "\nVector số lẻ: ";
    for (int val : odd) {
        std::cout << val << " ";
    }
    return 0;
}
Đỗ Thành