Hacker News Reader

Comment by colonwqbang | Hacker News Reader

I find it so strange and unintuitive that a table lookup in STL can actually amend the table to include the key. I don't know of another library that works like that.

    std::map<std::string, std::string> m;
    (void) m["nonexistent"];
    m.size(); // => 1

Is there a historic reason for this strange specification? Or is it just a concession make the "operator=" sugar work better?

View on HN

If you try to implement your own map you’ll naturally end up with this quirk.

operator[] returns a reference to a slot in the map which can be read from or assigned to. Since the reference must be valid, you better have allocated a slot in the map that can be written to if the value didn’t exist.

I don't think it's _that_ unnatural to just return a reference to a dummy value (i.e. have a member T map<T>::dummy and always return that if the key does not exist). Users writing to it/reading from it are on their own; you could even reinitialize it on every such operator[] call.

operator[] is not only used for lookups though, it’s also used for insertions:

    m["nonexistent"] = 1;

This would not work if you return a dummy value.

That's true; thanks! It's 3am and time for bed :-)

This is why I gave up on [] and just use .at now.

Which is perfectly reasonable if you're willing to deal with the performance consequences of exceptions (or crashes).

.find() is the safe way to do map lookup without side effects.

It is a quirk of C++ that element lookup and assignment are forcibly unified like this. Ruby for instance has an operator[]= which could solve the problem.

You could do it in C++ via proxy objects, but are kind of tricky to get right.

They are impossible to get right unless you are OK with things breaking when they get passed to templates. This is why std::vector<bool> is considered a mistake.

C++ really needs an 'operator auto' to properly support proxies :(

"quirk" looks more like "major overlooked detail" to me

I mean, left side expressions and right side expressions are different

Indeed, Rust's HashMap implements Index<&T> but not IndexMut<&T> meaning you can write this:

let salary = salaries["Jim Bob"]; // Note this panics if "Jim Bob" isn't a key in salaries, by analogy to arrays which panic if you do an out-of-bounds array access

However you can't write this, it won't compile:

salaries["Jim Bob"] += 10_000; // No raise for Jim Bob, this does not compile because that's not a mutable reference.

To be fair, you could achieve the same in C++ by only implementing `operator[]() const`.

Huh. Does that do the same thing? I can't figure it out in my head whether this causes all the correct things to fail and everything else to work.

If you only implement operator[]() it should do the same thing as only implementing Index in Rust, thanks to implicit cast conversion. Whether it causes "the correct things to fail and everything else to work" is up to interpretation, as this will give you const references to the array values, which is much less idiomatic in C++ than in rust.

Yeah, I think this probably does what I think ought to happen here, but in the process it probably makes a bunch of reasonable looking C++ not work, and thus would make programmers unhappy which is not a good goal :/

C++ allows you to override the constness of everything internally by defining a member variable as `mutable`.

Unfortunately while C++ does distinguish between things which can appear on the left hand side and right hand side of assignment, the things that can go on the lhs are much broader than in most programming languages. For example, a pretty normal thing to write in C++ is `foo(map) = 1;`, where foo something like `int& foo(std::map<std::string, int>& map) { return map["key"]; }`.

The ability to compute and pass around lvalue references (where "lvalues" are approximately "things that can appear on the lhs of assignment") is a very powerful feature, but also one which causes complexity in all sorts of other places, which is a bit of a theme for C++. One of those complexities is that non-const `operator[]` essentially has to be `operator[]=` even if at this specific call site there's no assignment happening.

C++ could have had const `std::map:::operator[]` throw an exception if the key isn't present, but having const and non-const versions of a function do different things is extremely error-prone and instead you have to use at() if that's what you want.

They're not forcibly unified if you don't use operator overloading. There is a find() and an insert().

I tend to use find() when doing a read only lookup, and operator overloading for writing.

There are two issues with that:

- what is the dummy value? does the value type even have one?

- I don't think index-assignment (or attribute-assignment) is overloadable in C++, so you need `a[b]` to return something which can be assigned to, and proxy values tend to be really wonky (see: `vector<bool>`), so assigning to the result of the indexing would replace the dummy value

Python's defaultdict also behaves like this, inserting the nonexistent entry into the dict:

    from collections import defaultdict
    m = defaultdict(int)
    m["nonexistent"]
    len(m) # => 1

There are examples of the opposite too, though. Ruby's Hash does not insert the entry:

    m = Hash.new(0)
    m["nonexistent"]
    m.length # => 0

Python's defaultdict is aptly named to indicate this behavior (the bare `dict` won't do this). `std::map` isn't.

> There are examples of the opposite too, though. Ruby's Hash does not insert the entry:

It does if you initialise the hash with a block to do so:

    m = Hash.new {|h, k| h[k] = 0}
    m["nonexistent"]
    m.length # => 1

That is, essentially, what defaultdict does. Just through subclassing (because `dict` does not provide such a fallback, but it has a magic method you can override to customise the mapping's behaviour in that case).

this famously introduced bugs into norvig's published code (i forget if it was the sudoku solver or the spell checker) that nobody noticed for years

if norvig isn't smart enough to use defaultdict without introducing bugs then i'm not either

iirc it was the spellchecker. My memory is fuzzy and unreliable but what it's claiming is that the first version on his webpage had that bug, he fixed it, and later I pointed out another bug of the same type. Or something like that!

(I am sure I never reported anything about the sudoku solver, since I never studied it.)

thanks!

Isn't that pretty common? The [] operator acts like find or insert default value, so you can do nice things like ++map[key]. The map.find(key) works if you don't want to insert, it will return map.end() if the key couldn't be found.

My only gripe with find() is that you can't do `if (auto it = map.find(key))`. Otherwise yes, that's the way.

At least you can do `if (auto it = map.find(key); it != map.end())` since C++17.

I didn't know that was possible, thanks. It's worse than in other languages imo but better than the existing C++ alternatives, I will use it.

> Isn't that pretty common?

AFAIK basically just 3 wide-spread languages which do this, and they're all known for their idiosyncratic behaviour: C++, Perl, and PHP.

A few languages provide this as opt-in via a subtype (Python's defaultdict) or init (Ruby's Hash.new with a block parameter).

Some more will do it via an opt-in callsite API e.g. Python's `setdefault`, Java's `computeIfAbsent`, Rust's `entry` API.

perl only does this in some cases; unlike with std::map, this is safe:

   my $x = $h{$v};

this is not safe because it autovivifies $h{$v} as an ARRAY ref:

   my $x = $h{$v}[$i];

with respect to idiosyncratic behavior, if a language doesn't have idiosyncratic behavior, it has no reason to exist; it's just gratuitously incompatible syntax for already-available semantics

Yes.

Especially annoying when looking up something in a const& map.

The alternative approach could have been to make operator[]= and operator[] different.

You couldn't quite do that, because C++ has compound operators, and they can of course be overloaded, so:

foo[bar] += baz;

... needs to provide operator+= with a mutable reference to foo[bar], and a maybe immutable reference to baz.

So does C#, and it simply desugars the above into (foo[bar] = foo[bar] + baz), except that "foo" and "bar" are only evaluated once.

In what version of C# do you believe C# gained overloading for the compound assignment operators ? The latest Microsoft documentation I could find claims these operators cannot be overloaded.

It was always present. The reason for the claim in the docs is because they cannot be overloaded by themselves, only indirectly via overloading the binary operators that they're syntactic sugar for.

https://learn.microsoft.com/en-us/dotnet/csharp/language-ref...

Which is actually better than C++ in more than one way. As a library author, you overload a+b, and you get a+=b for free. As a user, you know that a+=b always means the same thing as a=a+b (except for side effects) regardless of the library.

Similarly, you can't overload && and || in C# directly like you can in C++, but instead you overload "operator true" and "operator false", and you get the boolean ops consistently derived from that (which means that they can short-circuit properly when overloaded, unlike in C++).

I agree that the consistency is nice, but it does mean we would end up paying twice for a hash lookup in this context, the sub-expressions are only evaluated once but the actual lookup must be performed both by the getter and the setter.

  salaries["Jim Bob"] += 10_000;

Calls the getter on salary to look up "Jim Bob", it finds maybe he's currently on 80_000, returns 80_000, we add 10_000 to that, getting 90_000 and then we call the setter on salary asking it to write 90_000 to "Jim Bob". Two lookup operations.

It's also deeply unfortunate here that C# thinks "null" is both a plausible value for common types and a good way to distinguish lookup failure. So it's possible either that Jim Bob's salary literally is null for some insane reason or that Jim Bob wasn't on the payroll, and the effects here are identical.

The extra lookup would not be acceptable in C++ or Rust, though that feels much more reasonable in a language like C# or Go -- paying a little performance to buy nicer ergonomics. The needlessly dangerous API shape on the other hand is very C++ and ought not to exist in C#.

C# does not attach any special meaning to null in the context of lookup, nor does it allow it by default even for reference types (assuming that you're compiling with nullability checks on, which has been the default for years), so I'm not quite sure what you're referring to. The standard way to indicate a failed lookup in C# is to throw an exception.

But, yes, it is true that you end up needing double lookup when combining compound assignment with indexing.

> C# does not attach any special meaning to null in the context of lookup

Lots of C# APIs do, in fact return null from Index (ie the [] operator) for "Not found", you're clearly writing much newer .NET code and so you're using a modern generic container which can't do this (because its return type can't be null)

> nor does it allow it by default even for reference types (assuming that you're compiling with nullability checks on, which has been the default for years)

My emphasis. I believe the default you're talking about starts in .NET 6 in late 2021. I don't think "since late 2021" qualifies as "for years".

C# Code I write from scratch does have nullability checks because I'd prefer to be in a language where "Null reference" isn't a thing, and this is as close as C# gets - but I maintain tonnes of code that was written three, five, even ten years ago.

I've been writing C# code since 2002, when .NET 1.0 first came out. "Modern generic collections" have been around since .NET 2.0 - that's 2005, so almost 18 years now. Their use was already pervasive by 2010, in my experience. Just about the only place where I can think of finding old-style patterns like returning nulls is WinForms and WebForms APIs from that same era that implemented the non-generic interfaces like IDictionary, and which can't be changed for backwards compatibility reasons.

I stand corrected on the timeline for nullable reference types being the default - for some reason I remembered it as being on by default for new projects since VS 2019.

operator[] is indeed not great, the semantics are too surprising for such a short-hand notation.

  auto [it, newly_created] = m.try_emplace(key);

Does the same, and gives back more information. For something like `m[key] = value`, you can do `m.insert_or_assign(key, value)`, and save the default construction + assignment when the key was not there.

For ordinary lookup you don't want to randomly mutate the map anyway. If your reference to the map is const, you can't use operator[] anyway, fortunately. However `m.at(key)` is not great either when the key not being present is really not exceptional, and the dance with `m.find(key)` is often not too ergonomic. I still suggest to just use `find` here.

Lookup is map.at() (throws on invalid element), you can use map.contains() since c++20 or map.find()!=map.end() to see if the element exists beforehand.

operator[] does more than lookup, but there are other functions for the other stuff. It should be pretty clear...?

Things can be clear while still being unintuitive :)

Comparing to other languages I know, I couldn't think of another where collection[key] denotes insertion.

The historic reason is that in C, [] on arrays is defined as returning an lvalue on which assignment then operates - that is, they have always been separate things, and there was no operator []= or anything like that to define semantics of array assignment in a single operation.

C++ simply generalized this model to all collections, in line with the overall "better C" design. But then for maps it means that [] has to proactively create an entry if you want []= to work like it does everywhere else.

Similarly, C++ iterators are generalized C pointers, which is also not an ideal abstraction in practice (and why few other languages do it that way).

I (and many other C++ programmers), on the other hand, I'm always annoyed and surprised that dictionaries on other languages do not have default insert on lookup.

It is just very convenient (hence the existence of defaultdict in python).

Insert on lookup is convenient but encourages either double-lookup patterns (contains + get) or unintentional inserts. I very much like Python's setdefault -- except for its 10-chars name.

Well, STL encourages an iterator centric approach, so:

  if(auto i = x.find(y); i!=x.end()){ 
      // use i->{first,second}
  }

Also ideally you should be able to do this:

  for(auto [key, value]: x.equal_range(y)) { 
     
  }

But infuriatingly, x.equal_range returns a pair instead of some range view so you need some additional infrastructure (either convert the result of equal range into a range or add some begin/end overloads for pair).

My C++ is a bit rusty (no puns intended), I didn't know your first syntax was possible now (another comment states it comes from C++17), that's much nicer than the alternative that pollutes the scope indeed. Having to repeat both x and i is unfortunate, but that's par for the course with C++ iterators.

The equal_range solution looks nice from a genericity perspective (look ma I do multimaps!) but is really unintuitive with regular maps imo. Unless I'm mistaken it also does not allow an else branch for when the value is not there, which is often needed.

A for-else a-la Python would actually be generally useful!

Hopefully one day we will get proper patter matching and destructing in if statements (Herb Sutter has made significant progress on this).

For-else could be useful, but I don't think Python's semantics would actually help here? Python's for-else runs when the for loop did not break (even if nonempty), but what would be needed here would be to run when the for loop was empty, which is a different condition.

cpp2 is both interesting and ambitious, I really hope it gets somewhere.

Indeed, I misremembered the semantics of for-else! I don't think I have actually used it in python :)

Yeah for-else as implemented in Python is... not actually that useful. It's the right tool to inline std::find_if and that's basically it. I think the behavior you had in mind would actually be more intuitive and more useful.

OTOH, try...else I find myself missing at times.

You need both access patterns (otherwise you do a double-lookup to insert a default value) and C++ already provides both.

Whatever is implemented by operator[] in a given language is going to be implicitly encouraged by the language, and that's what most novices will use.

This was written at a time when std::option didn't exist. Thus it needed to return T& instead of option<T&>. When std::option was added, they couldn't change the existing interface because of back compat and the lack of a migrator tool (e.g. Swift has major backwards incompatible source changes but they have a tool that will migrate your code fore you). C++ has warts like this all over the place.

optional<T &> is not valid in C++ [1]

[1]: https://en.cppreference.com/w/cpp/utility/optional

Because C++ doesn't have the Guaranteed Niche Optimization C++ optional<T&> would be pretty miserable whereas Rust's Option<&T> is exactly what you want.

In practice C++ APIs where you'd naturally write Option<&T> use pointers and are consequently easier to use wrong, this is an example of Rust actually providing improved safety technology (whereas many commonly identified safety differences like bounds checking in Rust are cultural differences)

C++ could specify that std::optional<T&> is valid and implementations could implement the Guaranteed Niche Optimizations. This is not a theoretical possibility: boost.optional (which std::optional is based on) does exactly that.

The reason std::optional doesn't allow references is because someone in the commitee objected that some users might be confused by the assignment semantics (will assignment rebind or assign through the reference?) and the proposal authors dropped it instead of spending too long discussing pro and cons. It can still be easily re-added if the commitee wants to.

No need to drag the rust in the discussion.

I'm pretty sure you can't express the actual guarantee in C++ because of inadequacy in the design of the C++ type system, which has caused problems elsewhere recently too.

You could easily hack std::optional<T&> specifically - and several people have, not just Boost - however C++ has a long history of "clever" hacked specializations that turn out to be disastrous so that isn't attractive. It's called generic programming for a reason.

The fact that it looks like you might be able to rebind or assign through the reference is a design goof. To the extent that std::optional is just the Boost type with a sticker on, that's a goof by the people behind the Boost type. However, they were hemmed in by inadequate language functionality, WG21 has the option to go fix the language, and they didn't do that, so the blame for that goes to them and not Boost. Having now standardised std::optional with the design goof, there is no attractive route forward.

The correct answer to "someone's" question by the way should be neither and that's the goof in std::optional, assignment to a Maybe type is assignment to the Maybe type you can't assign a Foo to a Maybe<Foo>, imagine if C++ also thought this ought to work for std::vector<int> ...

> I'm pretty sure you can't express the actual guarantee in C++ because of inadequacy in the design of the C++ type system, which has caused problems elsewhere recently too.

Far from being inadequate, it is pretty trivial to do so: https://gcc.godbolt.org/z/n4vK4jeaG .

You still need to special-case references because they are not actual C++ objects and need special handling.

It's not about whether you can implement this hack - obviously numerous people have done that - it's about the type system itself.

Here's a question for you, what is the type of a do expression which just returns from the function you're in ? I mean, it's just an expression, we don't have to actually evaluate it we can ask what the type is... can't we ?

As far as I can see, C++ does not have a suitable type, which is why e.g. some C++ functions end up with a special attribute to signify that they won't actually return. I can see why this type would be unsettling, it's like when the ancient Greeks didn't like zero and so they initially refused to treat it as an integer. The type you want here is the additive identity.

Because the type system doesn't really understand additive identity, it's a struggle to write such a guarantee - not as a hack but in the type system.

I'm sorry, but I have no interest in playing a game of True Scotsman Chases The Goalpost.

Even if I did, I have no idea what you are trying to say.

edit: sorry that was a bit harsh. Can you try to explain what property is C++ missing exactly to implement the Niche optimization? I suspect you are trying to say that C++ lacks proper sum types (which is true), but that's really orthogonal to the optimization.

I don't think it is orthogonal, because it means we have to resort to this hack everywhere and we already know that specialization hacks end badly. Let me briefly explain why I've thought about this pretty hard.

Over in Rust I really want to make BalancedI8, BalancedI16 and so on, types which are exactly the same as the ordinary signed integers of each size, except, their smallest possible value (e.g. i8::MIN ie -128) is gone (so BalancedI8::MIN is -127), leaving them nicely balanced between negative and positive, their abs() method doesn't have a hidden surprise - and of course this offers the smallest possible niche so Option<BalancedI8> fits in a single byte.

I obviously can in some sense do that today and I did -- the types are published, but today I can't use them from stable Rust, these types require a (deliberately permanently unstable) Rust-internal attribute telling the compiler about the niche, and they also can't be safely constructed (obviously I provide a safe function to make one, but you can't just conjure one into existence without calling the function, yes it gets inlined but that's not very ergonomic)

This is not a desirable state of affairs. As usual in Rust, the reason for the perma-unstable feature flag is that there's a germ of an idea of the Right Thing™ and so the eventual removal of the feature flag is predicated on obsoleting the feature by having the Right Thing™ in the language itself, not stabilization of the existing flag. Rust types which provide a niche will some day remove the feature flag and instead be defined using the language in the now-natural way, yet to end users nothing seems to have changed. The backwards incompatible change lives only inside private internals of the standard library so it's fine.

In this case that Right Thing turns out to be Pattern Types. What if we actually just tell the type system what's going on here about which values a type can actually have versus which ones are niches by providing a Pattern for the type. So it knows everywhere in the language that -128 may be a valid i8 but it's not a valid BalancedI8 because the pattern doesn't match.

However, Pattern Types might take quite a while to produce even a basic MVP implementation that can be stabilized, and so for a while I was pushing to get some way to just have what I want stabilized, sooner - without all of Pattern Types, and then replace it later using Pattern Types. But I was persuaded that actually this is poison, if you introduce my hack as a stable feature then it cannot ever actually be translated into a Pattern Type in user's code, so it becomes this weird orphan feature, "tialaramex's stupid niche type hack" forever even though all new types would use Pattern Types to achieve a much superior outcome, there's no known way to fix any of my hacked types.

So in effect you're making the arguments I was making like a month ago, that I now see are hopeless, which is why I'm asserting so vigorously that this is just a hack and what you should aim for instead is to explain to the type system what's going on even though that's harder.

The question about decltype ( do { return; } ) is pertinent because that type is to a type system like zero is to the integers in Z. I hope I spelled that correctly - I can't Godbolt it because do expressions are a speculative design, but hopefully you get the idea. This problem is easier to express with a do expression than with other C++ where the same problem arises but is harder to exhibit.

Thanks for elaborating on this, now I understand your thoughts. I wanted to write a longer answer, but life got in the middle. So I'll just say:

If rust devs do not want to add a specialization or traits for this feature and wait for the Right Thing it is fine. It is such a niche (get it?) requirement that it is not worth polluting the standard library.

But if you really need it as an user, I don't think the trait solution is an hack at all. I don't see specialization as an hack in general and in fact is important for writing efficient code.

Ideally you would be able to encode every possible property of your program elegantly and generically in the type system while keeping the language lean, fast and easy to understand. In practice at any point in time only a language will only have a finite subset of features and an user can't wait forever for the language to reach perfection. Any 50+ year language will necessarily accumulate cruft. Embrace it. Worse is better.

> It can still be easily re-added if the commitee wants to.

Yes but the earliest that could happen is, like, 2026 or perhaps 2027. Because you have to wait for both a new std revision to become available.

Reply on news.ycombinator.com