Checking if an item is already in a vector

Question

So I want to do some error checking on a vector that I have in a class to see if the item already exists before adding the new item to the vector.

ClassA cpp

void ClassA::func(std::shared_ptr<ClassB> new_item)
{
    for(auto items : vector_)
    {
        if(items = new_item)
        {
            return;
        }
        vector_.push_back(new_item);
    }
}

vector_ is the member class member std::vector. With this current implementation all new_item are being ignored even if it is not a duplicate. I know that 'if(items = new_item)' is the problematic line but I do not know why.

First, try `==` instead of `=`. Next, have a look at `std::find`. — juanchopanza, Jan 16 '14 at 16:52
possible duplicate of [Variable assignment in "if" condition](http://stackoverflow.com/questions/17681535/variable-assignment-in-if-condition) — Nemo, Jan 16 '14 at 16:53
Doesn't this have undefined behaviour because `push_back` may reallocate and then the iterators used by the range-based for loop will be invalid? Not to mention that it will add the new item many times. — Joseph Mansfield, Jan 16 '14 at 16:54
Another reason why you should use const iterators, const & arguments. when you intend to read (compare, in your case). Had you used const iterators you wouldn't have been here posting this question :) — theAlias, Jan 16 '14 at 16:57
@sftrabbit Yes. It will probably fail in strange ways from time to time. (And when it doesn't fail, he's likely to get a lot of unwanted extra copies of the item.) — James Kanze, Jan 16 '14 at 17:00

score 8 · Accepted Answer · answered Jan 16 '14 at 16:56

You are assigning instead of comparing for equality here:

if(items = new_item) // assigns value of new_item to items

This kind of problem is easily avoided by using well tested standard library functions such as std::find:

#include <algorithm> // for std::find
....
if (find(vector_.begin(), vector_.end(), newitem) == vector_.end())
  vector_.push_back(newitem);

Jarod42 · Answer 2 · 2014-01-16T17:27:36.157

2

You have a typo:

if(items = new_item)

should be

if (items == new_item)

Btw you may write

if (std::find(std::begin(vector_), std::end(vector_), new_item) == std::end(vector_) {
    vector_.push_back(new_item);
}

or use a std::set

edited Jan 16 '14 at 17:27

answered Jan 16 '14 at 16:52

Jarod42

203,559
14
181
302

score 1 · Answer 3 · answered Jan 16 '14 at 16:52

1

= is assignment

== is equality

You want

    if(items == new_item)
    {
        return;
    }

answered Jan 16 '14 at 16:52

benjymous

2,102
1
14
21

score 1 · Answer 4 · answered Jan 16 '14 at 16:54

1

This is what you need:

void ClassA::func(std::shared_ptr<ClassB> new_item)
{
    for(auto items : vector_)
    {
        if(items == new_item)
        {
            return;
        }            
    }

    vector_.push_back(new_item);
}

Note that you need == rather that =. Also, your code was adding new_item to the vector on every iteration. Now it's just done if the item isn't found.

answered Jan 16 '14 at 16:54

Sean

60,939
11
97
136

You're probably also going to want to do `auto const&`. – David G Jan 16 '14 at 16:55
What he needs is `if ( std::find( vector_.begin(), vector_end(), new_item ) == vector_.end() ) { vector_.push_back( new_item ); }`. There's no point in reimplementing what's already in the standard library. (What he also needs is another naming convention. Underscores as leading or trailing characters is just bad.) – James Kanze Jan 16 '14 at 16:58
@JamesKanze - yes, but I'm trying to show what's wrong with the code – Sean Jan 16 '14 at 17:04
@JamesKanze: I don't see how it's bad. I do the same to identify private members of a class more easily. – ctor Jan 16 '14 at 17:04
This will have the advantage of working, but is still inefficient. – CashCow Jan 16 '14 at 17:06
@CashCow - that's quite a claim. What makes looping over `vector_` less efficient that calling `std::find`? – Sean Jan 16 '14 at 17:09
Both are wrong. Use a std::set or unordered_set. If you want to maintain the insertion order then have a set on the side. – CashCow Jan 16 '14 at 17:10
@Sean It's not the looping itself, but making an unnecessary copy every iteration that makes it inefficient. Refer to the first comment under you answer. – Praetorian Jan 16 '14 at 17:10
No it's the looping that makes it inefficient. If you are adding 1000 items then you are going to make 999 checks on your last insertion, 998 the insertion before etc. Thus 500,000 checks. If you used a std::set it would be approx 1000 * 10 = 10,000. The copying might be inefficient depending on the class itself. – CashCow Jan 16 '14 at 17:11
@ctor Leading and trailing underscores are easily overlooked, and disappear with some fonts. If you want to identify data members, then `myXxx` or `m_xxx` do the job quite well. – James Kanze Jan 16 '14 at 17:13
@CashCow Now that _is_ inefficient. If the vector is large, efficiency is an issue, and you don't need to maintain insertion order, you can keep it sorted, and use `std::lower_bound`. `std::set` is convenient, but it certainly isn't efficient. – James Kanze Jan 16 '14 at 17:15
@JamesKanze Yes efficiency in one area is inefficiency elsewhere. If there are likely to be just a few duplicates, insertion order is not an issue, and you need to maintain the compactness of a vector, you just push_back everything then at the end, sort and remove dupes. unordered_set is more efficient for avoiding dupes during insertion time. Far more of an issue for me than the OP's coding style. – CashCow Jan 16 '14 at 17:24
@JamesKanze I don't need to tell you this because I know you are very experienced. But keeping it sorted as you insert means inserting in the middle which is O(N) time to move the elements. – CashCow Jan 16 '14 at 17:27
@CashCow And using `std::set` means allocating a new node for every insertion. In our time critical components, we've banned node based containers, because of their poor performance; you can do a lot of copying in the time you're not spending in page faults. We use `std::vector>`, rather than `std::map`, for performance reasons. (The classical big-O analysis assumes that all accesses have constant time. Which just isn't true.) – James Kanze Jan 16 '14 at 17:54
@CashCow (and everyone else): I agree that `std::set` is (or should be) the initial approach. It's the most natural, requires the least code, and is the simplest to understand. My comments only address the relative performance issues; it was suggested that using `std::vector` was a grave error for reasons of performance, which is false. When performance is an issue, you'll have to measure, but in our case, we found a sorted `std::vector`, using `std::lower_bound` for the insertion, to be significantly faster. – James Kanze Jan 16 '14 at 17:58

score 1 · Answer 5 · answered Jan 16 '14 at 16:56

1

You are using

 if(items = new_item)
    {
        return;
    }

value of new_item is assigned to items as "=" is an assignment operator and anything positive to if will make the condition true. You need to use "==" operator for comparison

answered Jan 16 '14 at 16:56

Ahmed

2,176
5
26
40

Checking if an item is already in a vector

5 Answers5