What happened when use vector::reserve or vector::resize

Question

I'm user of C++14. When I coded for sort two dimensional array using std::vector with compare fucntion. But it didn't work as I thought, finally I found something weird things. Let's see code below.

using namespace std; int n; vector<vector<int>> v; bool cmp(const vector<int>& l, const vector<int>& r){ return l[1] < r[1] ? true : l[0] < r[0]; } int main() { scanf("%d", &n); v.resize(n, vector<int>(2)); for (int i = 0; i < n; ++i) scanf("%d %d", &v[i][0], &v[i][1]); sort(v.begin(), v.end(), cmp); for(int i = 0; i < n; ++i) cout << v[i][0] << ' ' << v[i][1] << endl; return 0; }

(Please ignore that I use scanf with cout. I'm doing on problem solving.) And here is input

11 1 4 3 5 0 6 5 7 3 8 5 9 6 10 8 11 8 12 2 13 12 14

I expected that output is exactly same with input without n, but the output is

0 6 1 4 2 13 3 5 3 8 5 7 5 9 6 10 8 11 8 12 12 14

Also I found the weird point when I change

v.resize(n, vector<int>(2);

to

v.reserve(n); for(int i = 0; i < n; ++i) v[i].reserve(2);

reserve makes code right as I wanted. I think I know the different with reserve and resize at vector but something is missing...

Would you teach me what is missing thing..?

"reserve makes code right as I wanted" - Reserving doesn't add elements to the vector, only raw memory. You are interacting with vectors that aren't there. — StoryTeller - Unslander Monica
– StoryTeller - Unslander Monica, Commented Jul 26, 2020 at 10:52
Your cmp implementation doesn't obey strict weak ordering (I don't think). That's undefined behaviour. — G.M.
– G.M., Commented Jul 26, 2020 at 10:53
resize changes the size of a vector, reserve doesn't. That's the thing you are missing. reserve allocates more space for the vector but does not change it's size. — john
– john, Commented Jul 26, 2020 at 11:12
Thank you for alll. I found bug in my logic for your answers. — Jerry
– Jerry, Commented Jul 26, 2020 at 12:24

MikeCAT · Accepted Answer · 2020-07-26 10:52:56Z

Firstly, your cmp function may not be what you want. For example, it will judge {0, 6} as smaller than {3, 5}. Try this instead:

bool cmp(const vector<int>& l, const vector<int>& r){ return l[1] < r[1] ? true : (l[1] == r[1] && l[0] < r[0]); }

or this:

bool cmp(const vector<int>& l, const vector<int>& r){ return l[1] != r[1] ? l[1] < r[1] : l[0] < r[0]; }

Secondly, std::vector::reserve won't change the number of elements in the vectors. For this reason, you invoked undefined behavior by using out-of-range (nonexistent) elements and you got your result by chance.

Your right... It was just coincidence ◡̈ It was my misunderstood of vector::reserve. Thank you!

Arthur R. · Accepted Answer · 2020-07-26 11:24:53Z

Since you know the size of your inner container at compile time, maybe you want to use an std::array instead (or std::pair or even a small struct to have better member variables names). Also, don't forget for range-based loop, it's elegant and a safer approach when iterating on a container. Next, you could use a lambda for your compare function in the std::sort call. Global variables are also considered as a bad practice, since it broke the encapsulation rule.

#include <iostream> #include <vector> #include <array> #include <algorithm> int main() { std::size_t n; std::cin >> n; std::vector<std::array<int, 2>> vec(n); for (auto& [x, y] : vec) std::cin >> x >> y; std::sort(begin(vec), end(vec), [](const auto& l, const auto& r) { return l[1] != r[1] ? l[1] < r[1] : l[0] < r[0]; }); for (const auto& [x, y] : vec) std::cout << x << ' ' << y << '\n'; return EXIT_SUCCESS; }

You're answer is amazingly helpful, because I don't have code reviewer of C++ since I work with java actually. I code c++ program for my pleasure. Really really thank you for your answer! Have a nice day :)

Collectives™ on Stack Overflow

What happened when use vector::reserve or vector::resize

2 Answers 2

1 Comment

1 Comment

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

1 Comment

Related