13

In the program below, I store some information in an hash table (std::unordered_map), the key is an object of the class RectData, the associated value is a tuple <uint, RectData, enum> and custom KeyHash and KeyEqual have been defined.

Inserting a <key,value> pair without a default constructor gives two pages of error with gcc 4.9.2. The line with the first error is:

visited_info[rect0] = info0;

I double checked with MSVC++ 12.0, I also have error messages.

When I add the default constructor, compilation is ok and the default constructor is called at run time. I could not understand why a default constructor is needed for the class RectData ?

Retrieving data from the hash table, using the [] operator, also requires a default constructor at compile time, but it is not called at run time, why ?

auto info = visited_info[rect];

Note: Changing the code with visited_info.emplace() and visited_info.find() solves the problem, but does not answer the question.

Thanks for your answers.

Full code is below.

#include <boost/functional/hash.hpp>
#include <tuple>
#include <vector>
#include <unordered_map>
#include <iostream>

using uint = unsigned int;

enum class Direction : int { left = 0, right = 1, up = 2, down = 3, null = 4 };

class RectData {
 public:
  RectData(uint width, uint height)
      : width_(width), height_(height), datas_(width * height, 0) {
    total_ = width_ * height_;
  }


  // A default constructor must be defined!
  RectData() : RectData(0u, 0u) {
    std::cout << "Calling the default constructor !!!" << std::endl;
  }

  size_t hash() const {
    return boost::hash_value(datas_);
  }

  bool operator==(const RectData &rect) const {
    return (width_ == rect.width_) &&
           (height_ == rect.height_) &&
           (datas_ == rect.datas_);
  }

  struct KeyHash {
    std::size_t operator()(const RectData &rect) const {
      return rect.hash();
    }
  };

  struct KeyEqual {
    std::size_t operator()(const RectData &r1, const RectData &r2) const {
      return r1 == r2;
    }
  };

 private:
  uint width_;
  uint height_;
  std::vector<uint> datas_;
  uint total_;
};

using StoredInfo = std::tuple<uint, RectData, Direction>;

int main() {
  std::unordered_map<RectData, StoredInfo, RectData::KeyHash,
                     RectData::KeyEqual> visited_info;

  RectData rect0(5u, 5u);
  RectData rect1(4u, 4u);
  RectData rect2(3u, 3u);
  RectData rect3(2u, 2u);

  StoredInfo info0 = std::make_tuple(10u, rect1, Direction::up);
  StoredInfo info1 = std::make_tuple(11u, rect2, Direction::down);
  StoredInfo info2 = std::make_tuple(12u, rect3, Direction::left);
  StoredInfo info3 = std::make_tuple(13u, rect0, Direction::right);


  // the line below requires a default RectData constructor!!! 
  visited_info[rect0] = info0;

  // default RectData constructor also needed here !!!
  visited_info[rect1] = std::move(info2);

  // but not needed here
  visited_info.insert(std::make_pair(rect2, info2));

  // and not needed here
  visited_info.emplace(rect3, info3);

  // but needed here and not called!!! 
  StoredInfo i1 = visited_info[rect1];
  std::cout << "Verify (must be 11) = " << std::get<0>(i1)
            << std::endl;

  // but needed here and not called!!! 
  StoredInfo &i2 = visited_info[rect2];
  std::cout << "Verify (must be 12) = " << std::get<0>(i2)
            << std::endl;


  // and not needed here
  auto it = visited_info.find(rect3); 
  std::cout << "Verify (must be 13) = " << std::get<0>(it->second)
            << std::endl;

}
Praetorian
  • 106,671
  • 19
  • 240
  • 328
user3636086
  • 803
  • 1
  • 7
  • 10
  • 5
    In `visited_info[rect0] = info0;`, first `operator[]` is called, which has no choice but to default-construct a new element and return a reference to it. Then `operator=` is called on that new element. Same with `auto info = visited_info[rect];` - `operator[]` needs a default constructor in case an entry with a given key does not exist. If the entry does exist after all, then a reference to the existing element is returned and the default constructor is not called. – Igor Tandetnik Apr 23 '15 at 14:18
  • possible duplicate of [Using std::map where V has no usable default constructor](http://stackoverflow.com/questions/1935139/using-stdmapk-v-where-v-has-no-usable-default-constructor) – Mark B Apr 23 '15 at 14:30
  • 1
    Understood, thanks to your clear explanation on the default construct for operator[]. – user3636086 Apr 23 '15 at 16:19

1 Answers1

18
visited_info[rect0] = info0;

well, what do you think this does? It's well-documented that the left-hand side evaluates to a reference to an item stored in the map. If that item wasn't there before, it is default constructed first.

You then use either copy- or move-assignment to update that default-constructed item from the right-hand-side of the expression.

If you want to avoid the default-construct-and-assign operation you're getting now, use emplace instead.

NB. One possible source of confusion is, for example, Python, where MyObj[1] might translate to a __getitem__ call, but MyObj[1]=1 to a __setitem__ call.

In C++, both the left-hand-side and right-hand-side expressions must evaluate to something, without knowing anything about the statement they're in. Hence, the left-hand-side evaluates to a reference which you can either read from or assign to - but the object needs to exist before you can take that reference.

Useless
  • 64,155
  • 6
  • 88
  • 132
  • WOW, nice~ but I found that DefualtInsertable is fixed from https://en.cppreference.com/w/cpp/container/unordered_map/operator_at ? Do you know the meaning? if we don't need default-constructed attribute, how can we create a variable before assgining? it is interesting. – fishshrimp鱼虾爆栈 Feb 15 '19 at 09:37
  • That says you still need the value to be DefaultConstructible though, _unless_ you have a custom allocator which can construct it with a non-default constructor when called as described (ie, as if emplacing with no value constructor arguments). – Useless Feb 15 '19 at 10:44