Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Why a default constructor is needed using unordered_map and tuple?

Tags:

c++

c++11

stl

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;

}
like image 600
user3636086 Avatar asked Apr 23 '15 14:04

user3636086


People also ask

Can tuple be key in unordered_map?

Unordered Map does not contain a hash function for a tuple. So if we want to hash a tuple then we have to explicitly provide it with a hash function that can hash a tuple. unordered_map can take up to 5 arguments: Key: Type of key values.

Why do you use unordered_map why not ordered map?

map is used to store elements as key,value pairs in sorted order. unordered_map is used to store elements as key,value pairs in non-sorted order.

What are the advantages of an unordered_map over a map?

Insertion of dense keys in std::map doesn't present performance difference with std::unordered_map under 1000 elements. In all other situations std::unordered_map tends to perform faster.

Which is faster map or unordered_map?

While the worst case time complexity for all the operations in a map is O(log(n)). Hence, in the worst case scenario, a map is faster than an unordered_map. An unordered_map is implemented using a hash table which makes it faster than a map in the average case.


1 Answers

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.

like image 164
Useless Avatar answered Oct 14 '22 18:10

Useless