boostorg / boostorg/json

Explore potential for optimization in array::insert(Iter, InputIt, InputIt)

Open
#702 6 comments 0 reactions 0 assignees View on GitHub
Performance
Dominant language
C++
Stars
479
Forks
110
Avg merge
10d 3h
Merged PRs (30d)
5

Description

The idea is this:
1. Fill the buffer up to capacity _at the end_ (needs a `revert_insert` protection).
2. Create a temporary buffer with the remaining elements (can throw).
3. If temporary buffer is not empty
1. Allocate new buffer with necessary size (can throw).
2. Relocate elements
* first original elements, up to insertion point,
* then new elements (at the end of the original buffer),
* then new elements from the temporary buffer,
* then remaining old elements.
4. If the temporary buffer is empty, rotate elements in the original buffer instead.

In the end result:
1. If the original capacity could accommodate the input range, then no new buffer (even a temporary one) is allocated. This is particularly useful when the caller uses input iterators, but does know the input range size, and thus can call `reserve`.
2. We should be able to keep the strong guarantee.

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.