std::set with custom comparator

Question

I am trying to order wordItems in descending wordCount order in a set.

I am in data structures, and our professor gives us challenges to use STL containers on previous assignments. The reason an std::set is being used here is because my Prof. wants to show us how to use an STL BST in practice.

I cannot seem to figure out the std::set and all of its functionality...

Here is what I believe to be the relevant code pertaining to my wordItem struct:

// header file (HashTable.hpp)
struct wordItem
{
    std::string word;
    int count;
    wordItem* next;
};

struct comp 
{
    // I have also tried bool operator<()(wordItem const &lhs, wordItem const &rhs)     
    bool operator()(wordItem const &lhs, wordItem const &rhs) const {
        if (lhs.count == rhs.count) {
            return lhs.word > rhs.word;
        }
        return lhs.count > rhs.count;
    }
};

And then here is my function that would actually use this set:

// implementation file (HashTable.cpp)
#include "HashTable.hpp"
void HashTable::printTopN(int n) {
    set<wordItem,comp> s;

    for (int i = 0; i < hashTableSize; i++) {
        if (hashTable[i] != nullptr) {
            wordItem *temp = hashTable[i];
            s.insert(*temp);
            while (temp->next != nullptr) {
                temp = temp->next;
                s.insert(*temp);
            }
        }
    }
}

However, I am getting an error message that says I am using undeclared identifiers. Both comp and s are causing this... This is the exact error message:

HashTable2.cpp:129:16: error: use of undeclared identifier 'comp' 
set<wordItem,comp> s;
             ^
HashTable2.cpp:134:7: error: use of undeclared identifier 's'
s.insert(*temp);
^
HashTable2.cpp:137:9: error: use of undeclared identifier 's'
s.insert(*temp); 
^

The set is supposed to contain wordItem's with the largest wordCount first, and if two words share the same count the tiebreaker should be lexicographical order.

I feel like the issue is probably coming from the fact that I am probably not comparing these wordItem's correctly

Lastly, I apologize because I assume its very messy to mix my own custom data structures with the STL structures, but any help would be greatly appreciated

Please extract a [mcve]. That should also help you rule out a few common errors yourself. Also, quote the full error verbatim, don't paraphrase! — Ulrich Eckhardt, Oct 30 '18 at 18:46

NathanOliver · Answer 1 · 2018-10-30T18:52:55.703

0

When you use a custom comparator std::map uses it as

comp_object(a, b)

In

struct comp {
    bool operator<(wordItem const &lhs, wordItem const &rhs) const {
        if (lhs.count == rhs.count) {
            return lhs.word > rhs.word;
        }
        return lhs.count > rhs.count;
    }
};

you define an operator <, not an operator (), so it wont work. Change it to

struct comp {
    bool operator()(wordItem const &lhs, wordItem const &rhs) const {
        if (lhs.count == rhs.count) {
            return lhs.word > rhs.word;
        }
        return lhs.count > rhs.count;
    }
};

And it will work. This is called a functor and you can read more about there here: What are C++ functors and their uses?

edited Oct 30 '18 at 18:52

answered Oct 30 '18 at 18:49

NathanOliver

171,901
28
288
402

Thank you for your quick reply @NathanOliver ! I will read up on functors and their uses for sure!! However, I suppose I do not know where my issue is coming from in this case (as I am using std::set): I changed `bool operator<()` with `bool operator()()` and the undeclared identifier error remains... – pickypoo1987 Oct 30 '18 at 19:01
1

@pickypoo1987: Is `comp` defined in a place where it can be found by `HashTable::printTopN`, that is, in some header file `#include`-ed in the source file where `HashTable::printTopN` is defined? Are you sure you saved both files? It's pretty hard to say anything for sure, given you haven't actually provided a [MCVE]. – ShadowRanger Oct 30 '18 at 19:11
@ShadowRanger I struggle with the Complete and Verifiable aspects of that especially :( However, I will change my code above to try and clarify! – pickypoo1987 Oct 30 '18 at 19:17

std::set with custom comparator

1 Answers1