CODEWITHSUNDEEP
c++c++11unique-ptrunordered-set
Sourab Sharma
Sourab Sharma

Reputation: 3

Unable to find a user-defined type in a c++ unordered set with custom operator==()

Problem Statement: Iterate over an array of objects and check if the object exists in an unordered_set.

Goal: I could have thousand of objects in one container to check their existence in millions of objects in another container. I choose unordered_set for its constant finding complexity and vector for iterating. I'm new to this and if you have any alternate approach, I'd really appreciate it.

Issue: unordered_set find isn't working as expected or I got the concept wrong!

Main:

int main() {
  std::vector<std::unique_ptr<Block>> vertices;

  vertices.push_back(std::make_unique<Block>("mod1", "work"));
  vertices.push_back(std::make_unique<Block>("mod2", "work"));
  vertices.push_back(std::make_unique<Block>("mod3", "work"));

  std::unordered_set<std::unique_ptr<Block>> undefs;

  undefs.insert(std::make_unique<Block>("mod1", "work"));
  undefs.insert(std::make_unique<Block>("mod2", "work"));

  for(auto& vertex : vertices) {
    auto search = undefs.find(vertex);
    if(search != undefs.end()){
      std::cout << "Block: " << vertex->getName() << "\n";
    }
  }
}

Block Class Overload:

bool Block::operator==(std::unique_ptr<Block>& block) const {
  return block->getName() == mName;
}

Expected Output:

mod1

mod2

Block:

#pragma once

#include <string>
#include <memory>

using std::string;

class Block {
  private:
    string mName;
    string mLib;
  public:
    Block(string const& name, string const& lib);
    string getName() const;
    string getLib() const;
    bool operator==(std::unique_ptr<Block>& block) const;
};

Upvotes: 0

Views: 604

Answers (3)

Adrisui3
Adrisui3

Reputation: 94

The problem there is that you are trying to compare pointers, which are different! I'dont know the reasons behind using unique_ptr<> but by doing that you are actually trying to compare identities, instead of states which is what you want.

So you can see what I mean, let's say the first Block object is at position 100 in your memory. That would be its identity. So we have object1 whose state is "mod1, work" and whose identity is 100. Then we have object2, whose identity is 150 but its state is the same as object1, "mod1, work".

All what you have both inside the vector and the unordered_set are pointers, so you have memory positions. When inserting them in the vector, you inserted, let's say, position 100. But in the unordered_set you inserted 150. They have the same state, but find method is looking for a memory position.

I hope my answer was helpful. If you find any mistakes here or think differently please let me know. Good luck! :)

Upvotes: 0

espkk
espkk

Reputation: 366

You are trying to compare pointers, not values. You need to specify hashing function for class Block.

For example, if you want to use mName as key the code will be the following:

class Block {
private:
    string mName;
    string mLib;
public:
    Block(string const& name, string const& lib)
    {
        mName = name;
        mLib = lib;
    }
    string getName() const {
        return mName;
    };
    string getLib() const {
        return mLib;
    }
    bool operator==(const Block & block) const;
};

template<> struct std::hash<Block> {
    std::size_t operator()(const Block & block) const noexcept {
        return std::hash<std::string>{}(block.getName());
    }
};

bool Block::operator==(const Block & block) const {
    return block.getName() == mName;
}

int main() {
    std::vector<Block> vertices;

    vertices.emplace_back(Block("mod1", "work"));
    vertices.emplace_back(Block("mod2", "work"));
    vertices.emplace_back(Block("mod3", "work"));

    std::unordered_set<Block> undefs;
    undefs.emplace(Block("mod1", "work"));
    undefs.emplace(Block("mod2", "work"));

    for (auto& vertex : vertices) {
        auto search = undefs.find(vertex);
        if (search != undefs.end()) {
            std::cout << "Block: " << vertex.getName() << "\n";
        }
    }
}

Upvotes: 2

David Schwartz
David Schwartz

Reputation: 182827

An unordered_set requires a hashing function and a comparison function. You are using the existing hashing and comparison functions for std::unique_ptr, which is definitely not what you want.

I would not suggest trying to change the behavior of std::unique_ptr<Block> because that will lead to confusion in other code that wants normal semantics for pointers. Instead, add normal hashing and comparison functions for Block and pass customized ones to the constructor of the unordered_set.

Upvotes: 2

Related Questions