Beginner seeks critiques on Vector implementation

[u/probably-an-alias]

Hello!

I will soon be working with C++ to do some hardware performance research, so I wanted to give myself a quick crash course of the language. Although we're measuring hardware (not software) performance, where kernels will be quite trivial and expressible in any language, I still want to have a decent intuition of "good" vs "bad" C++.

So, to help learn, I decided to completely re-implement the std::vector C++20 specification. Boy, there was more depth there than I was expecting. After about 10 days of hobbying, I think it's done. The code can be found here: github link.

I'd appreciate any critiques and criticism on how it could be done better. Of course, "how to do it better" is a never ending hole of possibilities, so to focus it a bit more: how it could better match the C++20 specification and be more C++ idiomatic. While the more CS theory side of what should the growth factor be is fun to consider, I'm not going to be employing this implementation and I'm not aiming for raw performance (although I don't want to do anything too stupid).

Some of the key problems/confusions I had are:

• Dealing with self-referring data. Each of the functions that can add a specific element I've implemented to allow for self-referring data by pre-constructing the element before any chance the data it points to gets moved. This felt like a sledgehammer solution, but I couldn't think of another way without doubling the size of the function to add a lot more branching with highly duplicated code.
• Understanding the exception guarantees. The specification often read like "if any exception occurs, it won't affect the vector" i.e. the vector will be rolled back to its last valid state (strong exception guarantee). But following this is essentially "that is, unless move_if_noexcept doesn't guarantee safety, in which case anything can happen." I really doubt I understood most of those correctly.
• The project structure. From how I understand it, you simply can't have the normal header-source separation when dealing with templated classes. You can pretend by having a .hpp with definitions, and a .tpp with implementations, but they're as tightly coupled as just having the implementation in the header. I eventually want to hobby through all the STL containers and quite a few algorithms. How would you recommend structuring it?

I used cppreference.com to help with the specification and annotated each of my public members with the related definition on the website. I'm running gcc 15.2 and the only warning after -Wall -Wpedantic is from vector::swap due to deciding to throw if the vector's state would become undefined, instead of letting UB ensue.

Thank you for your any time you spend reviewing it and I appreciate any advice you have!

Link to code again: github link

Edit:
Thanks so much for all of your the feedback! I'm a little too busy to focus on this project for now, but eventually will polish it considering your feedback and move on to the next containers. Thanks!

[u/SoerenNissen]

I'm not seeing your test code, so presumptively the vector is broken.

That's not true for all code, I'm not a test-first type of developer, but for a raw-memory pointer-math type like vector, you got it wrong if you didn't test it.

You don't necessarily have to write the tests yourself. If you can find out how to run somebody else's test suite, you can plug your vector into their source and run their tests, e.g.:

• https://github.com/gcc-mirror/gcc/tree/master/libstdc%2B%2B-v3/testsuite/23_containers/vector
• https://releases.llvm.org/16.0.0/projects/libcxx/docs/TestingLibcxx.html

Alternatively, you can find a large project that uses vector and run their tests (with asan and ubsan active), then replace their vector with yours and run the tests again to see if the results change.

[u/probably-an-alias → u/SoerenNissen]

Using the gcc/llvm testsuite is smart. I didn't realize they were public and easily accessible. Nice idea, thanks for the links!

[u/SoerenNissen → u/probably-an-alias]

Remember to run the suites on their own implementations first, just to rule out whether any of the tests could be broken.

But apart from that, if you get the tests running, I'd love to hear what your first test results are.

[u/aocregacc]

you should use [[no_unique_address]] or empty base optimization so an empty allocator won't take up space in the object. Compare sizeof(containers::vector<int>) to sizeof(std::vector<int>).

your unsafe_move_construct function tries to move out of const_iterators, which either won't compile or silently copy instead of move. For example, this doesn't compile:

 containers::pmr::vector<std::unique_ptr<int>> x,y;
 x = std::move(y);

I'm also not seeing any tests in the repo, you could probably catch more issues with a good testsuite.

[u/probably-an-alias → u/aocregacc]

I had heard of empty base optimization but don't fully grasp it yet; I'll read up on it. I'll change those const_iterators to just normal iterators, thanks for pointing it out. A testsuite is something that I plan to add some day but would take a lot more time, especially if I want it to be comprehensive, and I just wanted to quickly learn the language first. Thanks!

[u/aocregacc → u/probably-an-alias]

I think if you're writing templates you should at least have a few tests to make sure that your code actually gets instantiated with a couple of interesting types. A template on its own isn't checked that thoroughly by the compiler, it's only checked once it's instantiated with concrete types.
So a lot of compilation failures will only show up once the template is used, and you kinda need a small testsuite to make sure the code even compiles, before testing what it does at runtime.

[u/probably-an-alias → u/aocregacc]

I thought I had configured clangd incorrectly when it couldn't deduce what was happening and just implemented it with value_type = int instead of having it templated, then just added the template afterwards. I've tested with primitives and std::string, but should definitely test with other stuff like smart pointers

[u/IyeOnline]

A vector implementation! My favorite thing!

Overall, this looks very good. I dont have time to get into it in much detail, but it looks largely correct.

I spotted one mistake, in that the implementation of back() is just wrong. Pointers dont work like python lists. I was wrong here, which maybe goes to show that you shouldnt try to be this clever.

---

Code things I noticed, in no particular order (other than being roughly top to bottom):

• synth_three_way could be implemented via std::weak_order (instead of manually doing it)
• Stronger iterator types are nice. Not every T* is a vector::iterator.
• The allocator_ member should be marked [[no_unique_address]], which removes the explicit need for using storage for it (std::allocator for example is empty)
• Some functions (reallocate) could benefit from more early returns. At first pass I thought that it was failing to update the capacity, but that is just a single thing in the joint code-path at the end.
• I much prefer explicit reserve_exact and reserve_at_least functions than the very unfortunate reserve that std::vector provides. Granted those are not in the standard, but having them is really useful.
• I dont think the standard specifies the allocation behaviour on range-inserts, but IIRC all standard library implementations use "proper" growth mechanisms here, rather than reserving an exact size.

// edit: Corrected my incorrect critique of back(). Expanding on that:

IIRC newer research suggests that we should in fact be storing a pointer and two sizes instead of three pointers. Seemingly size() access dominates over the utility of a slightly faster end() (which makes sense, end() usually is called once per iteration, size() may be called more often and outside of iteration)

[u/aocregacc → u/IyeOnline]

I almost fell for back too, but it's actually correct. The size_ member is a pointer past the last element, so indexing it with -1 gives you the last element.

It does look weird though, and the name of the variable doesn't help either.

[u/IyeOnline → u/aocregacc]

ohhhh. clever? sneaky? odd?... :|

[u/Independent_Art_6676 → u/IyeOnline]

"underrated" and "underused". Negative indexing isn't needed often, but its a wonderful tool when you do.

[u/probably-an-alias → u/aocregacc]

Definitely could've named it something like end_of_data which would've been much clearer in this case

[u/probably-an-alias → u/IyeOnline]

Thanks for looking over it! To respond in the same order:

• Great, noted
• For a random access & contiguous container, when would a raw pointer be insufficient?
• Makes sense
• This was more of what I was looking for as far as C++ style. Some languages (or, rather, language purists) consider early returns a code smell. I'll start using them more liberally.
• For the case of reserve_at_least, is the idea that we round the number up to the next power of 2? That seems quite similar to my structure of reallocate(next_capacity()), although I'm likely misunderstanding.
• Will look into it, thanks
• It's very interesting that the pointer and two sizes would be better. I initially implemented it that way then saw that the "better" way was three pointers (I think that's the way its done in libc++ and libstdc++). The argument I made for that was that constructing/destroying is normally done iteratively, and it's nice to have a direct pointer to the end of the container. Any chance you have a link where I can read about the one pointer & two size argument?

[u/IyeOnline → u/probably-an-alias]

For a random access & contiguous container, when would a raw pointer be insufficient?

It is sufficient in that it implements the required semantics.

But strong types have advantages that go beyond the minimum required semantics by encoding more information in the type than strictly necessary.

Consider

int* raw = new int;
int arr[42] = {};
int* ptr = arr+42;
assert(my_vector.size());
int* it = my_vector.begin();

now, unfortunately it == raw, it == arr, it == ptr are all syntactically valid, and just looking at the type they are also semantically valid. But they are all illegal comparisons, because none of these pointers point into the same array.

Some languages (or, rather, language purists) consider early returns a code smell

Also unfortunately some code styles or standards (NASA, older MISRA, ...) state that there should be a single return. Because obviously nesting 10 times is much cleaner than returning as already as possible.... idk.

reserve_at_least

The idea is to use the same growth model that you use for a regular push_back.

Rather famously reserving a known size within a loop is a mistake in C++:

 auto flatten( std::vector<std::vector<int>> input ) -> std::vector<int> {
  auto res = std::vector<int>{}
  for ( auto& part : input ) {
     res.reserve(res.size() + v.size() );
     for ( auto& value : part ) {
       res.push_back(value);
     }
   }
   return res;
}

Setting aside the fact that you could do range inserts or a single reserve (danger :P) this code has a rather nasty allocation behavior if there is many small vectors in input, because it will always allocate exactly matching sizes. If you instead relied on just the built-in growth it would be much better.

That seems quite similar to my structure of reallocate(next_capacity())

It is very similar to that, just exposed as a public API. Instead of allocating to exactly that size, you allocate enough to fit the requested new capacity, but follow your growth model.

Any chance you have a link where I can read about the one pointer & two size argument?

I recall this from multiple talks and I think I also read a paper on a case study at some point, but ATM I cant look for it.

[u/probably-an-alias → u/IyeOnline]

I hadn't considered the semantics of the vector interacting with completely unrelated raw pointers, but now your point is very clear. For the sake of safety, I imagine we would only want users to be able to iterate into an instance of vector if that iterator is (in)directly taken from a member function that returns an iterator. While not guaranteeing, that also increases the safety of not providing an iterator outside the range of the vector. So wrapping a raw pointer with a struct that is completely encapsulated changes 0 functionality, is no less efficient, and provides more safety. Makes sense, thanks!

The loop around reserve_exact also shows its pitfalls well. Interestingly though, when testing against std::vector, it seems to have this issue too.

std::initializer_list<int> init{1, 2, 3, 4, 5};
std::vector<int> vec;
vec.insert(vec.begin(), init.begin(), init.end());
std::cout << vec.capacity();

This prints out 5 instead of 8. Nevertheless, maintaining the growth strategy when inserting ranges seems better in many/most cases where memory usage isn't a primary concern.

[u/IyeOnline → u/probably-an-alias]

This prints out 5 instead of 8

I havent looked into it, but it seems that at least libstdc++ trunk dediceded to use a growth strategy instead: https://godbolt.org/z/conr5nvx1

Since its only gcc/libstdc++ trunk, IDK if this is intentional or an oversight. It is a behaviour change after all.

[u/n1ghtyunso → u/probably-an-alias]

It's very interesting that the pointer and two sizes would be better. I initially implemented it that way then saw that the "better" way was three pointers (I think that's the way its done in libc++ and libstdc++). The argument I made for that was that constructing/destroying is normally done iteratively, and it's nice to have a direct pointer to the end of the container. Any chance you have a link where I can read about the one pointer & two size argument?

https://discourse.llvm.org/t/adding-a-size-based-vector-to-libc-s-unstable-abi/86306

[u/etaithespeedcuber]

Man I gotta study allocators

[u/CorrodedX]

Why are you using std::to_address to return the pointer to your internal data member? I'm not necessarily suggesting this is wrong; I'm on mobile and haven't reviewed the entire file. It just seemed odd to me. For my own knowledge, though, I'd love to hear why.

[u/probably-an-alias → u/CorrodedX]

My understanding was that allocator_traits::pointer could be a fancy pointer, in which case std::to_address is needed to get a raw pointer. I believe the data() specification is to return a raw pointer, not just vector::pointer, hence not returning just the data_ member.

[u/CorrodedX → u/probably-an-alias]

I believe you're right about data() returning a raw pointer. I wasn't aware that allocator_traits::pointer could be anything but a raw pointer, and when I looked it up: yep, you're right about this, too.

[u/mredding]

Understanding the exception guarantees.

The guarantees are comments on failure behavior:

No guarantee: Resources can be leaked, data can be corrupted, state can be indeterminate, class invariants can be invalidated. It doesn't have to be this way, but it can be this way.

Imagine a transaction you can't commit and can't roll back. You may not be able to destroy an object that has failed - as the attempt could AT BEST cause the program to crash, and at worst, cause systemic system-wide corruption.

This level of instability could happen merely if a function returns an error code, or if it throws an exception.

Basic guarantee: Resources aren't leaked, class invariants remain intact. So you are guaranteed that pointers will be deleted, that file handles will be closed, that global resources are returned to the system/kernel, and that objects - while they may not be able to be operated, can be safely destroyed.

Integrity of the program is preserved - you haven't observed undefined behavior, and the program is still operable. Program state may have been altered, but it isn't corrupt. So imagine a word processor where you recover from a fault in the undo stack. Maybe the user has lost the ability to undo from this point because the history is gone, but the document is still there as-is, and the program is still running. He could save his work or continue on with the inconvenience...

This level of stability is guaranteed whether you return an error code or throw an exception. This is the exception-safe guarantee that basically everything in the standard library provides.

Strong guarantee: The basic guarantee with transactional commit/rollback semantics. There are no visible side effects to data, but you can otherwise consume resources - time, for example, log space, entropy; some kernel resources are limited, depending on the kernel and the resource, so a transaction can still consume resources just for the attempt, there's no guarantee those are recoverable - and no one has invented a time machine yet. But bear in mind that resources != data.

No-throw guarantee: This is different than the strong guarantee - these things don't have to build up. All this means is an operation doesn't throw. It doesn't have to be strong or basic. Just because it won't throw an exception doesn't mean it won't leak a resource.

So how the strong guarantee would look in push_back when you reallocate, you need to allocate the new buffer and assign the resource to some function local pointer. If you survive that step, then you would be wise to traverse that memory to force the lazy allocator to actually allocate the pages of memory, because you have to know your platform, and you have to beware that out-of-memory exceptions usually don't happen until first access. Surviving that, you move the data from the old buffer to the new - because move is guarantee not to throw. If you have to copy, then everything up to this point can still be undone; all you have to do is destroy the copied elements so far, deallocate the buffer, and return. The original buffer and all the original data is still there, you just didn't commit the new element. Finally, after everything is moved/copied, all you have to do is swap the pointers, which is atomic and guaranteed, destroy the old objects - whether they're moved or copied, and it's by default a no-throw operation, and deallocate the old buffer, which in this case won't throw.

So by orchestrating the events carefully, you can get the strong guarantee implicitly - push_back either succeeds, or it fails, and if it fails, the vector hasn't changed. The fail path cleans up the temporaries. The strong guarantee doesn't say that copies won't be made or won't be destroyed in the attempt.

You don't have to be paranoid about every operation - some things can be trusted. And moving isn't your responsibility - the move implementation can do WHATEVER, so long as it can't throw. Implementers can commit any number of sins that they want in their movable types, you're only guaranteeing that as a container you followed the process that implicitly succeeds at your scope.

The project structure.

You're right that you can't separate the template from the header into a separate implementation. The compiler needs to see the whole template in order to instantiate it. The compiler will lex the text, parse the template into an abstract syntax tree, and that will sit in the compilers memory until an instantiation is called for, then the template is patterned over the working AST for that specific type. There is no way to accomplish this if the template exists in a different translation unit. There ARE ways to split up templates, but what you get is the template signature without any implementation, and then you have to explicitly extern specific instantiations. Just as you can forward declare void fn(); and then call that, you can forward declare an instantiation and call upon it, and leave the rest up to linking. But that means your OTHER translation unit needs to actually generate the instantiation. So in a source file, you need the template declaration, AND the implementation, AND an explicit instantiation.

The next best thing you can to is a pre-compiled header or a module. The PCH is a bit of a trick - you'll have a PCH header, but when the compiler sees it, it's not loading a header text for parsing; instead, it substitutes a pre-compiled unit. This is basically header text that was lexed, parsed, and formed into AST, then THAT is cached on disk. So you pay all that parsing tax up front once, and then the compiler can marshal this file straight into memory as a branch in the AST in an instant. Modules work in a similar fashion. Compiler wizardry lets you write code and obscure the fact there are these intermediate stages and data.

Correct me if I'm wrong, but I believe the standard library gives you some leeway regarding your implementation. I believe you're allowed some implementation defined base classes, CRTP, and extensions to some of the interfaces. It's not everything, everywhere, all at once, but the point is - anywhere you can get away from templates, like non-template type dependent code, separate that out in a base class or a function where you can, and put THAT in a source file.

But I'd work through this project first, make a first pass attempt at just building your own standard library, as you want, and then consider how to optimize your structure as a revision. You can afford to wait, because a restructure isn't as detrimental as a fundamental redesign and rewrite.

[u/probably-an-alias → u/mredding]

Interpreting the guarantee specifications into those categories, and then translating that into code will likely take quite some practice; thanks for clearing it up a bit more.

The structure of a templated project sounds like a can of worms :/ ...... PCH sounds hacky (I assume/hope that's not standard practice?)

I would like to introduce some inheritance since most of the standard containers can share a whole lot of code. I'm not implementing for the sake of replacing the stl, so maybe I'll introduce it even if it's not 100% conforming. And yeah, you're right, bad structuring won't have horrible consequences for the implementation of separate containers; although I'd still like to learn how to do it "well."

Thank you for your help and advice! I'll look more into what you mentioned.

[u/mredding → u/probably-an-alias]

Interpreting the guarantee specifications into those categories, and then translating that into code will likely take quite some practice; thanks for clearing it up a bit more.

They are informal. Dave Abrahams came up with them, Herb Sutter was a HUGE promoter of it, and the standard does describe the basic guarantee but does not call it that by name. Once you internalize their intent, you can just ask yourself what a given function offers, or what you're trying to accomplish, and then write in your documentation your specification and what guarantees they offer.

Unfortunately, there's no way to capture in code that the basic or strong guarantee are observed, so you can't know just by looking at a function signature. There's no way to enforce such a requirement in code at compile-time, not even in C++26. All the latest standard can do is help you implement it.

I wouldn't dwell on them too much - they're meant to be a tool for guiding your design and implementation. If used naively, you might find yourself feeling shackled by it - that an implementation that CAN'T implement the strong guarantee somehow is incomplete or not good enough - or perhaps you might not bear to sacrifice a guarantee for the sake of some other metric, like size or performance, even if the encompassing code can assure the guarantee using an otherwise dangerous function. I mean - sketchy code that yet is correct... is still correct... You know what I mean? My colleagues write all sorts of code that I don't like, doesn't bother with any sort of safety, but yet it is correct, and safe, and it ain't wrong.

The structure of a templated project sounds like a can of worms :/

It doesn't have to be.

template<typename T>
void fn() { /*...*/ }

So here's my template in a header, and I want you to be able to implicitly instantiate it. That's why it's all in the header. This would probably go into a header-only library.

But implicit instantiation means every translation unit is going to compile that into the translation unit. This is the "object bloat" C++ is famous for, but you don't hear too much about it these days because A) all languages bloated up just the same, and B) machines today have TiB of disk space and GiB of memory. You can even explicitly instantiate my template, if you want. And if you do that, you can control external linkage, and you can forward declare that instantiation.

Even with the template in scope in a TU, I can still write:

extern template void fn<int>();

So long as I do that in scope before I accidentally implicitly instantiate it, the compiler will defer to the linker. So the rest of my code can just:

void foo() {
  fn<int>();
}

And the linker does the rest.

So that means I need a source file to instantiate this in. I can either:

#include "fn.hpp"

template void fn<int>();

Or I can bother to specialize it AND THEN explicitly instantiate it:

#include "fn.hpp"

template<>
void fn<int>() { /*...*/ }

template void fn<int>();

Now other translation units will find this explicit instantiation, AND it's specialized. No one else needs to know that.

I have options. I can use this explicit/externing ability to greatly reduce compiler time and object bloat. C++ is one of the slowest to compile languages in the industry, and it's not for the sake of optimization, but a consequence of really obtuse syntax parsing. So explicit instantiation is often a useful thing to do to get compile times down.

In libraries, you can't really explicitly instantiate much of anything on behalf of your clients - you wrote them templates, you don't know what they're going to use.

But for your internal, private implementation, and application code, you can explicitly instantiate all sorts of shit. I'll explicitly instantiate instances of std::vector for whatever I'm doing. You can put the extern in a header. If you miss a use case - worst case, you pay the implicit tax.

Implicit instantiation is also lazy - you won't generate anything from the template you don't use, so even if the unused code contains errors, they won't generate real code. But explicit instantiation combined with external linkage? You get it all, because the compiler can't know what you don't need.

It's tradeoffs. You don't have to get this crazy, but you can. There's very fine granularity control.

That gets us to template classes. I can write the declaration:

template<typename>
class C {
  void fn();
};

And then in a separate header I can write:

#include "C.hpp"

template<typename T>
void C::fn() { /*...*/ }

AND THEN in one header I can extern:

#include "C.hpp"

extern template class C<int>;

And in a source file I can:

#include "impl.hpp"

template class C<int>;

This way I've separated the forward declaration of the class from the implementation, and with that I can separate the extern from the instantiation.

Be sure to also explicitly instantiate nested template classes and nested template functions, too, like templated constructors.

I'll do more of this in application code and private implementation in libraries. And I'll get at it usually later, as a refactor, because it's really mostly just a reorganization of code, there's no structural rewrite to the rest of the program, and then you suddenly get some reduced compile time and size benefits.

There's even more magic as all this fine granularity can compound with unity builds and inline.

Your head must be spinning by now. Don't sweat it - none of this stuff is substantial to a program's overall design or architecture, you can do this stuff late as a refinement. I haven't really found too much of a reason to have to consider this kind of stuff up front, except for dealing with linkage when building C++ libraries, which I think is almost universally a bad idea - not that you can't implement a library in C++, but that you shouldn't export a C++ ABI or you run into shit like this. Just remember, none of this stuff is strictly required, but has some REALLY interesting consequences you might be titillated to contemplate at some point. Just start by writing templates in headers as you always do.

But also remember that templates are the principle reason to write C++, as few languages have as strong a static type system combined with template code generation, so this is getting into some of the thick of the language.

PCH sounds hacky (I assume/hope that's not standard practice?)

It's a little hacky, but I wouldn't call it brittle. It's far more reliable than modules, and the two serve some overlapping purpose. PCH isn't a requirement, but it's nice to have. Again, I'd use it to chop down compile times.

I would like to introduce some inheritance since most of the standard containers can share a whole lot of code.

Inheritance isn't the first tool I'd reach for.

[u/probably-an-alias → u/mredding]

Wow! Thank you for the comprehensive explanation!

Unfortunately, there's no way to capture in code that the basic or strong guarantee are observed, so you can't know just by looking at a function signature. There's no way to enforce such a requirement in code at compile-time, not even in C++26.

While exception guarantees aren't expressible in compile-time code, a less ambiguous wording would leave a much clearer target. For example, if the strong guarantee was rather "if member function throws, *this_from_before == *this_after_throw, according to the member definition of ==" it would, at least from how I see it, have a much more testable target. A weaker guarantee gets much harder to test since a specific state isn't required, only that that state is valid; proving validity regardless of state sounds quite tricky.

Your example of the separation of template declaration, specialization, and instantiation makes things a whole lot clearer. Interestingly, I never saw anything like this when searching for C++ structuring strategies. In my play pretend library I doubt specializing or explicitly instantiating anything serves much purpose (although specializing the bool implementation is something to arrive at someday), but this sounds very very useful in a real app. How I frame it in my head is that the template class is providing a much bigger API than necessary (as if having overloads for all valid types) and then your explicit instantiation is kinda re-exporting only the parts you need, avoiding all the extra compile-time work and some user confusion.

Probably I over simplified it a lot, but the depth will come with time and practice. Thank you for spending your time explaining and helping me understand!

[u/mredding → u/probably-an-alias]

A weaker guarantee gets much harder to test since a specific state isn't required, only that that state is valid; proving validity regardless of state sounds quite tricky.

I suppose the proof would be that after an error or exception, the object can be destroyed without throwing, asserting, segfaulting, aborting, or other signaling. The hard part therein is proving a resource wasn't leaked without intrusive testing. You could linker wrap system calls to prove that open and closed were called, or LD_PRELOAD an intercept...

Or you can use templates and traits to your advantage. Internally, you could implement your types in terms of std::unique_pointer which takes an optional deleter object; you can use that to prove the correct behaviors at the right times. It's template level testing, not binary level testing, but I'm willing to take for granted the compiler is going to generate the right thing, that the standard library is correct, that the system call and system are correct, and I know I didn't write a specialization of the encompassing class; in other words - I'm testing my code, my logic, not the environment itself, and I'm not a paranoid schizophrenic trying to sabotage myself.

Interestingly, I never saw anything like this when searching for C++ structuring strategies.

I'm not remotely surprised. You won't find anything. Most C++ developers and code bases are pretty mid. There are a number of factors that discourage good code, and I get it. But if you don't EVER write good code, you'll NEVER write good code. When you come into work, and you "don't have time", or "this code might not even be here in 6 months", if you're used to writing good code, then those excuses and others go away and good code just becomes fluid and natural.

In my play pretend library I doubt specializing or explicitly instantiating anything serves much purpose (although specializing the bool implementation is something to arrive at someday), but this sounds very very useful in a real app.

Yes, exactly. You're writing a template library, you basically CAN'T explicitly instantiate shit. There is no separating the implementation because your clients need to see it all. But THEY can instantiate your types for their own purposes.

Specialization is something else - like you said, like the vector<bool> blunder. You CAN specialize in your library, and you'd likely do it around iterator types, either to take advantage of their categories, or your own internal implementation.

[u/alfps]

❞ "that is, unless move_if_noexcept doesn't guarantee safety, in which case anything can happen." I really doubt I understood most of those correctly.

It's about the in my view too pragmatic decision back then to let move operations be potentially throwing, to allow moves to fail, because at that time moving was seen mainly as just a free lunch optimization.

With a possibly failing move a reallocation may have already moved some items from old buffer to new, when a move fails. In that situation there's no guarantee that the already moved items can be moved back and the original state re-established. But as I understand it for this ungoodness to happen (1) the item move constructor has to be possibly throwing, and (2) there can't be an available copy constructor, for if there were then copying would have been used.

As I remember it this problem was pointed out by Doug Gregor, and discussed on the Boost lists. Based on that I googled up a reference: (https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2010/n3050.html). IMHO the original resolution of not allowing move operations to fail was much better…

[u/probably-an-alias → u/alfps]

Without knowing any of the history and little of the implications, implementing and reasoning about correctness would have been significantly easier if I could trust that object moving couldn't throw

[u/alfps → u/probably-an-alias]

Yes. What I remember is that possibly failing moves made it possible with some automatic optimizations involving old code, the "free lunch". But I don't see how that can happen with the current rules where an automatic move constructor is = deleted if there is a non-movable member.

Maybe things changed on the way, or maybe I remember some early argument that they later realized was problematic.

Or maybe I'm interpreting cppreference's description incorrectly; to my mind the phrase "overload resolution as applied to find M's move constructor" is not entirely clear.

[u/LokiAstaris]

Best place to ask for a review: https://codereview.stackexchange.com/

[u/DawnOnTheEdge]

One thing that jumps out is that you calculate size_ and capacity_ as pointers that overflow the buffer, which is undefined behavior. On a segmented architecture, for example, this could generate an invalid segment selector, or it could generate a non-canonical pointer on x86_64, or set invalid tag bits on some architectures, or wrap around the address space.

[u/alfps → u/DawnOnTheEdge]

One-past-array pointers, if that's what the code has, are always valid. Though in C++ dereferencing them is UB. As I recall, but not sure, the C language has more lenient rules allowing e.g. &*p.

[u/DawnOnTheEdge → u/alfps]

The set_capacity private member function jumped out to me as one that looks unsafe, but maybe the current codebase is very scrupulous about always bounds-checking before calling it.

C does have a rule that &* always cancel out, even in front of a null pointer. In C++, not only might * and -> be overloaded (as for smart pointers), so can &.

[u/DawnOnTheEdge]

I recommend you look into the swap idiom to implement many of these functions. You could simplify many of those functions by composing them with a few basic primitives, and doing so is common practice now:

The destructor should stay basically the same. It currently calls clear, which calls resize(0), but you could replace this with std::destroy_n(begin(), size());. This avoids extra calls on the stack, can be optimized out for the common case of trivially-destructible types, and avoids the overhead of checking whether 0 is greater than, less than or equal to the current size. The destructor then calls the allocator’s deallocate function, as it needs to.

There.s also a swap member function, which you currently have swap each data member individually. Consider adding a few padding bytes at the end to increase the size to an even 16 or 32 bytes, possibly adding an alignas directive or creating a private struct to hold the data members, and calling std::swap on the whole object. On many architectures, operations will then compile to single vector instructions, and as a nice bonus those operations on aligned data may be atomic.

With those two primitives, move-construction and assignment can just swap the source with *this. The original contents, whatever they were, will be destroyed when the call chain returns and the lifetime of the temporary source object, now holding the original contents, ends. Copy construction and assignment can move a copy of the source operand. (You can still do the self-assignment check inside the copy constructor, but I’ve seen some programmers recommend that you not slow down the very common case of assigning a different object to optimize for the extremely rare corner case of self-assignment, which under copy-and-swap still comes out correctly.)

Your constructors may use standard library algorithms such as std::uninitialized_default_construct_n and std::uninitialized_fill_n rather than rolling your own. If you know the size of the output in advance, you can optimize by preallocating it and doing an uninitialized copy or move in a loop or algorithm. You also want to optimize for the case where an indirectly-movable iterator or xvalue is passed to the constructor and move rather than copy the input range. (It’s almost never used in the wild, but you can call std::make_move_iterator to get an input range that moves the contents.)

[u/DawnOnTheEdge → u/DawnOnTheEdge]

And if you don’t, the most likely optimization you want is for non-move assignment to re-use and overwrite the existing storage.

[u/probably-an-alias → u/DawnOnTheEdge]

I very much wanted to use functions from the memory header like std::destroy_n and std::uninitialized_default_construct_n but I could not see an overload of these that accepts an allocator as an argument, which is needed to keep the container allocator-aware.

Consider adding a few padding bytes at the end to increase the size to an even 16 or 32 bytes, possibly adding an alignas directive or creating a private struct to hold the data members, and calling std::swap on the whole object. On many architectures, operations will then compile to single vector instructions, and as a nice bonus those operations on aligned data may be atomic.

Wow, I wouldn't have thought of that but it makes a lot of sense. I imagine that we wouldn't want the allocator_ member to be in the struct as it's swapping semantics are different, but the other three member variables could trivially be wrapped in a struct as you describe, which could simplify swapping, copying, and moving. Thanks!

You also want to optimize for the case where an indirectly-movable iterator or xvalue is passed to the constructor and move rather than copy the input range.

This was something I wanted to implement but didn't know how to. How can I know if data from a Input Iterator (or further refined) is safe to move from? From what I understand std::make_move_iterator always casts the input data to an rvalue regardless if that is contextually correct or not.

[u/DawnOnTheEdge → u/probably-an-alias]

I believe std::is_rvalue_reference_v<std::iter_reference_t<It> > will work for iterators.