Strange Comparison: vector<vector> vs vector<pair<int,int>> ?

Revision en1, by physics0523, 2022-12-17 15:19:02

If we want to use a 2D dynamic array, some C++ user writes following 2D vector:

vector<vector<int>> a(n);

// add y to a[x]
a[x].push_back(y);

// walkthrough a[x]
for(auto &nx : a[x]){
  cout << nx << "\n";
}

But we can do the equivalent thing with handwritten linked list (when we know the total size) by using vector<pair<int,int>>:

pair<int,int> empty={-1,-1};
vector<pair<int,int>> b(n+total_size,empty);
int add_point=n;

// add y to b[x]
if(b[x]!=empty){
  b[add_point]=b[x];
  b[x].second=add_point;
  add_point++;
}
b[x].first=y;

// walkthrough b[x]
int current=x;
while(current!=empty.second && b[currnt]!=empty){
  cout << b
}

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English physics0523 2022-12-17 17:31:08 1472 Tiny change: 'average)\n| |' -> 'average)\n\n| |' (published)
en2 English physics0523 2022-12-17 17:04:41 81
en1 English physics0523 2022-12-17 15:19:02 757 Initial revision (saved to drafts)