Việc chèn các phần tử trong một vector có làm hỏng một con trỏ tới vectơ không?

Question

Trong một chương trình để mô phỏng cổng logic Tôi chuyển từ việc sử dụng các mảng

node N[1000]; 

để vectơ

vector<node> N; 

Và chương trình của tôi đã hoạt động hoàn hảo trước khi sử dụng vectơ nhưng bây giờ nó in kết quả sai, vì vậy tôi cố gắng gỡ rối và tôi phát hiện ra lỗi xảy ra ở đây:

node* Simulator::FindNode(string h) 
{ 
    int i; 
    for(i = 0; i < NNodes; i++) 
    { 
     if (N[i].getname() == h) 
     { 
      return &N[i]; 
     } 
    } 

    node n ; 
    N.push_back(n); 
    N[NNodes].setname(h); 
    NNodes++; 
    return &N[NNodes-1]; //why?because of NNodes++ 
} 

// ... 

node* inp1; 
node* inp2; 
node* out; 
string NodeName; 

inp_file >> NodeName; 
inp1 = FindNode(NodeName); 
s1 = inp1; 

inp_file >> NodeName; 
inp2 = FindNode(NodeName); //inp1 is destroyed here 

inp_file >> NodeName; 
out = FindNode(NodeName); //inp2 and inp1 are destroyed here 

Khi lần đầu tiên, con trỏ thứ nhất i np1 trỏ đến đúng nơi là &N[0].

Khi gọi FindNode lần thứ hai con trỏ thứ 1 inp1 trỏ vào rác và điểm inp2 con trỏ thứ hai đến đúng vị trí &N[1].

Khi gọi FindNode lần thứ 3 cả con trỏ thứ nhất và thứ hai (inp1, inp2) trỏ tới rác! Và con trỏ thứ ba ra điểm đến đúng nơi.

Tại sao điều đó lại xảy ra?
Làm thế nào để vector hoạt động khi tôi chèn các mục vào chúng và loại con trỏ nào tôi nên sử dụng để trỏ tới các mục vectơ?

Answer 1

Một vài điều.

Đầu tiên, theo như tôi có thể nói NNodes chỉ cần theo dõi kích thước. Nhưng bạn có std::vector::size() cho điều đó. Sau đó, bạn sử dụng nó để lấy phần tử được chèn cuối cùng, nhưng bạn chỉ có thể sử dụng std::vector::back() cho điều đó: return &N.back();.

Ngoài ra, thông số của bạn đang được truyền theo giá trị, khi thông số này có thể được chuyển bởi tham chiếu const: const string& h. Điều này tránh các bản sao không cần thiết, và nói chung * bạn nên chuyển mọi thứ bằng tham chiếu const thay cho giá trị bằng.

Và điều này là xấu:

node n; 
N.push_back(n); 
N[NNodes].setname(h); 

node có lẽ nên có một constructor mà phải mất một const string& và đặt tên trong quá trình khởi. Bằng cách đó bạn không bao giờ có thể có một nút mà không cần một cái tên, như trong:

node n(h); 
N.push_back(n); 

Hoặc hơn ngắn gọn:

N.push_back(node(h)); 

Tốt hơn nhiều.

Thứ hai, có, vector có thể làm mất hiệu lực con trỏ tới các phần tử; cụ thể là, bất cứ khi nào năng lực của véc-tơ cần được tăng lên. Nếu bạn có thể, reserve() khả năng lên phía trước để tránh phân bổ lại. Trong trường hợp của bạn, bạn không thể, vì vậy bạn có thể đi hai tuyến đường khác nhau.

Tuyến đường đầu tiên là a level of indirection. Thay vì chỉ trực tiếp vào mọi thứ, hãy đưa chỉ mục của họ vào mảng. Lưu ý rằng mặc dù địa chỉ của chúng có thể thay đổi nhưng vị trí của chúng trong vector sẽ không thay đổi. Bạn sẽ có Simulator::FindNode trả lại size_t và trả lại N.size() - 1. Thêm thành viên như node& GetNode(size_t index), chỉ cần return N[index]; (sẽ kiểm tra lỗi nếu bạn muốn). Bây giờ bất cứ khi nào bạn cần một thành viên, hãy đưa chỉ mục cho thành viên đó đến GetNode và bạn sẽ nhận được một tham chiếu đến nút đó.

Tuyến đường khác là thay đổi vùng chứa của bạn. Bạn có thể sử dụng ví dụ deque. Điều này không có bộ nhớ tiếp giáp, nhưng nó giống như vector. push_back và pop_back vẫn là O (1) và nó vẫn có khả năng kết hợp bộ nhớ cache tốt. (Và bằng cách này, deque nghề lưu trữ tiếp giáp cho khả năng push_front và pop_front trong thời gian O (1) thời gian cũng)

Điều quan trọng là deque sẽ không con trỏ vô hiệu trong một push hoặc pop hoạt động từ một trong hai kết thúc.Nó hoạt động bằng một loại lai danh sách vectơ, nơi bạn nhận được nhiều phần lưu trữ cho các phần tử được liên kết với nhau. Thay đổi bộ nhớ cơ bản của bạn thành deque (và không lấy hoặc đặt bất kỳ thứ gì ở giữa) và bạn có thể trỏ đến mọi thứ tốt.

Tuy nhiên, từ những gì tôi có thể cho bạn biết có một bản đồ không hiệu quả khủng khiếp. Bạn đang ánh xạ tên cho các nút. Có lẽ bạn chỉ nên sử dụng std::map, trong đó có giao diện chính xác mà bạn đang cố gắng tạo lại. Bạn thậm chí có thể trỏ đến bất kỳ phần tử nào trong bản đồ, điều này không bao giờ làm mất hiệu lực mọi thứ.

_{* Nguyên tắc là, đi ngang qua const tham chiếu trừ loại là nguyên thủy (built-in như int, double, vv), nếu kích thước loại nhỏ hơn sizeof(void*), hoặc nếu bạn đang cần một bản sao của nó anyway.}

Đó là, không làm điều này:

void foo(const std::string& s) 
{ 
    std::string ss(s); // make a copy, use copy 
} 

Nhưng làm điều này:

void foo(std::string s) // make a copy, use copy 
{ 
} 

Answer 2

Có, nó có thể phân bổ lại toàn bộ bộ đệm, làm cho tất cả các con trỏ vào vị trí cũ không hợp lệ.

Bạn có thể giới hạn điều này bằng cách preallocating, nhưng đó thực sự chỉ là một tăng hiệu suất. Cách tốt hơn là sử dụng các chỉ mục thay vì các con trỏ thô.

Answer 3

Khi một vectơ phát triển, nó được phân bổ lại, điều này làm vô hiệu hóa tất cả các con trỏ tới các phần tử của vector.

Nếu bạn biết trước bao nhiêu phần tử bạn sẽ có trong vectơ, bạn có thể sử dụng phương thức reserve() để preallocate không gian.

Answer 4

Trả về con trỏ tới thành viên STL nội bộ có lẽ không phải là ý tưởng hay nhất. Khi bạn đưa một đối tượng vào một container STL, bạn về cơ bản sẽ từ bỏ quyền kiểm soát nó. Bạn đang nói với STL nó có thể di chuyển nó xung quanh vì nó thấy phù hợp để duy trì những lời hứa mà container mang lại cho bạn. Quay trở lại chỉ mục nơi nút được đặt là một ý tưởng tốt hơn như Steven Sudit đã đề cập.

Khi bạn nhận được chỉ mục, bạn có thể tạo một hàm trả về bản sao nội dung của nút bạn quan tâm. Bằng cách này, bạn cũng duy trì đóng gói dữ liệu với vùng chứa STL, không cho phép bất kỳ ai sửa đổi nội dung của nó.

Answer 5

Có, chèn sẽ làm mất hiệu lực con trỏ cũ thành phần tử vectơ khi phân bổ lại. Nếu bạn muốn sử dụng con trỏ ổn định thực sự khó khăn, bạn có thể chuyển từ vector sang deque. Nó cung cấp một giao diện rất giống với vector và có thể phát triển mà không tái phân bổ và di chuyển các nội dung trước đó bằng cách phân bổ các khối khác nhau.

Giá bạn trả cho việc sử dụng deque thay vì véc-tơ là một mức độ gián tiếp khi truy cập ngẫu nhiên. Tùy thuộc vào cách sử dụng của bạn, điều đó có thể hoàn toàn không liên quan. Bạn nên lặp lại trên deque deque toàn bộ nếu cần thiết bằng cách sử dụng iterators. Điều đó sẽ nhanh chóng lặp qua một vectơ.

Mức tăng là: không reallocations!

Answer 6

Hãy tưởng tượng bạn cần viết mã dựa trên mảng để có thể tái kích thước mảng nếu cần.

Hãy tưởng tượng bạn sẽ làm điều đó như thế nào.

Hãy tưởng tượng điều gì sẽ xảy ra với con trỏ cũ.

Viết lại mã của bạn để sử dụng các chỉ mục thay vì con trỏ hoặc để đảm bảo rằng phân bổ lại không xảy ra, nếu thích hợp.