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.
1 2
|
// 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.
1 2 3 4 5 6 7
|
// 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
|