Ignore the downvotes, this is a banger post. Super practical stuff that actually helps you pass TLE. The 9x benchmark is crazy. Keep it up, bro!

The content is for people who love AI generated blogs, obviously

Haha, you're 100% right.

For pure speed in Competitive Programming (CP) where you know the maximum value of $$$N$$$, a global static array (or std::array) is unbeatable — no dynamic allocation overhead at all.

My main point was just to show why std::vector (contiguous memory) is so much better than std::list (pointer chasing).
But you're absolutely correct — static arrays are another level up.

That's a fair point, and you're right.

In most common use cases (like sorting, finding distances, etc.), you’ll be accessing x, y, and z together. So the standard Array of Structs (AoS) is already quite cache-friendly. the Struct of Arrays (SoA) pattern is more of a niche optimization. It only helps in a specific bottleneck scenario — for example, if you had a hot loop that only needed to process the x-coordinates of millions of points, not y or z.

Thanks for the feedback! It's a good clarification.

It is highly use case dependent, but it's a very common optimization. It can also help with auto-vectorization if you do operations such as f(x[i], y[i], z[i]) on the entire array. Ref: https://en.algorithmica.org/hpc/cpu-cache/aos-soa/ https://odin-lang.org/docs/overview/#soa-data-types

Wow, thanks for sharing this!
That's exactly the kind of scenario that causes TLEs or FSTs even when the algorithm is correct.
A painful way to learn, but honestly, a super valuable fix.
Great case study for the post!

Thanks for the Godbolt tip G++ does auto-optimize %2 to bit ops like &1, but the real killer is branch mispredictions on unpredictable ifs (10-20 cycles each); branchless dodges that for hotter loops...

Appreciate the correction—keeps me sharp!

I remember a recent case where I optimized branch prediction out of a dp in some ucup contest by using templates.

int dp(int u, int v, int t) {
  // memo stuff here
  if(t == 0) {
    // do a shit
  } else if(t == 1) {
    // do some shit
  } else {
    // do other shit
  }
}

to

template<const int t>
int dp(int u, int v) {
  // memo stuff here
  if(t == 0) {
    // do a shit
  } else if(t == 1) {
    // do some shit
  } else {
    // do other shit
  }
}

The compiler then creates a function for every t and optimizes out the ifs completely. It turned 3s TLE into 1.1s AC.

My guess is from GPT.

If you actually want to learn about this you can start by looking up Data Oriented Design. I think these topics mostly apply only to game development though.

Cache locality is something that is taught in computer architecture courses

There are some minor differences such as the size of a basic_string object is 32 bytes, whereas the size of a vector object is 24 bytes. This should not be a problem unless you store and want to iterate over a large collection of basic_string_view objects.

basic_string does small string optimization so it can store up to 15 bytes of data inline without doing any heap allocation. This can be useful if want a lot of dynamic arrays but most of them are very small.

Additionally, you may want to look into std::span if you want slicing of a vector. It is similar to basic_string_view. Both are views over a contiguous block of elements of type T, and both provide sub-slicing (span::subspan and basic_string_view::substr). Note that these types are cheap to construct so try not to hold a persistent reference to them. For example, if you have a span over a vector and you push_back into the vector then the span might get invalidated. Just construct it when you need it. I tend to do string_view{s}.substr(i, j - i + 1) == s2 if I need to compare a sub-string.

My advice would be to not pick a favorite, and use it everywhere. Pick what you need.

Interesting. To me, a good bit of stuff in the post looks "too humanly" :)

It will not be a meaningful comparison because list::insert and vector::insert both have different time complexities.

vector::insert: If reallocation happens, linear in the number of elements of the vector after insertion; otherwise, linear in the number of elements inserted plus std::distance(pos, end()).

The memory allocation time complexity due to insert in a vector can be considered as amortized $$$O(1)$$$ due to the same reason as push_back. The reason being vector allocates more memory than required and it does not need to reallocate for the subsequent few inserts.

So, the overhead mostly comes from copying and shifting the elements in [pos, end()) over.

I wrote a small benchmark. You can increase the no. of insertions to see how the vector insert gets worse. Link: https://quick-bench.com/q/0hMXEe0tvlxqFLSJH1xInYvvneA#

Inserting in a vector at the beginning is the worst case as all the elements need to be copied over. Inserting at the back is equivalent to push_back. The closer to the end you are inserting, the better the performance.

Can you provide links to both the submissions?

In fact endl flush the out stream and might be more significant in interactive tasks.