C++ - Alternative to iterating vector

Question

I have a std::vector<MyClass*> (a vector of MyClass pointers), and I need to find a particular item in the vector. The class has a getID() function which returns a unique identifier of the class.

If I want to find a class with a specific ID, I iterate through the vector looking for the class with the ID, like this:

for(std::vector<Chunk*>::iterator it = chunksRenderList.begin(); it != chunksRenderList.end(); ++it)
{
    if((*it)->getID() == id)
        return *it;
}

This is rather slow because I am calling this code lots of times per second. I have tried using a std::unordered_map which was a lot slower, and a std::map was slower again. I'm not sure why it was slower, maybe it's the way I used it.

Is there any container/algorithm I can use to access a particular item without having to iterate (that is faster than iteration)?

`std::unordered_map` has amortized constant time for accessing an element. Iterating has O(N) complexity. — chris, Jul 18 '13 at 03:02
I have a hard time believing unordered_map was slower... You werent *iterating* on the map were you? — Borgleader, Jul 18 '13 at 03:05
I would like to see the justification for the statement that maps are slower with some hard data. I simply do not believe it. — Ed Heal, Jul 18 '13 at 03:44
Yeah, I had a hard time believing it as well... Maybe I'm doing it wrong. This is how I was finding the item in the unordered_map: `try { return uomap.at(ID); } catch (out_of_range ooe) { return NULL; }`. Is that correct? — brettwhiteman, Jul 18 '13 at 03:45
@chris what exactly do you mean by this? When I profiled it, there was some exception handling taking up a lot of CPU time, maybe the exception handling is the problem. Please elaborate on your comment - it may be the solution. — brettwhiteman, Jul 18 '13 at 04:06
Try `try { return uomap.at(ID); } catch (...) { return nullptr; }` — Ed Heal, Jul 18 '13 at 04:09
@Ed Heal tried that, no difference. I profiled it and RtlInitializeExceptionChain was using 50% of the CPU time!!!!!! What is it? — brettwhiteman, Jul 18 '13 at 04:13
What is wrong with 50% CPU? Surely the time from start to finish is important and the OS gives you as much free CPU as possible. Better than being idle. So you need to learn about profiling. — Ed Heal, Jul 18 '13 at 04:21
CxxThrowException is also using quite a lot of CPU time... maybe I should try to reduce the amount of out_of_range exceptions thrown... are exceptions quite expensive? (there are HEAPS occuring in my case) — brettwhiteman, Jul 18 '13 at 04:21
@user2593738: Yes, exceptions are generally *quite* expensive. — Jerry Coffin, Jul 18 '13 at 04:37
Don't rely on exceptions for searching. Use `map::find` to check if the item is in your map. — paddy, Jul 18 '13 at 04:43
@paddy - much faster. Must have been the exceptions! Thanks everyone!!! — brettwhiteman, Jul 18 '13 at 04:57
@user2593738, You might give this a quick look: http://stackoverflow.com/questions/2522299/c-catch-blocks-catch-exception-by-value-or-reference?rq=1 — chris, Jul 18 '13 at 06:24

Pixelchemist · Accepted Answer · 2013-07-18T04:36:56.220

If your container is sorted accoding to the value of getID() you may try using a binary search.

class A
{
  size_t m_id;
public:
  A (size_t id) : m_id(id) {}
  size_t getID (void) const { return m_id; }
};

template<class T1, class T2>
struct less_id
{
  bool operator () (T1 const &lhs, T2 const & cmp)
  {
    return (lhs->getID() < cmp);
  }
};

int main (void)
{
  std::vector<A*> v;
  v.push_back(new A(2));
  v.push_back(new A(3));
  v.push_back(new A(4));
  v.push_back(new A(5));

  less_id<A*, size_t> cmp;

  size_t find_value = 4;
  std::vector<A*>::iterator found = std::lower_bound(v.begin(), v.end(), find_value, cmp);
  if(found == v.end() || !((*found)->getID() == find_value))
  {
    // not found
  }
  else
  {
    // found
    std::cout << "Found element: " << (found-v.begin()) << std::endl;
  }

  for (size_t i=0; i<v.size(); ++i) delete v[i];
  v.clear();
}

Shows

Found element: 2

Where A == Chunk and v == chunksRenderList.

No, it wouldn't be the same. The unordered_* containers use hashing to identify elements. — Ulrich Eckhardt, Jul 18 '13 at 04:59

score 2 · Answer 2 · answered Jul 18 '13 at 03:05

2

If you're doing this enough to justify it, the obvious thing to do would be to sort the vector, then use a binary search to find your item.

If your ID's are reasonably predictably distributed over the range they cover, you could use an interpolating search to reduce the complexity from O(N) to roughly O(log log N) -- though it has enough higher constant that it's generally only a win with a fairly large collection.

answered Jul 18 '13 at 03:05

Jerry Coffin

476,176
80
629
1,111

By binary search do you mean should I check whether it is within the first half or second half, then check the first and second half of the half it's in and keep repeating this until I pinpoint the item? – brettwhiteman Jul 18 '13 at 04:02
1

@user2593738: Yes, exactly (though the standard library already has a "lower_bound" and "upper_bound" to do it for you). – Jerry Coffin Jul 18 '13 at 04:21
See http://stackoverflow.com/questions/446296/where-can-i-get-a-useful-c-binary-search-algorithm for an example implementation. – Marshall Clow Jul 18 '13 at 04:33
Or my answer where it's already adjusted for checking versus `getID()`. – Pixelchemist Jul 18 '13 at 04:35
Thanks @Pixelchemist I would +1 if I could (need 15 myself) – brettwhiteman Jul 18 '13 at 04:41

C++ - Alternative to iterating vector

2 Answers2