-3

I am working on a program to insert objects into vector of objects only if it does not exist already keeping them sorted. so for that i have included algorithm header and using find and sort functions i am trying to execute the same but it is giving me an error I am not able to understand and solve.

This is the function for insertion where it is returning a an object of class word and data is a vector of words.

    Word *WordVector::insert(const string text){
Word newWord(text);
if(data.size()==0)
{
    data.push_back(newWord);
}

else{
    if(find(data.begin(),data.end(),newWord)!=data.end()){
        newWord.increaseCount();
    }
    else data.push_back(newWord);
    std::sort(data.begin(), data.end());
}

return &newWord;

}

and it gives me this error "Invalid operands to binary expression ('Word' and 'const Word')" in algorithm file at this method at line 7

    template <class _InputIterator, class _Tp>
inline _LIBCPP_INLINE_VISIBILITY
_InputIterator
find(_InputIterator __first, _InputIterator __last, const _Tp& __value_)
{
    for (; __first != __last; ++__first)
        if (*__first == __value_)
            break;
    return __first;
}
Shilakha Dawar
  • 1
  • 5
  • 5
    Rather use a `std::set` for unique values. – user0042 Nov 09 '17 at 04:07
  • If the build results in errors, copy them (as text!) and paste it into the question body. In full, complete and without any modifications. – Some programmer dude Nov 09 '17 at 04:08
  • 1
    `newWord` isn't a predicate, i.e., you can't call it. You meant to use `std::find()` instead of `std::find_if()`. As an aside: if you already found the location you can `insert()` into this location: that is bound to be way more efficient than sorting the container every time. Note that your current code sorts `data` even if it didn't change. Also, on sorted ranges you can search using `std::lower_bound()`. – Dietmar Kühl Nov 09 '17 at 04:08
  • 1
    `return &newWord;` -- This was bound to fail anyway. You're returning the address of a local variable -- usage of that address after the function returns is undefined behavior. – PaulMcKenzie Nov 09 '17 at 04:17
  • 1
    @ShilakhaDawar -- Update the post with the code, not in the comment. Second, what is `Word`? How is `std::find` to know when a `Word` is equal to another `Word`? Third, don't post images. – PaulMcKenzie Nov 09 '17 at 04:25
  • [How to insert unique items into vector?](https://stackoverflow.com/q/23844830/995714) – phuclv Nov 09 '17 at 04:30
  • A lot of problems have already been told and many solutions given... In addition, it does not make much sense to sort the vector after each insert. – Phil1970 Nov 09 '17 at 04:35

1 Answers1

0

I would use std::lower_bound for this. It returns the correct insert position in a sorted container to keep the elements sorted.

bool insert_sorted(std::vector<int>& v, int n)
{
    // find the correct sorted insert position
    auto insert_itr = std::lower_bound(std::begin(v), std::end(v), n);

    // only insert if not a duplicate
    // test for end() first to make duplicate test safe
    if(insert_itr == std::end(v) || *insert_itr != n)
    {
        v.insert(insert_itr, n);
        return true;
    }

    return false;
}

int main()
{
    std::vector<int> ints;

    for(auto i = 0; i < 10; ++i)
        insert_sorted(ints, hol::random_number(0, 10));

    for(auto i: ints)
        std::cout << i << '\n';
}

Sample Output:

0
3
4
7
9
10

To get this to work on a user defined type you will need to define certain functions that enable the class to be sorted and tested for (in)equality.

For example:

class Word
{
public:
    Word(std::string const& s): s(s) {}

    // to enable sorting
    bool operator<(Word const& w) const { return s < w.s; }

    // enable equality matching
    bool operator==(Word const& w) const { return s == w.s; }
    bool operator!=(Word const& w) const { return s != w.s; }

    // enable printing out
    friend std::ostream& operator<<(std::ostream& os, Word const& w)
    {
        return os << w.s;
    }

private:
    std::string s;
};

bool insert_sorted(std::vector<Word>& v, Word const& w)
{
    // find the correct sorted insert position
    auto insert_itr = std::lower_bound(std::begin(v), std::end(v), w);

    // only insert if not a duplicate
    // test for end() first to make duplicate test safe
    if(insert_itr == std::end(v) || *insert_itr != w)
    {
        v.insert(insert_itr, w);
        return true;
    }

    return false;
}
Galik
  • 47,303
  • 4
  • 80
  • 117