0

Disclaimer: I am not very accustomed with working with C++11, especially with new semantics like auto and move.

I am trying to keep a O(log(n)) random access memory structure of simple structs sorted with respect to their first elements, with O(1) access to min/max elements. C++11 STL's set class provides exactly this, so tried implementing my design with it using g++ (GCC) 7.3.0 and preparing an overload for operator<. Since typing templated types every time is pain, I used auto for the result of the std::set::find member function as follows:

Minimal sample:

#include <set>

template <typename X> struct _get_auto_type;

struct A {
  int x;
  char y;
  bool operator<(const A &a) const { return x < a.x; }
};

int main(void)
{
  typedef std::set<A> A_set;
  A_set a_set{{1, 'a'}, {0, 'b'}, {2, 'c'}};
  auto a_it = a_set.find({0, 'b'});
  a_it->y++;
  _get_auto_type<decltype(a_it)> _gat;
  return 0;
}

g++ output:

$ g++ -std=c++11 possible_gcc_bug.cpp
possible_gcc_bug.cpp: In function ‘int main()’:
possible_gcc_bug.cpp:16:34: error: aggregate ‘_get_auto_type<std::_Rb_tree_const_iterator<A> > _gat’ has incomplete type and cannot be defined
   _get_auto_type<decltype(a_it)> _gat;
                                  ^~~~
possible_gcc_bug.cpp:17:10: error: increment of member ‘A::y’ in read-only object
   a_it->y++;
          ^~

The two cases where this result is expected are:

  1. Compiler has a bug (my initial guess), or
  2. std::set's Key values are rvalues only, which seems more reasonable but I couldn't find any solid evindence for this.

Are either of my guesses correct, and if the 2nd one is true, which data structure (preferably from STL) can I use instead?

Yakk - Adam Nevraumont
  • 262,606
  • 27
  • 330
  • 524
acarturk
  • 111
  • 1
  • 7
  • The correct way to alter the contents of a set is to extract the value, modify it, and reinsert it. The set maintains the items in a particular structure based on their value; if you change them without removing/inserting them, you can end up with the layout of the elements being wrong. – Yakk - Adam Nevraumont Jan 13 '22 at 17:20
  • 1
    @Yakk-AdamNevraumont In reality what I had clumsily implemented here was `std::map`: Those members that I modify didn't affect the total ordering of the set, so dividing them into keys and values solved my problem. Otherwise, yes, your point about `std::set` is correct. Thanks for the input anyways. – acarturk Jan 13 '22 at 18:25
  • you could also mark members as mutable ;) (usually a bad idea) – Yakk - Adam Nevraumont Jan 13 '22 at 22:34

0 Answers0