CODEWITHSUNDEEP
c++dictionaryvectorstl
Kyudos
Kyudos

Reputation: 735

STL Vectorised Map - Looking for Best Practice

I'm not too experienced with STL, so I'm unsure of the best approach here.

I have a set of actions, each tied to a unique ID. To ensure I don't duplicate the actions, I initially thought to store them in a std::map, keyed on the ID. However, I need to retain strict ordering internally a la std::vector, such that when I unwind my actions they appear in the reverse order they were added.

Any given list of actions could be anywhere from one or two items, to several thousand. Will I lose anything if I switch to manually checking a vector for duplicates (i.e., iterating through and checikng IDs)? Or is there some form of map or other container I can use that lets me lookup by ID, but doesn't internally sort or re-order my elements?

Upvotes: 0

Views: 291

Answers (2)

zzk
zzk

Reputation: 1387

Sounds to me that you need Boost.MultiIndex

The Boost Multi-index Containers Library provides a class template named multi_index_container which enables the construction of containers maintaining one or more indices with different sorting and access semantics. Indices provide interfaces similar to those of STL containers, making using them familiar. The concept of multi-indexing over the same collection of elements is borrowed from relational database terminology and allows for the specification of complex data structures in the spirit of multiply indexed relational tables where simple sets and maps are not enough. A wide selection of indices is provided, modeled after analogous STL containers like std::set, std::list and hashed sets.

Upvotes: 2

nogard
nogard

Reputation: 9716

You might want to use boost:multi_index map, which can support order of insertion for the map.

struct Item 
{
      string name;
      int data;
};
struct ItemTag {};
typedef multi_index_container<
    Item,
    indexed_by<
        random_access<>, // this index represents insertion order
        hashed_unique< tag<ItemTag>, member<Item, string, &Item::name> >
    >
> ItemsMap;

Upvotes: 2

Related Questions