data struct selection

[leo2008]

Which data structure is more ideal here?
1)Frequently need to add and remove elements from the middle of a list, and you will not read it very frequently? I tried with Linkedlist, vector, but none of these have any method to remove an element from the middle of a list in constant time.
2)Frequently adding and removing items from front and back of a list. Can I choose queue here?
3)List will never change size and you will swap items within it frequently. Array can be used?
4)Looking for specific unique items frequently using hashmap?
5)A list is sorted except for one item which is in wrong place. Can I use quick or bubble sort here?

[seeplus]

1) For element removal from a container that supports a forward iterator, then consider std::remove/std::remove_if. These transform the range without actually reducing it's size. See
https://cplusplus.com/reference/algorithm/remove/

Once you're used these for the required elements then you can do an .erase() from the returned new end iter to the original end iter to actually remove the elements in one step. This is the so-called erase-remove idiom.
https://en.wikipedia.org/wiki/Erase%E2%80%93remove_idiom

2) Suggest a dequeue
https://cplusplus.com/reference/deque/deque/

3) Consider a std::array
https://cplusplus.com/reference/array/array/

4) unordered_set (or unordered _map)
https://cplusplus.com/reference/unordered_set/unordered_set/

[Geckoo]

I am not really experienced - and maybe I don't understand your question, but for almost all your suggestions I could use as a container a simple std::vector<yourStruct> which is efficient for many of those contexts. With iterator I can add/remove some entries. However if your container does not change its size during process (example 3) I could use an array. I guess that other containers could be more efficient for some specific task. I stay tuned - your question is relevant and I wait other answers from most experienced dev ++

[leo2008]

I am trying to find best data structure for the above mentioned options.

[jonnin]

1) if the container is sorted (or in a meaningful order, eg by timestamp) matters. is it?
1.b) a lazy delete is a big, big performance enhancer when used correctly.

3) use pointers to the thing if it is bigger than an integer. swapping pointers is cheap, swapping fat objects may not be (even like a std string).
5) see your other question.

[salem c]

Well you should create your own container to begin with.

template <T> class myContainer {
  private:
    std::list<T> data;
  public:
    // push front, back, middle
    // pop front, back, middle
};

Now depending on which standard container you use, some of the methods are going to be simple one-liner wrappers feeding directly to the underlying container. Others will need work.

The point is to establish an interface for your container that then allows you the freedom to change the internals when you discover new information.

So if you decide later to change to std::vector<T> data;, you only need re-implement the class methods, leaving the interface alone (and the rest of your code oblivious to the change).

No one here knows the intricate details of how your use cases interact with one another.

You really need to build something, try it in the real world with real data, and make some performance measurements.

Only then will you know where the bottlenecks really are. People waste months trying to optimise their bikesheds (https://en.wiktionary.org/wiki/bikeshedding).

[Peter87]

1)
If the number of elements is small (say 100 elements or so) and the elements are cheap to copy then std::vector might very well be a good alternative.

With std::list (linked list) it will be faster if you already have an iterator to the position that you want to remove/insert at but otherwise you still need to step through each element one by one and that is not necessarily faster than shifting all the elements like std::vector would have to do, at least not when the elements are small and cheap to copy.

Using the erase-remove idiom as suggested by seeplus is a good idea if you're removing many elements.

// remove all elements that are equal to 12
container.erase(std::remove(container.begin(), container.end(), 12), container.end());

Otherwise, if you want to remove/add a single element you can use erase/insert with a single iterator as argument.

// The following works for std::vector and other random-access containers:
vec.erase(vec.begin() + 45); // remove the element at index 45
vec.insert(vec.begin() + 85, 10); // insert an element with the value 10 at index 85

// The following works for std::list and any other sequence container (including std::vector):
container.erase(std::next(container.begin(), 45)); // remove the element at index 45
container.insert(std::next(container.begin(), 85), 10); // insert an element with the value 10 at index 85 

2)
From the back: std::vector

From both front and back: std::deque.

There might of course exist other data structures that are more efficient for your particular use case (such as a circular buffer) but std::deque is probably good enough.


3)
Yes, std::vector/array should be a good choice.


4)
Well, you say "hashmap" so I guess you want std::unordered_map. std::map is similar but is implemented as a binary search tree.


5)
If you know it's just one element you don't need to run the whole algorithm. Personally I would look more at how insertion sort does it.

Start at the element that is in the wrong place. Put it aside and move each element one step until you arrive at the position where the out-of-place element should be and write it to that location.

 1 2 3 6 4 5 7


 1 2 3 6 4 5 7
       ^
       6

        ↶
 1 2 3 4 4 5 7 
         ^
         6

          ↶
 1 2 3 4 5 5 7
           ^
           6

          
 1 2 3 4 5 6 7

[leo2008]

Thanks Peter.
For 4)Looking for specific unique items frequently using hashmap?
instead of hashmap, can I use hash table?

[Peter87]

Hash map and hash table are two names for the same thing.

[dhayden]

The right answer often depends on how you find the elements in the collection.

1. If you have an iterator that points to the item, then std::list will remove it in constant time. If you need to find the item first then the time to find it might be much more than the time to remove. I'd suggest std::set if you need to find it by value.

2. std::list or std::deque

3. Again, how will you find these items? If you're swapping items then that seems to mean you're looking them up by index or some other key. If it's an index then array or vector would work. If it's by some other key then consider a std::map.

4. hash table or set.

5. I assume that you don't know which item is out of order. In that case, use std::list. Find the item. Remove it. Search forward or backward until you find where it goes. Insert it. Total time is O(n).

The key to problems like these is to figure out the operations you need to do and then find a collection that works well for them. If there's anything unusual about the problem then try to exploit it.

[leo2008]

Thanks everyone for your inputs. This thread can be closed.