cách nhanh để triển khai pop_front thành std :: vector

Question

Tôi đang sử dụng một số lớp và một số phương thức tiện ích sử dụng std :: vector.

Bây giờ tôi cần phải sử dụng từng khung một phương thức pop_front - push_back trên một trong các lớp đó (nhưng chúng đều được liên kết và làm việc cùng nhau vì vậy tôi không thể thay đổi chỉ một).

Hầu hết các hoạt động được lặp qua tất cả các hoạt động của phần tử và push_back, vì vậy những gì tôi nên làm cho công việc tốt nhất là: dĩa kho lưu trữ của các lớp và tiện ích đó, lấy mẫu mọi thứ và sử dụng deque hoặc list.

Nhưng điều này có nghĩa là rất nhiều mã viết lại và rất nhiều thử nghiệm mà sẽ làm cho tôi bỏ lỡ thời hạn.

Vì vậy, tôi cần lời khuyên để viết một pop_front hiệu quả cho một vector kích thước tĩnh (kích thước sẽ không thay đổi).

Tôi đã tìm thấy một cách here:

template<typename T> 
void pop_front(std::vector<T>& vec) 
{ 
    vec.front() = vec.back(); 
    vec.pop_back(); 
    vec.front() = vec.back(); // but should this work? 
} 

Và ý tưởng khác nên là:

template<typename T> 
void pop_front(std::vector<T>& vec, already_allocated_vector vec1) 
{ 
    vec1.clear(); 
    copy(vec.begin(), vec.end()-1, vec1.begin()); 
    copy(vec1.begin(), vec1.end(), vec.begin()); 
} 

là gì nhanh hơn của hai giải pháp này? Bất kỳ giải pháp nào khác?

Answer 1

Tôi mong chờ:

template<typename T> 
void pop_front(std::vector<T>& vec) 
{ 
    assert(!vec.empty()); 
    vec.front() = std::move(vec.back()); 
    vec.pop_back(); 
} 

là cách hiệu quả nhất để làm điều này, nhưng nó không duy trì trật tự của các yếu tố trong vector.

Nếu bạn cần phải duy trì trật tự của các yếu tố còn lại trong vec, bạn có thể làm:

template<typename T> 
void pop_front(std::vector<T>& vec) 
{ 
    assert(!vec.empty()); 
    vec.erase(vec.begin()); 
} 

này sẽ có thời gian tuyến tính về số lượng các yếu tố trong vec, nhưng nó là tốt nhất bạn có thể làm mà không thay đổi cấu trúc dữ liệu của bạn.

Không có chức năng nào trong số này sẽ duy trì vector ở kích thước không đổi, vì hoạt động pop_front sẽ theo định nghĩa xóa phần tử khỏi vùng chứa.

Answer 2

Kể từ pop_front() chỉ xóa phần tử đầu tiên, việc thực hiện trực tiếp là thế này:

template <typename V> 
void pop_front(V & v) 
{ 
    assert(!v.empty()); 
    v.erase(v.begin()); 
} 

Đừng lo lắng về tốc độ cho bây giờ. Nếu bạn muốn quay lại và tối ưu hóa mã, hãy yêu cầu thời gian dự án chuyên dụng.

Answer 3

Bạn cũng có thể IgushArray (https://github.com/igushev/IgushArray) giống như một mảng có hoạt động truy cập liên tục thời gian nhanh, nhưng thao tác chèn/xóa chỉ mất thời gian O (N^1/2). Vì vậy, trong trường hợp của bạn chèn vào đầu sẽ rất hiệu quả ở đây. Hãy cẩn thận, cấu trúc rất nhạy cảm với dự trữ().

template <class T> 
void pop_front(IgushArray<T>& v) 
{ 
    if (!v.empty()) 
    v.erase(v.begin()); 
} 

Trong tùy chọn đầu tiên bạn viết, bạn vi phạm thứ tự các phần tử. Nó là một vấn đề?

Nếu có, hãy sử dụng biến thể tôi đã viết.

Nếu không và thứ tự các phần tử không quan trọng chút nào, có thể tốt hơn nên sử dụng std :: set or std :: multiset.

Answer 4

nếu bạn chỉ cố gắng để xóa phần tử đầu tiên sau đó trong chức năng sử dụng:

if (my_vector.size()){ //check if there any elements in the vector array 
    my_vector.erase(my_vector.begin()); //erase the firs element 
} 

nếu bạn muốn cạnh tranh trước pop cho toàn bộ mảng vector (bạn muốn giữ pop ra mọi phần tử từ đầu đến cuối), tôi đề xuất trên:

reverse(my_vector.begin(),my_vector.end()); // reverse the order of the vector array 
my_vector.pop_back(); // now just simple pop_back will give you the results