2

I have a map which stores attacks for different ports. Now I am confused as for how to store attack details as the value. Also, there can be multiple attacks for one port.

AttackDetails is a structure containing various details of each attack.

Now I have two approaches for the map:

std::map <int, std::list<AttackDetails>>
std::map <int, std::list<<std::shared_ptr<AttackDetails>>>

There won't be much insertion or deletion but there will be a lot of searchings for ports in the map. Kindly tell me if there is any major performance issue in either of these or any better solution to it?

I need to access the list while deleting the attack details where I will need to traverse through the list and find similar attack id and stop that particular attack.

Archit J
  • 152
  • 8
  • 2
    Don't look at the smart pointers as simple self-deleting pointers. Instead see them from an *ownership* point of view. Is `AttackDetails` a resource that can only have a single owner (`std::unique_ptr`)? Can the ownership be shared (`std::shared_ptr`)? Or is ownership semantics irrelevant (plain objects or non-owning pointers)? – Some programmer dude Jan 22 '19 at 11:12
  • Also, the default container should almost always be `std::vector`. What is the reason you picked `std::list`? – Some programmer dude Jan 22 '19 at 11:12
  • 2
    Rather than a `map` of `list`s (or even better, `vector`s), I suggest a `multimap`. – HolyBlackCat Jan 22 '19 at 11:12
  • Is more than one entity responsible for deleting `AttackDetails` objects? Or do they die when they are removed from the map? – Galik Jan 22 '19 at 11:14
  • 1
    Lastly, remember that `std::map` (and `std::multimap`) is *ordered* by the key. Do you need it to be ordered? If not, then I suggest you use the unordered variants instead. – Some programmer dude Jan 22 '19 at 11:14
  • If there will be little modifications but a lot of searching, `std::list` is likely to be the worst performing data structure. Use `std::set` or sorted `std::vector`. – Fureeish Jan 22 '19 at 11:14
  • @Fureeish massive searching is done for port only not for the values in map. – Archit J Jan 22 '19 at 11:29
  • @HolyBlackCat I need the list of values to be stored according the time of insertion so i can process the attacks accordingly. – Archit J Jan 22 '19 at 11:35
  • I do not understand what `shared_ptr` has to do with searching performance at all. – Vittorio Romeo Jan 22 '19 at 11:36
  • @Someprogrammerdude I have used list as I am going to push the attack details in it and there won't be a lot of attacks and i don't need vector access. If i need access of details i need to do searching inside the attack details to find the attack I need to stop. – Archit J Jan 22 '19 at 11:41
  • @VittorioRomeo Excess indirection kills cache performance. Like, _kills it_. Then again, the OP already has practically none of that thanks to the map and the list. – Lightness Races in Orbit Jan 22 '19 at 11:45
  • @VittorioRomeo I did not state the issue correctly. I need to search in values for when I need to stop a particular attack. Travershing through the list would be needed which will access elements of attack details but there will not be much of insertion or deletion I repeat. – Archit J Jan 22 '19 at 11:47
  • 1
    @LightnessRacesinOrbit: I know that. I just don't understand why `shared_ptr` is even being considered – Vittorio Romeo Jan 22 '19 at 11:48

2 Answers2

2

Since you seem to just need the AttackDetails itself, not just ones whose lifetimes are managed with RAII semantics, I think that

std::map<int, std::list<AttackDetails>>

would be more preferable than std::map<int, std::list<<std::shared_ptr<AttackDetails>>>.

Similar concepts are stated in R.30 of C++ Core Guidelines as follows. Although this is not the exactly same situation with the current problem, but this point of view should be shared with us:

R.30: Take smart pointers as parameters only to explicitly express lifetime semantics

Reason Accepting a smart pointer to a widget is wrong if the function just needs the widget itself. It should be able to accept any widget object, not just ones whose lifetimes are managed by a particular kind of smart pointer. A function that does not manipulate lifetime should take raw pointers or references instead.

...any better solution to it?

  • Use std::unordered_map if you do not need to sort the elements by key.

  • Elements of std::list are scattered in memory. Hence it's access operations usually cause cache misses and would show poor performance. Even if erasing any single element of them by std::list::erase has the complexity O(1), the access performance is much slower and sometimes makes sense to use other STL containers. I recommend you to test the performance and compare the results between std::list, std::vector and std::deque.

Community
  • 1
  • 1
Hiroki
  • 2,780
  • 3
  • 12
  • 26
0

Do you need shared ownership of an AttackDetails instance? If not, then you shouldn't use std::shared_ptr.

If you want to optimize searching performance, then consider using a hash data structure such as unordered_map (or a faster third-party solution), as that will bring down your complexity from O(log N) to O(1).

Vittorio Romeo
  • 90,666
  • 33
  • 258
  • 416