PaciukZvichainyi's blog

Runtime without vector.reserve
By PaciukZvichainyi, history, 19 months ago, In English

Why I got Runtime Error on first test w/o vector reserve and got Accepted with reserve?

Without

With

The only difference is line 77 (if you open it in text editor).

Also, it passes test on local machine even without reserve statement.

RE

ImplicitSegmentTree(int l, int r) {
	lb = l; rb = r;
	n = r-l+1;
	next = 0;
	// TODO Change
	// nodes.reserve(4831707);
	nodes.push_back(Node());
	root = &nodes[next++];
}

OK

ImplicitSegmentTree(int l, int r) {
	lb = l; rb = r;
	n = r-l+1;
	next = 0;
	// TODO Change
	nodes.reserve(4831707);
	nodes.push_back(Node());
	root = &nodes[next++];
}

And last: the memory limit isn't a problem with this solution, because even with reserve(1e7) it works fine.

  • Vote: I like it
  • +5
  • Vote: I do not like it

»
19 months ago, # |
  Vote: I like it +9 Vote: I do not like it

This is because of the way how vectors work. When you increase the size of a vector, it sometimes needs to relocate all of its elements to a different place in memory. When this happens, all pointers to its elements may become invalid. Using reserve means that until the vector size reaches some threshold (which is not less than the number of elements you reserved), it won't be relocated, that's why it works with reserve.

→ Reply
  • »
    »
    19 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Do the vectors reallocate new memory for every push_back when a size is a power of two? I knew that vectors are contiguous in memory but did not understand how its allocation (towards a power of two) actually works. Is this "power of two" allocation just a method to guarantee $$$O(\frac{2^n}{2^{n-1}})=O(1)$$$ amortized time complexity?

    → Reply
    • »
      »
      »
      19 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes, but it is unspecified whether the implementation needs to reallocate when their size is a power of 2; only the specifications in the C++ standard are relevant. You can use any exponential reallocation scheme for getting amortized $$$O(1)$$$ complexity.

      If you want your code to work as it is, you can consider using a std::deque instead of a std::vector. It supports pretty much all vector operations you would need in this context and doesn't suffer from pointer/iterator invalidation. Keep in mind that an empty std::deque is quite large though.

      → Reply
  • »
    »
    19 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thx, never heard about relocation, because never worked with pointers in such way.

    → Reply