0

I am writing a program in C++ in which I will have to have a container with the following characteristics:

  1. It is basically FIFO
  2. I will put elements at the end
  3. I will take elements from the top
  4. I will take elements after a search

If only the three conditions would be needed, then I think a queue will be ideal.

However, sometimes I will have to take out elements depending on their values. For example, say I have the elements {1,2,3,4} , I can do take(2) and the resulting container will have to be {1,3,4}

On other occasions the take will happen only on the top.

What would be the best or recommended way to implement this, taking into account issues like performance?

KansaiRobot
  • 5,148
  • 7
  • 44
  • 95
  • Does this answer your question? https://stackoverflow.com/questions/54310262/getting-index-of-an-element-in-a-stdqueue-by-its-value – 463035818_is_not_a_number May 08 '20 at 08:16
  • top and end are the same or you mean top == front? – bartop May 08 '20 at 08:22
  • Another approach could be to replace taken values by a place-holder which remarks the element as unused. Hence, taking away element doesn't cause any shifting anywhere. The only effort is to skip un-used values once the approach on front. Btw. a ring-buffer (based on a vector) might be worth a thought as well... – Scheff's Cat May 08 '20 at 08:22
  • 1
    try the best candidates and profile them if performance is of concern – bolov May 08 '20 at 08:28
  • @idclev463035818 not really sure. According to https://stackoverflow.com/a/54310728/4451521 it seems deque could be convenient... – KansaiRobot May 08 '20 at 08:53
  • 1
    "...taking into account issues like performance?" performance is always an "issue" otherwise you wouldn't use C++, but don't do premature optimization. You can only know what is more efficient when you implement something and compare it to something else by measuring and profiling both. The first trial should always be code that is easy to write and read – 463035818_is_not_a_number May 08 '20 at 09:08
  • ...that being said, I would probably use a `std::vector` ;) – 463035818_is_not_a_number May 08 '20 at 09:10
  • @idclev463035818 thanks. Care to mention why would you use `std::vector`? – KansaiRobot May 08 '20 at 09:28
  • 1
    because it is the one I know best and even though it has worse complexity for some operations than other containers it still beats them in many situations due to its cache-friendliness. Only if that turns out to be too slow I'd turn to a container that has constant insertion – 463035818_is_not_a_number May 08 '20 at 09:33

0 Answers0