8

If I have a std:queue can I erase an element in the middle?

Or should I just go for a simple vector?

EDIT:

In the end, my search became between std::list and std::deque. this post gives a nice comparison, although I am still a bit undecided.

On one side, since after deletion I won't be accessing more members (the operation finishes) I am not that concerned about iterator invalidation. On the other side, I will probably access (or search) elements one by one, so random access might not be that important...

KansaiRobot
  • 7,564
  • 11
  • 71
  • 150
  • 2
    Related and/or interesting read: https://stackoverflow.com/questions/4010097/general-use-cases-for-c-containers – Tas May 11 '20 at 03:10

2 Answers2

5

  1. No, not unless you want to take all the elements out and put them back in again.

  2. A std::list might be better, but it depends on what else you want to do with it.

Bill Lynch
  • 80,138
  • 16
  • 128
  • 173
Beta
  • 96,650
  • 16
  • 149
  • 150
  • I want to do the common operations of a queue plus deleting middle elements on occasion (would require finding said element). I heard deque's might be of help. What do you think? – KansaiRobot May 11 '20 at 03:09
  • 1
    See https://stackoverflow.com/questions/4010097/general-use-cases-for-c-containers which contains a handy flowchart of what containers might fit your needs – Tas May 11 '20 at 03:10
  • @Tas Thanks. I did that and I got `std::list`. So now I am between list, vector or deque...:) – KansaiRobot May 11 '20 at 03:17
  • 1
    vectors are good for stacks but not queues, vector only allows efficient addition/removal at the back but a queue needs to remove elements at the opposite end from where they are inserted. deque and list are both good for queues. And depending on the object type there are also the equivalent types in boost.intrusive. – SoronelHaetir May 11 '20 at 03:18
  • @SoronelHaetir That is great advice! So in my case vectors should be out. Now my options are between `std::list` and `std:deque`... To delete a member in the middle I have first to find it, so some simple search is also needed – KansaiRobot May 11 '20 at 03:22
  • @KansaiRobot in most common cases `std::deque` will perform better than `std::list`. – Kyle May 11 '20 at 03:54
4

std:: queue is a container adapter i.e. it processes elements in a specific order 'First in First Out'. Why would you want to break this order? First, you can't erase elements from any position of an std:: queue except front end (Until and unless you use another auxiliary data structure). If you want a similar functionality then even before an std:: list go blindly for an std:: vector. Profile your code and if you feel the need of std:: list go for it.

Arun Suryan
  • 1,615
  • 1
  • 9
  • 27
  • 1
    Understood your point,Thanks!. I have been just told that vector allows efficient removal at the back so they are not that convenient for my needs. I am now between lists and deques. – KansaiRobot May 11 '20 at 04:01
  • 1
    @KansaiRobot You should go with `deque` then, `deque` has proven to be flexible and easier to use in my experience. Can't say much though. – Arun Suryan May 11 '20 at 04:28
  • 1
    @KansaiRobot `std::deque` give a nice balance between FIFO (First In, First Out) and random access. If you need both, `std::deque` is definitely the way to go. –  May 11 '20 at 04:30