CODEWITHSUNDEEP
c++vector
Josh Elias
Josh Elias

Reputation: 3290

Efficient Input Handling with std::vector buffers

I'm trying to find a fast way to do input but I've learned that using STL for such purposes might be slow.

I have a callback that fires whenever I get Keyboard input. It creates an object with (int _key, int _state, int _life)

Everytime I receive this callback, I push_back the object to my std::vector;

Every frame I check the top of this vector and remove the "dead" input.

The vector can be polled for whatever input is valid at that moment which means it will be searched frequently.

Optimizations:

-All the memory should be contiguous so although Link Lists are better for dynamic allocation, should I stick with STL's vector? I'm always adding to the top and removing from the bottom so what data struct should I use?

-I was thinking of having a buffer(second vector) that continuously receives new input from the callback, then each frame copy the data from that vector to the top of my active input vector. Since the active vector will be polled, would this increase performance since it won't be wasting time getting added to during the loop?

Basically I'm trying to squeeze as much performance from this vector as possible and I could use some help.

Upvotes: 1

Views: 322

Answers (4)

Some programmer dude
Some programmer dude

Reputation: 409166

What you are describing, adding data in one end, removing in another, is the archetypical description of a queue. This is implemented in the standard library with the std::queue class.

This queue class is a so-called container adapter, meaning it uses another container for the actual storage. By default it uses std::deque, but that container doesn't keep its data in a contiguous memory area. However you can declare a std::queue with almost any other standard container, like std::vector (which is the only container guaranteed to store data in a contiguous memory area):

std::queue<int, std::vector> my_queue_with_vector;
my_queue_with_vector.push(1);
my_queue_with_vector.push(2);
my_queue_with_vector.push(3);

while (!my_queue_with_vector.empty())
{
    std::cout << my_queue_with_vector.top() << '\n';
    my_queue_with_vector.pop();  // Remove top element in the queue
}

Upvotes: 3

Puppy
Puppy

Reputation: 146910

std::deque makes the best container. It guarantees O(1) pop_front and push_back() and has random access and a good degree (although not completely) of cache behaviour.

But if you absolutely must have complete contiguity, then you'll need to look into a custom circular buffer container (there's one in Boost IIRC), as pop_front() on a vector is rather expensive.

Edit: As another poster has pointed out, keyboard input is so infrequent even for a very fast typist that I find it difficult to believe that this is a bottleneck in your system.

Upvotes: 3

Peter
Peter

Reputation: 5728

Short answer: It doesn't matter. std::vector and std::list can easily handle millions of insert operations per second, but most typists don't type faster than 10 characters per second on a keyboard.

Long answer: push_back and erase are usually very cheap on a vector if the vector is small (< 100) and the copy/swap operations of the objects stored on the vector are cheap. The allocations used to insert into or remove from an std:list are usually more expensive. If it becomes an issue, measure the cost.

An std::deque also has allocations and depending on the implementation is likely more expensive than the vector in your case, if my assumption that your vector rarely if ever contains more than 10 items - all of which are cheap to copy - is correct.

Upvotes: 0

Andreas Brinck
Andreas Brinck

Reputation: 52519

Sounds like you want a std::deque. Adjacents elements are nearly always allocated continuously in memory and it has constant time insertion and removal at begin and end.

Upvotes: 1

Related Questions