Return index of struct position in vector

Question

I read almost every thread that I found via google, but it didn't help me out..

I've got a struct inside a class:

struct animation {
    int identifier;
    int another_variable;
};

I store a bunch of these structs in a vector:

static std::vector<animation> anims;

Now, I need to find the index (the position) of a struct, based on the field identifier.

// This is what I found so far
int Animation::get_animation_index(int identifier) {        
    std::find(anims.begin(), anims.end(), identifier) - anims.begin();
 }

The idea is to get the vector index anims[0] .. anims[xxx] where the struct with the identifier xx is stored.

I tried it within a loop, but then I only get access to the object itself, not the index..

for (Animation::animation a : anims) {
    if (a.identifier == identifier) {
         // a is now the object, but I need the vector index..

Any ideas?

`for (size_t i = 0; i < anims.size(); ++i) { if (anims[i].identifier == identifier) {...} }` — David, Jan 09 '17 at 17:18
Have a look at http://stackoverflow.com/questions/589985/vectors-structs-and-stdfind eg. or the more current http://stackoverflow.com/questions/14437825/using-stdfind-with-a-predicate — Sander De Dycker, Jan 09 '17 at 17:18

Richard Hodges · Accepted Answer · 2017-01-09T18:07:03.883

for (Animation::animation const& a : anims) {  // note: reference
    if (a.identifier == identifier) {
        return std::addressof(a) - std::addressof(anims[0]);
    }
}

or:

std::find_if(anims.begin(), anims.end(), 
         [ident](const animation& a) { return a.identifier == ident; })
   - anims.begin();

or, if the animation may not be present:

int find_index(int ident)
{
    auto it = std::find_if(anims.begin(), anims.end(), 
              [ident](const animation& a) 
              { 
                  return a.identifier == ident; 
              });
    if (it == anims.end())
        return -1; // or throw, depending on requirements
    else 
        return it - anims.begin();
}

Finally, if your animations are sorted by identifier, you can employ a binary search, which will on average be a lot faster when the vector is large:

int find_index_sorted(const std::vector<animation>& anims, int ident)
{
    struct lower_ident
    {
        constexpr bool operator()(const animation& l, int r) const {
            return l.identifier < r;
        }

        constexpr bool operator()(int l, const animation& r) const {
            return l < r.identifier;
        }
    };
    constexpr auto pred = lower_ident();
    auto it = std::lower_bound(anims.begin(), anims.end(), ident, pred);
    if (it == anims.end() or pred(ident, *it))
        return -1;
    return it - anims.begin();
}

@elasticman be careful of range-based-for. By default it makes copies of each element. That is not normally what you want when iterating a vector of objects. Not so important when iterating a vector of integers etc. — Richard Hodges, Jan 09 '17 at 17:33

score 0 · Answer 2 · answered Jan 09 '17 at 17:36

0

An alternative to @RichardHodges find_index which is simpler imo:

for (size_t i = 0; i < anims.size(); ++i)
    if (anims[i].identifier == id)
        return i;

answered Jan 09 '17 at 17:36

David

27,652
18
89
138

1

If performance is important to you, you'll find that the compiler will be more eager to optimise the iterator-based versions. The repeated call to `anims.size()` in the loop test will defeat the compiler's attempts to perform loop unrolling. I appreciate that the difference is small for small vectors. For larger vectors it might be a factor. For this reason it's generally 'better' to prefer std algorithms. – Richard Hodges Jan 09 '17 at 18:17
@RichardHodges I'd be shocked if compilers can't optimize this just as well as iterator based versions. Do you have any reference backing up that claim? The reason I'd be shocked is because A) the vector isn't potentially modified in the loop and B) for about a decade this was the de-facto way to write loops so it would be extremely advantageous for compilers to optimize this particular case well. I was always told it was a 'given' the compiler would elide repeating this `size()` call, and in similar situations – David Jan 09 '17 at 18:21
1

prepare to be as shocked as I was: https://godbolt.org/g/anVZIv Note the lack of loop unrolling and the expensive indirect-with-offset addressing mode in the 3rd function. Both on clang and gcc. – Richard Hodges Jan 09 '17 at 19:18
1

Also anims.size() will be evaluated unnecessary often. Put outside of loop. – stephanmg Feb 11 '20 at 02:50

Return index of struct position in vector

2 Answers2

Linked