CODEWITHSUNDEEP
c++dictionarylinked-listcontainers
Jonathan Livni
Jonathan Livni

Reputation: 107092

Simple and efficient container in C++ with characteristics of map and list containers

I'm looking for a C++ container that will enjoy both map container and list container benefits.

map container advantages I would like to maintain:

list container advantages I would like to maintain:

A simple example application would be to hold a list of certain valid dates (business dates, holidays, some other set of important dates...), once given a specific date, you could find it immediately "map style" and then find the next valid date "list style".

Upvotes: 2

Views: 1416

Answers (8)

Dialecticus
Dialecticus

Reputation: 16761

How about this one: all dates are stored in std::list<Date>, but you look it up with helper structure stdext::hash_map<Date, std::list<Date>::iterator>. Once you have iterator for the list access to the next element is simple. In your STL implementation it could be std::tr1::unordered_map instead of stdext::hash_map, and there is boost::unordered_map as well.

Upvotes: 2

wilhelmtell
wilhelmtell

Reputation: 58677

You will never find a container that satisfies both O(log n) access and an ordered nature. The reason is that if a container is ordered then inherently it must support an arbitrary order. That's what an ordered nature means: you get to decide exactly where any element is positioned. So to find any element you have to guess where it is. It can be anywhere, because you can place it anywhere!

Note that an ordered sequence is not the same as a sorted sequence. A sorted nature means there is one particular ordering relation between any two elements. An ordered nature means there may be more than one ordering relation among the elements.

Upvotes: 1

sth
sth

Reputation: 229593

std::map is already a sorted container where you can iterate over the contained items in order. It only provides O(log(n)) access, though.

std::tr1::unordered_map (or std::unordered_map in C++0x) has O(1) access but is unsorted.

Do you really need O(1) access? You have to use large datasets and do many lookups for O(log(n)) not being fast enough.

If O(log(n)) is enough, std::map provides everything you are asking for.

Upvotes: 8

CashCow
CashCow

Reputation: 31435

You can store data in a list and have a map to iterators of your list enabling you to find the actual list element itself. This kind of thing is something I often use for LRU containers, where I want a list because I need to move the accessed element to the end to make it the most recently accessed. You can use the splice function to do this, and since the 2003 standard it does not invalidate the iterator as long as you keep it in the same list.

Upvotes: 2

Roger Pate
Roger Pate

Reputation:

  • having an order between the items
  • being able to traverse the list easily

Maps already do both. They are sorted, so you start at begin() and traverse until you hit end(). You can, of course, start at any map iterator; you may find map's find, lower_bound, and related methods helpful.

Upvotes: 2

T.E.D.
T.E.D.

Reputation: 44804

According to Stroustrup, the [] operator for maps is O(log(n)). That is much better than the O(n) you'd get if you were to try such a thing with a list, but it is definitely not O(1). The only container that gives you that for the [] operator is vector.

That aside, you can already do all your listy stuff with maps. Iterators work fine on them. So if I were you, I'd stick with map.

Upvotes: 3

mch
mch

Reputation: 7373

Maps are generally implemented as trees and thus have logarithmic look up time, not O(1), but it sounds like you want a sorted associative container. Hash maps have O(1) best case, O(N) worst case, so perhaps that is what you mean, but they are not sorted, and I don't think they are part of the standard library yet.

In the C++ standard library, map, set, multimap, and multiset are sorted associative containers, but you have to give up the O(1) look up requirement.

Upvotes: 3

Diego Sevilla
Diego Sevilla

Reputation: 29011

If you don't consider the sparse nature, you can take a look at the Boost Multi-Index library. For the sparse nature, you can take a look at the Boost Flyweight library, but I guess you'll have to join both approaches by yourself. Note that your requirements are often contradictory and hard to achieve. For instance, O(1) and order between the items is difficult to maintain efficiently.

Upvotes: 5

Related Questions