Chromium Code Reviews
|
|
Chromium Code Reviews
Issue
2715433007:
Add a flat_map container (Closed)
DescriptionAdd a flat_map container.
This works the same as flat_set but corresponding to a std::map.
The existing flat_set implementation was factored into a base class called flat_tree with a provision to have a potentially different lookup key type than value type, and a way to convert from a value to a key. flat_set and flat_map can be trivially implemented on top of this API.
The existing flat_set tests are moved to flat-tree and some simple type-specific tests were created for the set and map derivations.
flat_tree no longer copies the comparison object except when required (when returned by value_comp()). But this requires that the comparison functor be const which was not the case before.
Review-Url: https://codereview.chromium.org/2715433007
Cr-Commit-Position: refs/heads/master@{#458796}
Committed: https://chromium.googlesource.com/chromium/src/+/9816813a28b7f20ef03ff69d901d3b9a891f0400
Patch Set 1 : Base for review #Patch Set 2 : New #
Total comments: 18
Patch Set 3 : Fix #
Total comments: 15
Patch Set 4 : Review comments #Patch Set 5 : Posix #Patch Set 6 : Fixes #
Total comments: 4
Patch Set 7 : Remove noexcept #Patch Set 8 : Comments #
Total comments: 3
Patch Set 9 : Merge and unsafe_emplace #Patch Set 10 : Fix EraseIf #
Total comments: 13
Patch Set 11 : Review comments #
Total comments: 1
Patch Set 12 : Nit #
Total comments: 10
Patch Set 13 : Comments #
Total comments: 2
Messages
Total messages: 123 (61 generated)
Set tests pass:
Description was changed from ========== flat_tree BUG= ========== to ========== Add a flat_map container. This works the same as flat_set but corresponding to a std::map. The existing flat_set implementation was factored into a base class called flat_tree with a provision to have a potentially different lookup key type than value type, and a way to convert from a value to a key. flat_set and flat_map can be trivially implemented on top of this API. The existing flat_set tests are moved to flat-tree and some simple type-specific tests were created for the set and map derivations. ==========
Patchset #1 (id:1) has been deleted
Patchset #1 (id:20001) has been deleted
Patchset #1 (id:40001) has been deleted
Patchset #1 (id:60001) has been deleted
Description was changed from ========== Add a flat_map container. This works the same as flat_set but corresponding to a std::map. The existing flat_set implementation was factored into a base class called flat_tree with a provision to have a potentially different lookup key type than value type, and a way to convert from a value to a key. flat_set and flat_map can be trivially implemented on top of this API. The existing flat_set tests are moved to flat-tree and some simple type-specific tests were created for the set and map derivations. ========== to ========== Add a flat_map container. This works the same as flat_set but corresponding to a std::map. The existing flat_set implementation was factored into a base class called flat_tree with a provision to have a potentially different lookup key type than value type, and a way to convert from a value to a key. flat_set and flat_map can be trivially implemented on top of this API. The existing flat_set tests are moved to flat-tree and some simple type-specific tests were created for the set and map derivations. flat_tree no longer copies the comparison object except when required (when returned by value_comp()). But this requires that the comparison functor be const which was not the case before. ==========
New
new
New
brettw@chromium.org changed reviewers: + danakj@chromium.org, dyaroshev@yandex-team.ru
Patchset #4 (id:140001) has been deleted
Patchset #2 (id:100001) has been deleted
Patchset #2 (id:120001) has been deleted
I was doing some container research and we also want to experiment with this class for base::Value dictionaries in the context of a refactor we're doing there. INSTRUCTIONS FOR REVIEWING First look at flat_tree.h. The diff from PS1 will show you what has changed from the existing flat_set (flat_tree.h in PS1 is a copy of flat_set.h with the strings "flat_set" changed "flat_tree", so you will only see functional changes). Then look at flat_set.h. this just changes it to forward to flat_tree and should be straightforward. Then look at flat_map.h. The diff from PS1 will show you what changed from the NEW flat_set.h above (flat_map.h in PS1 is the new flat_set.h implementation from the previous review step). Note the change in const requirements for the comparator I mentioned in the CL description. If you think this is wrong I'm happy to change it back, I can't tell which is better. The way it's structured as a base class it needs to be either const or copied to be usable from const member functions. In practice the copies won't matter much since comparison functors won't have member data.
The CQ bit was checked by brettw@chromium.org to run a CQ dry run
Dry run: CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...
The CQ bit was unchecked by commit-bot@chromium.org
Dry run: Try jobs failed on following builders: android_cronet on master.tryserver.chromium.android (JOB_FAILED, https://build.chromium.org/p/tryserver.chromium.android/builders/android_cron...) ios-device on master.tryserver.chromium.mac (JOB_FAILED, http://build.chromium.org/p/tryserver.chromium.mac/builders/ios-device/builds...) ios-device-xcode-clang on master.tryserver.chromium.mac (JOB_FAILED, http://build.chromium.org/p/tryserver.chromium.mac/builders/ios-device-xcode-...) ios-simulator-xcode-clang on master.tryserver.chromium.mac (JOB_FAILED, http://build.chromium.org/p/tryserver.chromium.mac/builders/ios-simulator-xco...)
The CQ bit was checked by brettw@chromium.org to run a CQ dry run
Dry run: CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...
The CQ bit was unchecked by commit-bot@chromium.org
Dry run: Try jobs failed on following builders: cast_shell_linux on master.tryserver.chromium.linux (JOB_FAILED, http://build.chromium.org/p/tryserver.chromium.linux/builders/cast_shell_linu...)
Really glad that you've decided to do this! >But this requires that the comparison functor be const >which was not the case before. Well stl allows for non const operator() as long as it acts like it and this design does not. And there are still going to be copies when you call algorithms. However this is a minor thing and if you think that avoiding this copy is benefitial, I'm ok with it. My main conscern is: have you thought of possibly reducing code size? You can use inheritance/typedefs or (I'm not 100% sure that it's possible) implement flat_map in terms of flat_set? https://codereview.chromium.org/2715433007/diff/160001/base/containers/flat_m... File base/containers/flat_map.h (right): https://codereview.chromium.org/2715433007/diff/160001/base/containers/flat_m... base/containers/flat_map.h:16: // sorted containers that stores it's elements in contiguous memory (current Nit: Is plural intentional? https://codereview.chromium.org/2715433007/diff/160001/base/containers/flat_m... base/containers/flat_map.h:23: // Maybe we want to mention stbility here explicitly, since it's ore important for maps? It maybe a hard bug to find: base::flat_map<int, string> my_map{{0, "a"}, {1, "b"} {1, "c"}} assert(my_map[1] == ...) // we don't have guaranties here. https://codereview.chromium.org/2715433007/diff/160001/base/containers/flat_m... base/containers/flat_map.h:76: // length). Unfortunatly, this comment has to be updated to just say O(N * log(N)) + O(N). I've replaced std::stable_sort with std::sort, because we decided that stability of a constructor is very rarely a requirement but I forgot to update the comment. https://codereview.chromium.org/2715433007/diff/160001/base/containers/flat_m... base/containers/flat_map.h:160: mapped_type& operator[](key_type&& key); Wouldn't at be useful as well? We can do CHECK in it https://codereview.chromium.org/2715433007/diff/160001/base/containers/flat_m... base/containers/flat_map.h:223: // does. Implementation note: currently we use operator==() and operator<() on This code won't change - you use opertors on the tree. not on the underlying type. https://codereview.chromium.org/2715433007/diff/160001/base/containers/flat_m... base/containers/flat_map.h:421: // creating a temporary value. This commemt refers to implementation, so it should probably only reflect situation with operator[] and at https://codereview.chromium.org/2715433007/diff/160001/base/containers/flat_t... File base/containers/flat_tree.h (right): https://codereview.chromium.org/2715433007/diff/160001/base/containers/flat_t... base/containers/flat_tree.h:14: // use directly. We have a significant amount of comments duplication. Maybe a md file would be better (like for base callback)? https://codereview.chromium.org/2715433007/diff/160001/base/containers/flat_t... base/containers/flat_tree.h:39: class value_compare : public key_compare { Will it work to prediclare it? Or mabe to declare it as in some sort of helper before class? https://codereview.chromium.org/2715433007/diff/160001/base/containers/flat_t... base/containers/flat_tree.h:70: // length). See the comment in flat_map https://codereview.chromium.org/2715433007/diff/160001/base/containers/flat_t... base/containers/flat_tree.h:106: // reserve() and shrink_to_fit() invalidate iterators and references. We have a significant amount of comments duplication. Maybe we should do an md file instead (like for callback https://cs.chromium.org/chromium/src/docs/callback.md?q=callbac+package:%5Ech... https://codereview.chromium.org/2715433007/diff/160001/base/containers/flat_t... base/containers/flat_tree.h:299: } impl_; I recently learned that a recommended way of doing empty class optimisation is via using std::tuple. Want to change this too maybe? https://codereview.chromium.org/2715433007/diff/180001/base/containers/flat_m... File base/containers/flat_map.h (right): https://codereview.chromium.org/2715433007/diff/180001/base/containers/flat_m... base/containers/flat_map.h:40: class flat_map { It seems that inheritig from a flat tree would make a lot of code go away. Wouldn't that be better? https://codereview.chromium.org/2715433007/diff/180001/base/containers/flat_m... File base/containers/flat_map_unittest.cc (right): https://codereview.chromium.org/2715433007/diff/180001/base/containers/flat_m... base/containers/flat_map_unittest.cc:24: class MoveOnly { Can we maybe move it to some common location? Or, perhaps, merge flat_mat tests into flat_set tests. https://codereview.chromium.org/2715433007/diff/180001/base/containers/flat_s... File base/containers/flat_set.h (right): https://codereview.chromium.org/2715433007/diff/180001/base/containers/flat_s... base/containers/flat_set.h:83: class flat_set { Wouldn't just a using declarition do the trick?
https://codereview.chromium.org/2715433007/diff/180001/base/containers/flat_m... File base/containers/flat_map.h (right): https://codereview.chromium.org/2715433007/diff/180001/base/containers/flat_m... base/containers/flat_map.h:440: } As written this seems to do an extra check (in insert). I think that in case of a complex Compare compiler might not be able to eliminate it. How about some form of a hook from a tree?
On 2017/02/24 22:55:49, dyaroshev wrote: > My main conscern is: have you thought of possibly reducing code size? You can > use inheritance/typedefs or (I'm not 100% sure that it's possible) implement > flat_map in terms of flat_set? Ok, I thought about it and it seems like implementing flat_map as flat_set<std::pair<key_type, value_type>, clever_compare> should work, except you need to implement templated versions of some methods from C++14 crbug.com/682254 and base::less<> which is a good thing. * most of the methods - plain forwarding to set methods. * count/find/equal_range/lower_bound/upper_bound forward to templated version of set operations. * erase(key_type) - unfortunately just equal_range + erase - no way around it, std::set does not have a templated version of erase. I guess this is because of complex overloading for this function. For operator[]/at you would still need some form of a hook. I think it would be a great idea to expose some unsafe api to everybody, however while we are not settled on it, I think a friend declaration is ok. On metaprogramming: In case you don't know how to implement is_transparent trait, there is a wonderful void_t trick. https://godbolt.org/g/mJ3AU0 Btw: in C++17 they've added an overload of erase(iterator) - this is a fix to: http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-defects.html#2059 and maybe we can do it in this patch too. A test for it can be found in libc++ tests: https://github.com/llvm-mirror/libcxx/blob/master/test/std/containers/associa... Maybe we can do it in this patch too?
https://codereview.chromium.org/2715433007/diff/180001/base/containers/flat_t... File base/containers/flat_tree.h (right): https://codereview.chromium.org/2715433007/diff/180001/base/containers/flat_t... base/containers/flat_tree.h:83: flat_tree(flat_tree&&); I recently realised, that this won't be noexcept. Because noexcept for move operations is important - please add it. https://codereview.chromium.org/2715433007/diff/180001/base/containers/flat_t... base/containers/flat_tree.h:217: void swap(flat_tree& other); Both swaps should also be declared noexcept.
New snap up. I implemented flat_set as a typedef and flat_map as a derived class. This removed a lot of the code. I originally did it as the member variable because both boost and MSVC's STL did something similar. But I don't see much benefit in doing that. I'd rather keep the C++17 anbd tuple enhancements you suggested as a future work item. https://codereview.chromium.org/2715433007/diff/160001/base/containers/flat_m... File base/containers/flat_map.h (right): https://codereview.chromium.org/2715433007/diff/160001/base/containers/flat_m... base/containers/flat_map.h:16: // sorted containers that stores it's elements in contiguous memory (current On 2017/02/24 22:55:48, dyaroshev wrote: > Nit: > Is plural intentional? Done. https://codereview.chromium.org/2715433007/diff/160001/base/containers/flat_m... base/containers/flat_map.h:23: // On 2017/02/24 22:55:48, dyaroshev wrote: > Maybe we want to mention stbility here explicitly, since it's ore important for > maps? > > It maybe a hard bug to find: > base::flat_map<int, string> my_map{{0, "a"}, {1, "b"} {1, "c"}} > assert(my_map[1] == ...) // we don't have guaranties here. I mentioned this in the constructor comment (I think this is the only place where this issue comes up). https://codereview.chromium.org/2715433007/diff/160001/base/containers/flat_m... base/containers/flat_map.h:76: // length). Done, I updated the comment. https://codereview.chromium.org/2715433007/diff/160001/base/containers/flat_m... base/containers/flat_map.h:160: mapped_type& operator[](key_type&& key); On 2017/02/24 22:55:48, dyaroshev wrote: > Wouldn't at be useful as well? We can do CHECK in it Done. https://codereview.chromium.org/2715433007/diff/160001/base/containers/flat_m... base/containers/flat_map.h:223: // does. Implementation note: currently we use operator==() and operator<() on On 2017/02/24 22:55:48, dyaroshev wrote: > This code won't change - you use opertors on the tree. not on the underlying > type. Yeah, I just removed this part of the comment. https://codereview.chromium.org/2715433007/diff/160001/base/containers/flat_m... base/containers/flat_map.h:421: // creating a temporary value. On 2017/02/24 22:55:48, dyaroshev wrote: > This commemt refers to implementation, so it should probably only reflect > situation with operator[] and at Done. https://codereview.chromium.org/2715433007/diff/180001/base/containers/flat_m... File base/containers/flat_map.h (right): https://codereview.chromium.org/2715433007/diff/180001/base/containers/flat_m... base/containers/flat_map.h:306: tree_ = ilist; I changed this to use std::move which I think is correct. Do you agree? https://codereview.chromium.org/2715433007/diff/180001/base/containers/flat_m... base/containers/flat_map.h:440: } Good catch! I added a protected helper function to tree to do this. https://codereview.chromium.org/2715433007/diff/180001/base/containers/flat_s... File base/containers/flat_set.h (right): https://codereview.chromium.org/2715433007/diff/180001/base/containers/flat_s... base/containers/flat_set.h:83: class flat_set { Interesting, I hadn't thought of that! The only thing in practice that this will be is that with the using flat_set::value_compare will be the weird wrapped Compare rather than the original template parameter. In some obscure case this might be surprising (and you have a test for that), but I think the simplicity of the using approach is better overall. I'll do that. https://codereview.chromium.org/2715433007/diff/180001/base/containers/flat_t... File base/containers/flat_tree.h (right): https://codereview.chromium.org/2715433007/diff/180001/base/containers/flat_t... base/containers/flat_tree.h:83: flat_tree(flat_tree&&); On 2017/02/27 07:26:39, dyaroshev wrote: > I recently realised, that this won't be noexcept. Because noexcept for move > operations is important - please add it. The style guide says don't do noexcept https://google.github.io/styleguide/cppguide.html#Exceptions since we should be compiling without exceptions anyway. Is there a practical difference in this case?
The CQ bit was checked by brettw@chromium.org to run a CQ dry run
Dry run: CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...
The CQ bit was unchecked by commit-bot@chromium.org
Dry run: Try jobs failed on following builders: android_cronet on master.tryserver.chromium.android (JOB_FAILED, https://build.chromium.org/p/tryserver.chromium.android/builders/android_cron...) cast_shell_linux on master.tryserver.chromium.linux (JOB_FAILED, http://build.chromium.org/p/tryserver.chromium.linux/builders/cast_shell_linu...) ios-device-xcode-clang on master.tryserver.chromium.mac (JOB_FAILED, http://build.chromium.org/p/tryserver.chromium.mac/builders/ios-device-xcode-...) ios-simulator-xcode-clang on master.tryserver.chromium.mac (JOB_FAILED, http://build.chromium.org/p/tryserver.chromium.mac/builders/ios-simulator-xco...)
Posix
Posix
Patchset #5 (id:220001) has been deleted
The CQ bit was checked by brettw@chromium.org to run a CQ dry run
Dry run: CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...
The CQ bit was unchecked by commit-bot@chromium.org
Dry run: This issue passed the CQ dry run.
On brettw said: I implemented flat_set as a typedef and flat_map as a derived class. This removed a lot of the code. I originally did it as the member variable because both boost and MSVC's STL did something similar. But I don't see much benefit in doing that. == Well, it's my understanding they do it for the multiset. I don't see much use in it too. ============================= I'd rather keep the C++17 anbd tuple enhancements you suggested as a future work item. == Well then we could get rid off flat_tree, wich I think is nice. It doesn't seem that hard - I mean - all the tests for sets are in. You would have do more or less this: https://godbolt.org/g/vtE40Q And we would not have to have an extra class. If you think this is too much, I understand. https://codereview.chromium.org/2715433007/diff/160001/base/containers/flat_m... File base/containers/flat_map.h (right): https://codereview.chromium.org/2715433007/diff/160001/base/containers/flat_m... base/containers/flat_map.h:23: // On 2017/02/27 19:20:15, brettw (plz ping after 24h) wrote: > On 2017/02/24 22:55:48, dyaroshev wrote: > > Maybe we want to mention stbility here explicitly, since it's ore important > for > > maps? > > > > It maybe a hard bug to find: > > base::flat_map<int, string> my_map{{0, "a"}, {1, "b"} {1, "c"}} > > assert(my_map[1] == ...) // we don't have guaranties here. > > I mentioned this in the constructor comment (I think this is the only place > where this issue comes up). Assigment too. Well, I think it's an important usability aspect but I'm ok with whatever you decide. https://codereview.chromium.org/2715433007/diff/180001/base/containers/flat_m... File base/containers/flat_map.h (right): https://codereview.chromium.org/2715433007/diff/180001/base/containers/flat_m... base/containers/flat_map.h:306: tree_ = ilist; On 2017/02/27 19:20:15, brettw (plz ping after 24h) wrote: > I changed this to use std::move which I think is correct. Do you agree? I don't think it will work - I'm not 100% sure. Initilizer lists are wiered, they can be put in static memory, they are always const etc. In libc++ std::initilizer_list is just a pointer and a size: https://github.com/llvm-mirror/libcxx/blob/master/include/initializer_list#L61 So this won't do anything. My main argument not to do this would be that I've spent about 20 minutes online and haven't found a single example where somebody was doing it. https://codereview.chromium.org/2715433007/diff/180001/base/containers/flat_t... File base/containers/flat_tree.h (right): https://codereview.chromium.org/2715433007/diff/180001/base/containers/flat_t... base/containers/flat_tree.h:83: flat_tree(flat_tree&&); On 2017/02/27 19:20:15, brettw (plz ping after 24h) wrote: > On 2017/02/27 07:26:39, dyaroshev wrote: > > I recently realised, that this won't be noexcept. Because noexcept for move > > operations is important - please add it. > > The style guide says don't do noexcept > https://google.github.io/styleguide/cppguide.html#Exceptions > since we should be compiling without exceptions anyway. Is there a practical > difference in this case? Sorry, can't do link to the section - chromium style guide says it's ok https://chromium-cpp.appspot.com Well, we have the issue of move_if_noexcept in vectors - so if you do not have a noexcept on your move operations - the vector might copy the elements on resize. I'm not 100% sure what happens if your type is moveonly but not noexpect_movable, but it's a known issue. Noexcept has some compilation problems on android, maybe the operations will have to be inlined in the body of class. If you are not comfortable with this suggestion - feel free to ignore it.
On 2017/02/27 22:23:38, dyaroshev wrote: > On brettw said: > ============================= > > I'd rather keep the C++17 anbd tuple enhancements you suggested as a future work > > item. > > == > > Well then we could get rid off flat_tree, wich I think is nice. > > It doesn't seem that hard - I mean - all the tests for sets are in. > > You would have do more or less this: https://godbolt.org/g/vtE40Q > > And we would not have to have an extra class. If you think this is too much, I > understand. > On the other hand - - you would have to redeclare many methods. Maybe the flat_tree base class is better and somewhat clearer. Ok - I'm willing to drop this.
Fixes
The CQ bit was checked by brettw@chromium.org to run a CQ dry run
Dry run: CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...
New snap up. I actually started implementing map on top of set. I found it challenging and I wasn't happy implementing some templatized versions on set that didn't exist in STL. This is why I studied what other implementations do and ended up with a tree member. But I think the current derivation version is the shortest and cleanest of all of them. Were you suggesting that I make the sorting stable? I wasn't 100% clear on this. I didn't do this change. I suspect we may want to revisit how these get merged and added to in bulk, and may want to revisit this at that point. It's easy to go from unstable to stable, but hard to do the reverse. https://codereview.chromium.org/2715433007/diff/180001/base/containers/flat_m... File base/containers/flat_map.h (right): https://codereview.chromium.org/2715433007/diff/180001/base/containers/flat_m... base/containers/flat_map.h:306: tree_ = ilist; Okay, removed. https://codereview.chromium.org/2715433007/diff/180001/base/containers/flat_t... File base/containers/flat_tree.h (right): https://codereview.chromium.org/2715433007/diff/180001/base/containers/flat_t... base/containers/flat_tree.h:83: flat_tree(flat_tree&&); I added noexcept to the moves and swaps. https://codereview.chromium.org/2715433007/diff/180001/base/containers/flat_t... base/containers/flat_tree.h:217: void swap(flat_tree& other); On 2017/02/27 07:26:39, dyaroshev wrote: > Both swaps should also be declared noexcept. Done.
On 2017/02/28 18:05:59, brettw (plz ping after 24h) wrote: > New snap up. > > I actually started implementing map on top of set. I found it challenging and I > wasn't happy implementing some templatized versions on set that didn't exist in > STL. This is why I studied what other implementations do and ended up with a > tree member. But I think the current derivation version is the shortest and > cleanest of all of them. > Ok. > Were you suggesting that I make the sorting stable? I wasn't 100% clear on this. > I didn't do this change. I suspect we may want to revisit how these get merged > and added to in bulk, and may want to revisit this at that point. It's easy to > go from unstable to stable, but hard to do the reverse. > No, I wasn't, I'm sorry if I gave that impression. It's not that much of an expense but is really annoying - I don't want any overhead over plain sorted vector. I suggested to fix the comment, which you already did. And that if you think that stability should be mentioned on the method level rather than on class one, you should probably add the same disclaimer to the initialiser list assignment.
The CQ bit was unchecked by commit-bot@chromium.org
Dry run: Try jobs failed on following builders: ios-simulator-xcode-clang on master.tryserver.chromium.mac (JOB_FAILED, http://build.chromium.org/p/tryserver.chromium.mac/builders/ios-simulator-xco...)
Remove noexcept
noexcept didn't go well so I removed the specifications. The problem was in flat_tree::Impl's constructor. I could have used some kind of tag and create a noexcept constructor (the current one can't be marked noexcept because it's used by other constructors). But this code copies the Compare class in all cases and I don't think that can be noexcept. I don't think the lack of noexcept is causing issues here (and I don't know of any performance or correctness issues as pointed out in the style guide) so I just removed it.
Comments
On 2017/02/28 18:29:04, brettw (plz ping after 24h) wrote: > noexcept didn't go well so I removed the specifications. The problem was in > flat_tree::Impl's constructor. I could have used some kind of tag and create a > noexcept constructor (the current one can't be marked noexcept because it's used > by other constructors). > > But this code copies the Compare class in all cases and I don't think that can > be noexcept. I don't think the lack of noexcept is causing issues here (and I > don't know of any performance or correctness issues as pointed out in the style > guide) so I just removed it. Ok, we don't want magic. Here is the disccussion thread on noexcept and why you might want to declare move operations noexcept: https://groups.google.com/a/chromium.org/forum/#!topic/chromium-dev/8i4tMqNpHhg
New snap up with more "not stable" comments in the constructors.
The CQ bit was checked by brettw@chromium.org to run a CQ dry run
Dry run: CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...
https://codereview.chromium.org/2715433007/diff/260001/base/containers/flat_m... File base/containers/flat_map.h (right): https://codereview.chromium.org/2715433007/diff/260001/base/containers/flat_m... base/containers/flat_map.h:76: const Compare& comp = Compare()); It would be nice to inherit all of these constructors. There are some issues with inheriting constructors on Visual Studio - but can you check if you bump into them? You already have a test where you use initilizer list, I would also add one for first, last pair - because templates can expose some weird compiler bugs. https://codereview.chromium.org/2715433007/diff/260001/base/containers/flat_m... base/containers/flat_map.h:190: CHECK(found == tree::end() || tree::key_comp()(key, found->first)); This should probably just be tree::find. https://codereview.chromium.org/2715433007/diff/300001/base/containers/flat_t... File base/containers/flat_tree.h (right): https://codereview.chromium.org/2715433007/diff/300001/base/containers/flat_t... base/containers/flat_tree.h:253: iterator unsafe_insert_new_at(const_iterator position, value_type&& val); Nit: this could be one unsafe_emplace. https://codereview.chromium.org/2715433007/diff/300001/base/containers/flat_t... File base/containers/flat_tree_unittest.cc (right): https://codereview.chromium.org/2715433007/diff/300001/base/containers/flat_t... base/containers/flat_tree_unittest.cc:5: #include "base/containers/flat_tree.h" Nit: I would just keep them as flat_set tests. This is essentially what you do. Maybe you can move flat_map tests here too?
The CQ bit was unchecked by commit-bot@chromium.org
LGTM https://codereview.chromium.org/2715433007/diff/260001/base/containers/flat_m... File base/containers/flat_map.h (right): https://codereview.chromium.org/2715433007/diff/260001/base/containers/flat_m... base/containers/flat_map.h:76: const Compare& comp = Compare()); On 2017/02/28 18:40:53, dyaroshev wrote: > It would be nice to inherit all of these constructors. > There are some issues with inheriting constructors on Visual Studio - but can > you check if you bump into them? > > You already have a test where you use initilizer list, I would also add one for > first, last pair - because templates can expose some weird compiler bugs. I've checked - it doesn't work - compiler doesn't do lasy initialization - so it tries to instantiate a copy constructor for MoveOnly types. https://codereview.chromium.org/2715433007/diff/300001/base/containers/flat_t... File base/containers/flat_tree.h (right): https://codereview.chromium.org/2715433007/diff/300001/base/containers/flat_t... base/containers/flat_tree.h:253: iterator unsafe_insert_new_at(const_iterator position, value_type&& val); On 2017/02/28 18:40:53, dyaroshev wrote: > Nit: this could be one unsafe_emplace. I still think this is a good idea.
ping @brettew.
Merge and unsafe_emplace
Was distracted by other work for a while. I uploaded a new patch. There was some merging with the EraseIf work, and I did the unsafe_emplace suggestion. Do you want to take a final look? I'll submit tomorrow if I don't hear anything. https://codereview.chromium.org/2715433007/diff/260001/base/containers/flat_m... File base/containers/flat_map.h (right): https://codereview.chromium.org/2715433007/diff/260001/base/containers/flat_m... base/containers/flat_map.h:76: const Compare& comp = Compare()); Thanks for checking!
The CQ bit was checked by brettw@chromium.org to run a CQ dry run
Dry run: CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...
We should provide an EraseIf override for flat_map, but I would prefer to do that as a followup.
The CQ bit was unchecked by commit-bot@chromium.org
Dry run: Try jobs failed on following builders: ios-device on master.tryserver.chromium.mac (JOB_FAILED, http://build.chromium.org/p/tryserver.chromium.mac/builders/ios-device/builds...) ios-simulator-xcode-clang on master.tryserver.chromium.mac (JOB_FAILED, http://build.chromium.org/p/tryserver.chromium.mac/builders/ios-simulator-xco...)
Fix EraseIf
The CQ bit was checked by brettw@chromium.org to run a CQ dry run
Dry run: CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...
The CQ bit was unchecked by commit-bot@chromium.org
Dry run: This issue passed the CQ dry run.
Great that you are back! Just some nits. https://codereview.chromium.org/2715433007/diff/340001/base/containers/flat_m... File base/containers/flat_map.h (right): https://codereview.chromium.org/2715433007/diff/340001/base/containers/flat_m... base/containers/flat_map.h:18: // extracts the key as the first() element of a pair. Nit: maybe |first|? I'm ok with either, it's just that first is not a function. https://codereview.chromium.org/2715433007/diff/340001/base/containers/flat_m... base/containers/flat_map.h:30: // sorted containers that stores its elements in contiguous memory (a vector> Nit: closing brace. https://codereview.chromium.org/2715433007/diff/340001/base/containers/flat_m... base/containers/flat_map.h:39: class flat_map : public ::base::internal::flat_tree< Nit: dropping |::base| should work. If this is a deliberate style choice than it's ok. https://codereview.chromium.org/2715433007/diff/340001/base/containers/flat_m... base/containers/flat_map.h:189: CHECK(found == tree::end() || tree::key_comp()(key, found->first)); I'm pretty sure, that it should found != tree::end() and &&. Consider using tree::find - it does the right thing for you. https://codereview.chromium.org/2715433007/diff/340001/base/containers/flat_m... File base/containers/flat_map_unittest.cc (right): https://codereview.chromium.org/2715433007/diff/340001/base/containers/flat_m... base/containers/flat_map_unittest.cc:138: } Tests for at? https://codereview.chromium.org/2715433007/diff/340001/base/containers/flat_t... File base/containers/flat_tree.h (right): https://codereview.chromium.org/2715433007/diff/340001/base/containers/flat_t... base/containers/flat_tree.h:48: bool operator()(const Value& left, const Value& right) const { const value_type& ? https://codereview.chromium.org/2715433007/diff/340001/base/containers/flat_t... File base/containers/flat_tree_unittest.cc (left): https://codereview.chromium.org/2715433007/diff/340001/base/containers/flat_t... base/containers/flat_tree_unittest.cc:159: using SetWithLess = base::flat_set<int, std::less<int>>; Why did you drop set with less? I'd like to keep it - when we have less<> it would be IntTreeWithLess = flat_tree<int, int, GetKeyFromValueIdentity<int>, std::less<>> which would be different from IntTree after crbug.com/682254. I was hoping to do it reasonably soon, please don't make me restore all of these tests) https://codereview.chromium.org/2715433007/diff/340001/base/containers/flat_t... File base/containers/flat_tree_unittest.cc (right): https://codereview.chromium.org/2715433007/diff/340001/base/containers/flat_t... base/containers/flat_tree_unittest.cc:133: using ::base::internal::GetKeyFromValueIdentity; Is this necessary? You seem to be in base::internal already.
Review comments
The CQ bit was checked by brettw@chromium.org
The patchset sent to the CQ was uploaded after l-g-t-m from dyaroshev@yandex-team.ru Link to the patchset: https://codereview.chromium.org/2715433007/#ps360001 (title: "Review comments")
https://codereview.chromium.org/2715433007/diff/340001/base/containers/flat_m... File base/containers/flat_map.h (right): https://codereview.chromium.org/2715433007/diff/340001/base/containers/flat_m... base/containers/flat_map.h:39: class flat_map : public ::base::internal::flat_tree< On 2017/03/21 16:03:57, dyaroshev wrote: > Nit: dropping |::base| should work. If this is a deliberate style choice than > it's ok. Yes, I prefer not to reference relative namespaces. https://codereview.chromium.org/2715433007/diff/340001/base/containers/flat_m... base/containers/flat_map.h:189: CHECK(found == tree::end() || tree::key_comp()(key, found->first)); Find should be good, I did that. I think I was copying the code I wrote for operator[]. https://codereview.chromium.org/2715433007/diff/340001/base/containers/flat_m... File base/containers/flat_map_unittest.cc (right): https://codereview.chromium.org/2715433007/diff/340001/base/containers/flat_m... base/containers/flat_map_unittest.cc:138: } On 2017/03/21 16:03:57, dyaroshev wrote: > Tests for at? Yeah, thanks. I actually messed up at() in multiple ways, including the definition! https://codereview.chromium.org/2715433007/diff/340001/base/containers/flat_t... File base/containers/flat_tree_unittest.cc (left): https://codereview.chromium.org/2715433007/diff/340001/base/containers/flat_t... base/containers/flat_tree_unittest.cc:159: using SetWithLess = base::flat_set<int, std::less<int>>; I don't follow what the interface will look like in C++14, but I'll take your word for it and put this back. I deleted it just because the std::less was the default. https://codereview.chromium.org/2715433007/diff/340001/base/containers/flat_t... base/containers/flat_tree_unittest.cc:159: using SetWithLess = base::flat_set<int, std::less<int>>; I put these back. Normally I would prefer not to do this since it's currently unnecessary, you may never actually get around to changing this, and it's easy to add when you need it.
CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...
The CQ bit was unchecked by commit-bot@chromium.org
No L-G-T-M from a valid reviewer yet. CQ run can only be started once the patch has received an L-G-T-M from a full committer. Even if an L-G-T-M may have been provided, it was from a non-committer,_not_ a full super star committer. Committers are members of the group "project-chromium-committers". Note that this has nothing to do with OWNERS files.
The smallest nit possible) https://codereview.chromium.org/2715433007/diff/360001/base/containers/flat_m... File base/containers/flat_map.h (right): https://codereview.chromium.org/2715433007/diff/360001/base/containers/flat_m... base/containers/flat_map.h:105: const Mapped& at(const Key& key) const; mapped_type?
Nit
The CQ bit was checked by brettw@chromium.org
The patchset sent to the CQ was uploaded after l-g-t-m from dyaroshev@yandex-team.ru Link to the patchset: https://codereview.chromium.org/2715433007/#ps380001 (title: "Nit")
CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...
The CQ bit was unchecked by commit-bot@chromium.org
No L-G-T-M from a valid reviewer yet. CQ run can only be started once the patch has received an L-G-T-M from a full committer. Even if an L-G-T-M may have been provided, it was from a non-committer,_not_ a full super star committer. Committers are members of the group "project-chromium-committers". Note that this has nothing to do with OWNERS files.
The CQ bit was checked by brettw@chromium.org to run a CQ dry run
Dry run: CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...
On 2017/03/21 19:43:12, commit-bot: I haz the power wrote: > No L-G-T-M from a valid reviewer yet. > CQ run can only be started once the patch has received an L-G-T-M from a full > committer. > Even if an L-G-T-M may have been provided, it was from a non-committer,_not_ a > full super star committer. > Committers are members of the group "project-chromium-committers". > Note that this has nothing to do with OWNERS files. @brettw, just in case you missed it - I'm not an owner - you would need danakj lgtm. My lgtm still stands.
https://codereview.chromium.org/2715433007/diff/380001/base/containers/contai... File base/containers/container_test_utils.h (right): https://codereview.chromium.org/2715433007/diff/380001/base/containers/contai... base/containers/container_test_utils.h:1: // Copyright 2017 The Chromium Authors. All rights reserved. Why is this not in base/test/ (and the test build target)? https://codereview.chromium.org/2715433007/diff/380001/base/containers/flat_m... File base/containers/flat_map.h (right): https://codereview.chromium.org/2715433007/diff/380001/base/containers/flat_m... base/containers/flat_map.h:95: // Normal insert() functions are inherited from flat_tree. What do you think of making everything in flat_tree protected and putting "using" lines here so that the whole API is available to be seen in this one file? https://codereview.chromium.org/2715433007/diff/380001/base/containers/flat_m... base/containers/flat_map.h:103: // CHECK()s if the element does not exist. I think it'd be nice to instead word this in terms like "Only valid to be called if |key| exists in the map, will not add |key| to the map." or so. That expresses the intent and use case rather than the implementation. https://codereview.chromium.org/2715433007/diff/380001/base/containers/flat_m... base/containers/flat_map.h:189: CHECK(found != tree::end()); why did you choose CHECK instead of DCHECK? This would crash shortly after on trying to use *end() anyway, right? And DCHECK would be similar to assert() in the STL without adding strings to the binary.
https://codereview.chromium.org/2715433007/diff/380001/base/containers/flat_m... File base/containers/flat_map.h (right): https://codereview.chromium.org/2715433007/diff/380001/base/containers/flat_m... base/containers/flat_map.h:189: CHECK(found != tree::end()); On 2017/03/21 20:28:56, danakj wrote: > why did you choose CHECK instead of DCHECK? This would crash shortly after on > trying to use *end() anyway, right? And DCHECK would be similar to assert() in > the STL without adding strings to the binary. I suggested this. This is consistent with std::map - it throws an exception. base::Value does a check too: https://cs.chromium.org/chromium/src/base/values.cc?q=values.cc&l=221 Essentially at() is a strange method but I think we should be consistent with the standard.
The CQ bit was unchecked by commit-bot@chromium.org
Dry run: Try jobs failed on following builders: linux_chromium_chromeos_ozone_rel_ng on master.tryserver.chromium.linux (JOB_FAILED, http://build.chromium.org/p/tryserver.chromium.linux/builders/linux_chromium_...)
https://codereview.chromium.org/2715433007/diff/380001/base/containers/flat_m... File base/containers/flat_map.h (right): https://codereview.chromium.org/2715433007/diff/380001/base/containers/flat_m... base/containers/flat_map.h:189: CHECK(found != tree::end()); On 2017/03/21 20:34:46, dyaroshev wrote: > On 2017/03/21 20:28:56, danakj wrote: > > why did you choose CHECK instead of DCHECK? This would crash shortly after on > > trying to use *end() anyway, right? And DCHECK would be similar to assert() in > > the STL without adding strings to the binary. > > I suggested this. > This is consistent with std::map - it throws an exception. > base::Value does a check too: > https://cs.chromium.org/chromium/src/base/values.cc?q=values.cc&l=221 > Essentially at() is a strange method but I think we should be consistent with > the standard. We don't enable exceptions though, so it's not consistent for chrome.
On 2017/03/21 21:38:39, danakj wrote: > https://codereview.chromium.org/2715433007/diff/380001/base/containers/flat_m... > File base/containers/flat_map.h (right): > > https://codereview.chromium.org/2715433007/diff/380001/base/containers/flat_m... > base/containers/flat_map.h:189: CHECK(found != tree::end()); > On 2017/03/21 20:34:46, dyaroshev wrote: > > On 2017/03/21 20:28:56, danakj wrote: > > > why did you choose CHECK instead of DCHECK? This would crash shortly after > on > > > trying to use *end() anyway, right? And DCHECK would be similar to assert() > in > > > the STL without adding strings to the binary. > > > > I suggested this. > > This is consistent with std::map - it throws an exception. > > base::Value does a check too: > > https://cs.chromium.org/chromium/src/base/values.cc?q=values.cc&l=221 > > Essentially at() is a strange method but I think we should be consistent with > > the standard. > > We don't enable exceptions though, so it's not consistent for chrome. I'd guess that exception thrown would call terminate than, even in release mode. However, this is the idea of an at() function - to do a runtime error. It would be surprising, at the very least for me, if it didn't. We do the same thing for base::Value, isn't it a good enough reason?
On Tue, Mar 21, 2017 at 5:42 PM, <dyaroshev@yandex-team.ru> wrote: > On 2017/03/21 21:38:39, danakj wrote: > > > https://codereview.chromium.org/2715433007/diff/380001/ > base/containers/flat_map.h > > File base/containers/flat_map.h (right): > > > > > https://codereview.chromium.org/2715433007/diff/380001/ > base/containers/flat_map.h#newcode189 > > base/containers/flat_map.h:189: CHECK(found != tree::end()); > > On 2017/03/21 20:34:46, dyaroshev wrote: > > > On 2017/03/21 20:28:56, danakj wrote: > > > > why did you choose CHECK instead of DCHECK? This would crash shortly > after > > on > > > > trying to use *end() anyway, right? And DCHECK would be similar to > assert() > > in > > > > the STL without adding strings to the binary. > > > > > > I suggested this. > > > This is consistent with std::map - it throws an exception. > > > base::Value does a check too: > > > https://cs.chromium.org/chromium/src/base/values.cc?q=values.cc&l=221 > > > Essentially at() is a strange method but I think we should be > consistent > with > > > the standard. > > > > We don't enable exceptions though, so it's not consistent for chrome. > > I'd guess that exception thrown would call terminate than, even in release > mode. > Oh I thought that throws would actually do nothing but you're right it terminates. > However, this is the idea of an at() function - to do a runtime error. It > would > be surprising, at the very least for me, if it didn't. > > We do the same thing for base::Value, isn't it a good enough reason? > Cargo culting holds little motivation to me. In general I question use of CHECK() always, it's a rather expensive line of code on the binary, and they are usually not the right thing unless trying to debug a failing DCHECK in canary or avoiding a security problem in the case of failure (buffer overflow for example). Otherwise, it's usually wasteful. In this case dereffing a vector's end() iterator will already crash, so we're adding code here for no benefit really. The following will segfault: std::vector<std::pair<int, int>> v; auto i = v.end(); LOG(ERROR) << i->second; -- You received this message because you are subscribed to the Google Groups "Chromium-reviews" group. To unsubscribe from this group and stop receiving emails from it, send an email to chromium-reviews+unsubscribe@chromium.org.
On Tue, Mar 21, 2017 at 6:03 PM, <danakj+reviewer@chromium.org> wrote: > On Tue, Mar 21, 2017 at 5:42 PM, <dyaroshev@yandex-team.ru> wrote: > >> On 2017/03/21 21:38:39, danakj wrote: >> > >> https://codereview.chromium.org/2715433007/diff/380001/base/ >> containers/flat_map.h >> > File base/containers/flat_map.h (right): >> > >> > >> https://codereview.chromium.org/2715433007/diff/380001/base/ >> containers/flat_map.h#newcode189 >> > base/containers/flat_map.h:189: CHECK(found != tree::end()); >> > On 2017/03/21 20:34:46, dyaroshev wrote: >> > > On 2017/03/21 20:28:56, danakj wrote: >> > > > why did you choose CHECK instead of DCHECK? This would crash >> shortly after >> > on >> > > > trying to use *end() anyway, right? And DCHECK would be similar to >> assert() >> > in >> > > > the STL without adding strings to the binary. >> > > >> > > I suggested this. >> > > This is consistent with std::map - it throws an exception. >> > > base::Value does a check too: >> > > https://cs.chromium.org/chromium/src/base/values.cc?q=values.cc&l=221 >> > > Essentially at() is a strange method but I think we should be >> consistent >> with >> > > the standard. >> > >> > We don't enable exceptions though, so it's not consistent for chrome. >> >> I'd guess that exception thrown would call terminate than, even in >> release mode. >> > > Oh I thought that throws would actually do nothing but you're right it > terminates. > > >> However, this is the idea of an at() function - to do a runtime error. It >> would >> be surprising, at the very least for me, if it didn't. >> >> We do the same thing for base::Value, isn't it a good enough reason? >> > > Cargo culting holds little motivation to me. In general I question use of > CHECK() always, it's a rather expensive line of code on the binary, and > they are usually not the right thing unless trying to debug a failing > DCHECK in canary or avoiding a security problem in the case of failure > (buffer overflow for example). Otherwise, it's usually wasteful. > > In this case dereffing a vector's end() iterator will already crash, so > we're adding code here for no benefit really. The following will segfault: > > std::vector<std::pair<int, int>> v; > auto i = v.end(); > LOG(ERROR) << i->second; > See also https://chromium.googlesource.com/chromium/src/+/master/styleguide/c++/c++.md... which says to basically never use CHECK. -- You received this message because you are subscribed to the Google Groups "Chromium-reviews" group. To unsubscribe from this group and stop receiving emails from it, send an email to chromium-reviews+unsubscribe@chromium.org.
On Tue, Mar 21, 2017 at 6:10 PM, <danakj+reviewer@chromium.org> wrote: > > > On Tue, Mar 21, 2017 at 6:03 PM, <danakj+reviewer@chromium.org> wrote: > >> On Tue, Mar 21, 2017 at 5:42 PM, <dyaroshev@yandex-team.ru> wrote: >> >>> On 2017/03/21 21:38:39, danakj wrote: >>> > >>> https://codereview.chromium.org/2715433007/diff/380001/base/ >>> containers/flat_map.h >>> > File base/containers/flat_map.h (right): >>> > >>> > >>> https://codereview.chromium.org/2715433007/diff/380001/base/ >>> containers/flat_map.h#newcode189 >>> > base/containers/flat_map.h:189: CHECK(found != tree::end()); >>> > On 2017/03/21 20:34:46, dyaroshev wrote: >>> > > On 2017/03/21 20:28:56, danakj wrote: >>> > > > why did you choose CHECK instead of DCHECK? This would crash >>> shortly after >>> > on >>> > > > trying to use *end() anyway, right? And DCHECK would be similar to >>> assert() >>> > in >>> > > > the STL without adding strings to the binary. >>> > > >>> > > I suggested this. >>> > > This is consistent with std::map - it throws an exception. >>> > > base::Value does a check too: >>> > > https://cs.chromium.org/chromium/src/base/values.cc?q=values >>> .cc&l=221 >>> > > Essentially at() is a strange method but I think we should be >>> consistent >>> with >>> > > the standard. >>> > >>> > We don't enable exceptions though, so it's not consistent for chrome. >>> >>> I'd guess that exception thrown would call terminate than, even in >>> release mode. >>> >> >> Oh I thought that throws would actually do nothing but you're right it >> terminates. >> >> >>> However, this is the idea of an at() function - to do a runtime error. >>> It would >>> be surprising, at the very least for me, if it didn't. >>> >>> We do the same thing for base::Value, isn't it a good enough reason? >>> >> >> Cargo culting holds little motivation to me. In general I question use of >> CHECK() always, it's a rather expensive line of code on the binary, and >> they are usually not the right thing unless trying to debug a failing >> DCHECK in canary or avoiding a security problem in the case of failure >> (buffer overflow for example). Otherwise, it's usually wasteful. >> >> In this case dereffing a vector's end() iterator will already crash, so >> we're adding code here for no benefit really. The following will segfault: >> >> std::vector<std::pair<int, int>> v; >> auto i = v.end(); >> LOG(ERROR) << i->second; >> > > See also https://chromium.googlesource.com/chromium/src/+/master/ > styleguide/c++/c++.md#CHECK_DCHECK_and-NOTREACHED which says to basically > never use CHECK. > I was talking with @jbroman about this and he mentioned that I was probably seeing a crash because the vector had no capacity. Indeed by doing reserve() you can deref the end(). Walking off the end of the vector (and assigning to it) would be bad and potentially a security problem, so CHECK seems like the right call here then afterall. Thanks :) -- You received this message because you are subscribed to the Google Groups "Chromium-reviews" group. To unsubscribe from this group and stop receiving emails from it, send an email to chromium-reviews+unsubscribe@chromium.org.
https://codereview.chromium.org/2715433007/diff/380001/base/containers/flat_m... File base/containers/flat_map.h (right): https://codereview.chromium.org/2715433007/diff/380001/base/containers/flat_m... base/containers/flat_map.h:95: // Normal insert() functions are inherited from flat_tree. On 2017/03/21 20:28:55, danakj wrote: > What do you think of making everything in flat_tree protected and putting > "using" lines here so that the whole API is available to be seen in this one > file? I started doing this to see what it looked like. I agree with the concern that this class is harder to understand since the API is spread across two files. But with the usings I think you end up with: using tree::size; using tree::insert; using tree::begin; using tree::cend; which I don't think is much improvement. You still need to look at the tree file to see what insert looks like. It does at least tell you what functions are available, but the complexity-to-value ratio is not great (since I would also have to implement flat_set as a separate class again). What I ended up doing was writing a quick reference in both flat_set and flat_map of the available functions. A downside is that it might get out-of-date. But I think then the reference will be there where people look for it. Since it's a comment, I could give a more useful function signatures than just the name, but since it's not real code I could omit some of the ugly template goop so I think it's easier to follow than the alternatives. https://codereview.chromium.org/2715433007/diff/380001/base/containers/flat_m... base/containers/flat_map.h:103: // CHECK()s if the element does not exist. I'm thinking that we should remove at() entirely. Thinking about code bloat, the CHECK will generate like 120 bytes of code (if I recall correctly) for something that should never happen. This indicates that maybe we should be using a DCHECK, but I'm reluctant to ever knowingly return invalid references. The only use for at() is when you have a const object that you know contains the value and you don't want to bother with find(). This is something that's easy to add later if we change our minds.
LGTM https://codereview.chromium.org/2715433007/diff/380001/base/containers/flat_m... File base/containers/flat_map.h (right): https://codereview.chromium.org/2715433007/diff/380001/base/containers/flat_m... base/containers/flat_map.h:95: // Normal insert() functions are inherited from flat_tree. On 2017/03/21 23:19:54, brettw (plz ping after 24h) wrote: > On 2017/03/21 20:28:55, danakj wrote: > > What do you think of making everything in flat_tree protected and putting > > "using" lines here so that the whole API is available to be seen in this one > > file? > > I started doing this to see what it looked like. I agree with the concern that > this class is harder to understand since the API is spread across two files. But > with the usings I think you end up with: > > using tree::size; > using tree::insert; > using tree::begin; > using tree::cend; > > which I don't think is much improvement. You still need to look at the tree file > to see what insert looks like. It does at least tell you what functions are > available, but the complexity-to-value ratio is not great (since I would also > have to implement flat_set as a separate class again). > > What I ended up doing was writing a quick reference in both flat_set and > flat_map of the available functions. A downside is that it might get > out-of-date. But I think then the reference will be there where people look for > it. > > Since it's a comment, I could give a more useful function signatures than just > the name, but since it's not real code I could omit some of the ugly template > goop so I think it's easier to follow than the alternatives. FWIW with a using tree::size; in codesearch you'd have something to click to take you to the actual declaration. But having the full signature seems pretty cool too. https://codereview.chromium.org/2715433007/diff/380001/base/containers/flat_m... base/containers/flat_map.h:103: // CHECK()s if the element does not exist. On 2017/03/21 23:19:54, brettw (plz ping after 24h) wrote: > I'm thinking that we should remove at() entirely. Thinking about code bloat, the > CHECK will generate like 120 bytes of code (if I recall correctly) for something > that should never happen. This indicates that maybe we should be using a DCHECK, > but I'm reluctant to ever knowingly return invalid references. > > The only use for at() is when you have a const object that you know contains the > value and you don't want to bother with find(). This is something that's easy to > add later if we change our minds. sgtm
The CQ bit was checked by brettw@chromium.org
The patchset sent to the CQ was uploaded after l-g-t-m from dyaroshev@yandex-team.ru Link to the patchset: https://codereview.chromium.org/2715433007/#ps400001 (title: "Comments")
CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...
The CQ bit was unchecked by commit-bot@chromium.org
Try jobs failed on following builders: chromeos_daisy_chromium_compile_only_ng on master.tryserver.chromium.linux (JOB_FAILED, http://build.chromium.org/p/tryserver.chromium.linux/builders/chromeos_daisy_...)
The CQ bit was checked by brettw@chromium.org
CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...
The CQ bit was unchecked by commit-bot@chromium.org
Try jobs failed on following builders: ios-simulator on master.tryserver.chromium.mac (JOB_TIMED_OUT, build hasn't started yet, builder probably lacks capacity)
The CQ bit was checked by brettw@chromium.org
CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...
CQ is committing da patch.
Bot data: {"patchset_id": 400001, "attempt_start_ts": 1490202882177070,
"parent_rev": "203e5190f1c4b99f8407958a0e59f9a289649b5c", "commit_rev":
"9816813a28b7f20ef03ff69d901d3b9a891f0400"}
Message was sent while issue was closed.
Description was changed from ========== Add a flat_map container. This works the same as flat_set but corresponding to a std::map. The existing flat_set implementation was factored into a base class called flat_tree with a provision to have a potentially different lookup key type than value type, and a way to convert from a value to a key. flat_set and flat_map can be trivially implemented on top of this API. The existing flat_set tests are moved to flat-tree and some simple type-specific tests were created for the set and map derivations. flat_tree no longer copies the comparison object except when required (when returned by value_comp()). But this requires that the comparison functor be const which was not the case before. ========== to ========== Add a flat_map container. This works the same as flat_set but corresponding to a std::map. The existing flat_set implementation was factored into a base class called flat_tree with a provision to have a potentially different lookup key type than value type, and a way to convert from a value to a key. flat_set and flat_map can be trivially implemented on top of this API. The existing flat_set tests are moved to flat-tree and some simple type-specific tests were created for the set and map derivations. flat_tree no longer copies the comparison object except when required (when returned by value_comp()). But this requires that the comparison functor be const which was not the case before. Review-Url: https://codereview.chromium.org/2715433007 Cr-Commit-Position: refs/heads/master@{#458796} Committed: https://chromium.googlesource.com/chromium/src/+/9816813a28b7f20ef03ff69d901d... ==========
Message was sent while issue was closed.
Committed patchset #13 (id:400001) as https://chromium.googlesource.com/chromium/src/+/9816813a28b7f20ef03ff69d901d...
Message was sent while issue was closed.
FYI I'm adding back "noexcept" to the move constructors in a separate change. I assumed noexcept functions can only call other noexcept functions but it seems this is not true. My problem was with marking the "Impl" noexcept in the cases it's noexcept, and not in the other cases. But since the compiler doesn't care, I can leave the Impl as-is and just mark the move constructors noexcept (in this case the Impl is logically noexcept).
Message was sent while issue was closed.
On 2017/03/22 21:44:57, brettw (plz ping after 24h) wrote: > FYI I'm adding back "noexcept" to the move constructors in a separate change. > > I assumed noexcept functions can only call other noexcept functions but it seems > this is not true. My problem was with marking the "Impl" noexcept in the cases > it's noexcept, and not in the other cases. But since the compiler doesn't care, > I can leave the Impl as-is and just mark the move constructors noexcept (in this > case the Impl is logically noexcept). Nope, wrong again. I filed https://bugs.chromium.org/p/chromium/issues/detail?id=704307 for this, I suspect somebody that knows C++11 more than me needs to take a look.
Message was sent while issue was closed.
On 2017/03/22 22:14:39, brettw (plz ping after 24h) wrote: > On 2017/03/22 21:44:57, brettw (plz ping after 24h) wrote: > > FYI I'm adding back "noexcept" to the move constructors in a separate change. > > > > I assumed noexcept functions can only call other noexcept functions but it > seems > > this is not true. My problem was with marking the "Impl" noexcept in the cases > > it's noexcept, and not in the other cases. But since the compiler doesn't > care, > > I can leave the Impl as-is and just mark the move constructors noexcept (in > this > > case the Impl is logically noexcept). > > Nope, wrong again. I filed > https://bugs.chromium.org/p/chromium/issues/detail?id=704307 for this, I suspect > somebody that knows C++11 more than me needs to take a look. noexcept is a promise - it does not require anything of called functions. If exception is leaking through a function marked as noexcept - it calls terminate (http://en.cppreference.com/w/cpp/language/noexcept_spec). This is what we do for all exceptions (as far as I know). There are some compilation problems with noexcept on linux, I wrote about them here: https://groups.google.com/a/chromium.org/forum/#!searchin/chromium-dev/noexce... Can you upload your cl with noexcept? I might help you figure out what's going on. Or - I can try to add it here: crbug.com/682254 - I planned to work on that task in a close future.
Message was sent while issue was closed.
On 2017/03/22 22:14:39, brettw (plz ping after 24h) wrote: > On 2017/03/22 21:44:57, brettw (plz ping after 24h) wrote: > > FYI I'm adding back "noexcept" to the move constructors in a separate change. > > > > I assumed noexcept functions can only call other noexcept functions but it > seems > > this is not true. My problem was with marking the "Impl" noexcept in the cases > > it's noexcept, and not in the other cases. But since the compiler doesn't > care, > > I can leave the Impl as-is and just mark the move constructors noexcept (in > this > > case the Impl is logically noexcept). > > Nope, wrong again. I filed > https://bugs.chromium.org/p/chromium/issues/detail?id=704307 for this, I suspect > somebody that knows C++11 more than me needs to take a look. noexcept is a promise - it does not require anything of called functions. If exception is leaking through a function marked as noexcept - it calls terminate (http://en.cppreference.com/w/cpp/language/noexcept_spec). This is what we do for all exceptions (as far as I know). There are some compilation problems with noexcept on linux, I wrote about them here: https://groups.google.com/a/chromium.org/forum/#!searchin/chromium-dev/noexce... Can you upload your cl with noexcept? I might help you figure out what's going on. Or - I can try to add it here: crbug.com/682254 - I planned to work on that task in a close future.
Message was sent while issue was closed.
noexcept on Windows is blocked on this landing: https://codereview.chromium.org/2769283002/ which should hopefully go in today. For the flat_map changes, just check Patch 2 on here: https://codereview.chromium.org/2771643002/#ps20001 and see the Mac/iOS errors.
Message was sent while issue was closed.
dalecurtis@chromium.org changed reviewers: + dalecurtis@chromium.org
Message was sent while issue was closed.
https://codereview.chromium.org/2715433007/diff/400001/base/containers/flat_m... File base/containers/flat_map.h (right): https://codereview.chromium.org/2715433007/diff/400001/base/containers/flat_m... base/containers/flat_map.h:243: found = unsafe_emplace(found, key, Mapped()); Did you mean tree::unsafe_emplace() here? It doesn't compile for a base::flat_map<base::StringPiece, base::TimeDelta> where map[key] = value is used.
Message was sent while issue was closed.
https://codereview.chromium.org/2715433007/diff/400001/base/containers/flat_m... File base/containers/flat_map.h (right): https://codereview.chromium.org/2715433007/diff/400001/base/containers/flat_m... base/containers/flat_map.h:243: found = unsafe_emplace(found, key, Mapped()); On 2017/03/29 01:16:42, DaleCurtis wrote: > Did you mean tree::unsafe_emplace() here? It doesn't compile for a > base::flat_map<base::StringPiece, base::TimeDelta> where map[key] = value is > used. And we probably don't have a test for it. I think creating base::StringPiece explicitly should help you
Message was sent while issue was closed.
And we broke this usage: template <typename ... Args> using this_set = base::flat_set<Args...>; Usings are not OK with unpacking. |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
