Fix an issue in which b-tree set iterators allow for mutable access to keys.

This change makes b-tree sets conform to the std::set API of having const access through `iterator`s as well as `const_iterator`s.

This change can cause breakages for user code that depends on having mutable access to keys. If your code breaks, then there a couple of options to fix the issue:
- If you are mutating a part of the key that can impact the sorted order, then this is a bug and you need to extract the key, mutate it, and then re-insert the mutated key.
- If you are mutating a part of the key that can't impact the sorted order, then you can potentially (a) refactor to use btree_map instead of btree_set and make the part of the key that doesn't impact that ordering be the mapped_type, (b) change the part of the key that doesn't impact the ordering to be a `mutable` member of the key_type, (c) refactor from btree_set<K> to btree_set<K*> (but this also permits mutable access to the part of the key that determines the ordering).

PiperOrigin-RevId: 563118156
Change-Id: I243558e74c43aa6655290099494b411d15298f4c

2 files changed, 19 insertions, 2 deletions

diff --git a/absl/container/btree_test.cc b/absl/container/btree_test.cc
index 72f446b2..a204c6d5 100644
--- a/absl/container/btree_test.cc
+++ b/absl/container/btree_test.cc
@@ -2965,6 +2965,20 @@ TYPED_TEST(BtreeMultiKeyTest, Count) {
   EXPECT_EQ(set.count(2), 2);
 }
 
+TEST(Btree, SetIteratorsAreConst) {
+  using Set = absl::btree_set<int>;
+  EXPECT_TRUE(
+      (std::is_same<typename Set::iterator::reference, const int &>::value));
+  EXPECT_TRUE(
+      (std::is_same<typename Set::iterator::pointer, const int *>::value));
+
+  using MSet = absl::btree_multiset<int>;
+  EXPECT_TRUE(
+      (std::is_same<typename MSet::iterator::reference, const int &>::value));
+  EXPECT_TRUE(
+      (std::is_same<typename MSet::iterator::pointer, const int *>::value));
+}
+
 TEST(Btree, AllocConstructor) {
   using Alloc = CountingAllocator<int>;
   using Set = absl::btree_set<int, std::less<int>, Alloc>;
diff --git a/absl/container/internal/btree.h b/absl/container/internal/btree.h
index 5e8a2523..419a5356 100644
--- a/absl/container/internal/btree.h
+++ b/absl/container/internal/btree.h
@@ -1122,8 +1122,11 @@ class btree_iterator : private btree_iterator_generation_info {
   using const_reference = typename params_type::const_reference;
   using slot_type = typename params_type::slot_type;
 
-  using iterator =
-     btree_iterator<normal_node, normal_reference, normal_pointer>;
+  // In sets, all iterators are const.
+  using iterator = absl::conditional_t<
+      is_map_container::value,
+      btree_iterator<normal_node, normal_reference, normal_pointer>,
+      btree_iterator<normal_node, const_reference, const_pointer>>;
   using const_iterator =
       btree_iterator<const_node, const_reference, const_pointer>;