Блог пользователя PaciukZvichainyi

Автор PaciukZvichainyi, история, 2 года назад, По-английски

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.

  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

»
2 года назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

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.

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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?

    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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