0

I'm trying to find a cheat sheet for the containers of the STL. So, if someone was designing a system and didn't have the STL containers memorized, they could refer to the cheat sheet and have a better chance of choosing an efficient container to suit their particular problem.

Is there a table that shows big O notation for each of the STL container methods?

Homer6
  • 15,034
  • 11
  • 61
  • 81
  • 1
    What would be the point benchmarking different architectures? They are.. different. – Neil Kirk Jul 27 '13 at 06:17
  • Answers in this format would be incredibly long. Voting to close. – Rapptz Jul 27 '13 at 06:18
  • I won't vote to close, but I think this would be better if you narrowed it down to a specific container. Otherwise, it's probably too broad. – Mysticial Jul 27 '13 at 06:19
  • Science is the practice of measurement. What is the use in measurement anyways? It has never served us before. – Homer6 Jul 27 '13 at 06:19
  • @Mysticial The point of this question is to find a comprehensive list. Depth is secondary. – Homer6 Jul 27 '13 at 06:20
  • Please see the updated note. I think that this use case affects a number of different programmers. Regarding the formats that have been presented so far, I don't feel that they provide to tool with which a novice or intermediate c++ programmer can very quickly make good STL collection decisions with. The point of this reference is for them to make quick, appropriate choices in containers. – Homer6 Jul 27 '13 at 06:43
  • 1
    vectors are fast for indexing, slow for inserting/removing, especially in the middle or beginning. lists are fast for inserting/removing anywhere but slow for finding a particular index. maps are inbetween. deques are like vectors but inserting/removing is identical performance on beginning or end. – Neil Kirk Jul 27 '13 at 06:51
  • benchmarking - depends on what you store in those collections. also, real life performance is often dependent on memory locality, but in practice it's quite hard to benchmark how your program will behave. – Karoly Horvath Jul 27 '13 at 07:30
  • @KarolyHorvath hence the "benchmark data may be hard to come by or controversial"... cheap benchmarks are better than no benchmarks... everyone knows that they can be misleading. However, they do give you *some* indication of which ballpark you're in. – Homer6 Jul 27 '13 at 07:34
  • The C++ standard itself has tables with complexities for each container operation. Most of them are pretty obvious, so it's not that useful unless you have no clue what a vector or a list is. The only exception is list::size() - unless you know about list::splice(). – DanielKO Jul 27 '13 at 07:49
  • @Neil Kirk: see Stroustrup's key note "C++11 Style", on Going Native 2012. Unless your vector is larger than your cache, even shifting all elements around for insert/erase can be still faster than list, once you take traversal into account. – DanielKO Jul 27 '13 at 07:53
  • @DanielKO, I'm not sure what you mean, but in the general case a vector may contain an object which is expensive to copy. – Neil Kirk Jul 27 '13 at 07:54
  • @DanielKO Interesting. That seems like it would cover a lot of cases. Does he elaborate with metrics? – Homer6 Jul 27 '13 at 08:23
  • Stroustrup's point is: use vector for sequences, unless you measured it to be slower than specific alternatives. He presented an (invisible, thanks to powerpoint woes) graph showing how vectors benefit from data locality, versus lists that can jump all over the place to reach the next node. Here's the graph: http://bulldozer00.com/2012/02/09/vectors-and-lists/ That said, lists don't invalidate iterators like vectors, so you might not have a choice. They do different things, that's the gist. – DanielKO Jul 27 '13 at 08:32
  • @DanielKO This is precisely why I wanted to see benchmarks. Data locality and real work systems can dramatically impact the "best case" usage for the collections (versus the Big-O generalization of their growth). Big-O is very useful "as a problems grows", but what if you only use collections under 64K? What if the collections that you use are below 64K 90%+ of the time? Real world metric are important considerings when choosing an appropriate data structure. Wouldn't you agree? – Homer6 Jul 27 '13 at 08:40
  • These metrics will come from a benchmark for your particular scenario. Your results on a dual-core laptop are not directly applicable on my 64-core 512 GB server. All the possible scenarios can't possibly fit in any cheat sheet. – DanielKO Jul 27 '13 at 08:48
  • @DanielKO Forget benchmarks, I'll settle for just a Big-O cheatsheet. That doesn't seem too improbable, does it? – Homer6 Jul 27 '13 at 08:50
  • 1
    The table of big-O complexities would have to be about 1/2 as large as the table [here](http://en.cppreference.com/w/cpp/container) to be complete. That's way too long for a [so] answer. If you're asking for an external resource, it sounds like `"asking [for] us to recommend or find a tool, library or favorite off-site resource"` (copied from an off-topic close reason). – Bernhard Barker Jul 27 '13 at 13:18
  • @Dukeling Perfect! Now I can color code this table. Thank you Dukeling! – Homer6 Jul 27 '13 at 15:04
  • @Dukeling As for the close reasoning, I fail to see how my question is any different from http://stackoverflow.com/questions/181693/what-are-the-complexity-guarantees-of-the-standard-containers why didn't they post that entire article? Off-site resources are very useful and are in a large majority of answers. – Homer6 Jul 27 '13 at 15:09
  • There's also this: http://www.cplusplus.com/reference/stl/ – Homer6 Jul 27 '13 at 15:24
  • @Homer6 I'm pretty sure that that question wouldn't have lasted very long had it been asked recently, rather than almost 5 years ago (what's appropriate for StackOverflow has changed quite a bit since then). Off-site resources are very useful, but questions asking for them are not on-topic for StackOverflow (that's simply the way StackOverflow decided to go), although answers to questions that ask about some specific problem can link to an off-site resource containing, for example, a more detailed explanation of what was provided in the answer. – Bernhard Barker Jul 27 '13 at 17:07
  • http://john-ahlgren.blogspot.com/2013/10/stl-container-performance.html Just have a look here :) – Shalomi90 Nov 20 '18 at 14:22

3 Answers3

4

Most online references include such data (other than benchmarks, which I believe aren't very useful for most people, if not done by themselves).

For example, look at http://en.cppreference.com/w/
It has a 'Complexity' field for most methods.

manasij7479
  • 1,665
  • 1
  • 14
  • 22
  • I see complexity for most containers in general. But I don't see it for each method. Can you point to a specific page to illustrate what you mean by "complexity for most methods"? Ideally, this would be in a single table. – Homer6 Jul 27 '13 at 06:27
  • Try also this website, here is an example method with a complexity section http://www.cplusplus.com/reference/list/list/insert/ – Neil Kirk Jul 27 '13 at 06:29
  • @NeilKirk Can you post a separate answer please? I feel that that is closer to answering the question. – Homer6 Jul 27 '13 at 06:31
  • It would be better if you link the [containers library page](http://en.cppreference.com/w/cpp/container/set/clear). – juanchopanza Jul 27 '13 at 06:41
  • cplusplus.com is not considered a great resource by the C++ community. – Rapptz Jul 27 '13 at 06:41
  • I'm sorry, I didn't realise I need an official badge to be in the C++ community and have an opinion. – Neil Kirk Jul 27 '13 at 06:43
  • @NeilKirk Don't worry. Rapptz is just a troll that would vote to close and encourage others to vote to close a question that could potentially help a great number of novice c++ programmers. I guess it's better to keep the jobs for ourselves... am I right?!?!? – Homer6 Jul 27 '13 at 06:51
  • @Homer6 Yeah I'm definitely a troll for following the rules of StackOverflow. Spoiler: If you're ever read the close reason I just used it mentions: "There are either too many possible answers, or good answers would be too long for this format. Please add details to narrow the answer set or to isolate an issue that can be answered in a few paragraphs." So no, I'm not "trolling", your question does not follow the site's format for questions. I think you're just upset that I used my right to vote. – Rapptz Jul 27 '13 at 06:54
  • You're right. Is there a table that shows big O notation for the STL containers? USELESS! How did I ever think that anyone would ever find that useful? You're too concerned with being right versus answering the question. It clearly states that even Big O notation for each of the operations of the containers of the STL would be acceptable. How is that too much information? I fully expected "too much information" from all of the primates of this planet, but not the c++ community. I guess I'm just too optimistic. Please don't close this. People can use it to make better software. – Homer6 Jul 27 '13 at 07:01
  • Yes and he likes to make fun of posters on the stackoverflow chat room. He described your question as ****y. – Neil Kirk Jul 27 '13 at 07:06
  • @Homer6 : Look at http://en.cppreference.com/w/cpp/container/vector/insert – manasij7479 Jul 27 '13 at 09:22
2

Here you can find a reference for the STL data structures and their methods, which usually have a complexity description on their page.

http://www.cplusplus.com/reference/stl/

Neil Kirk
  • 21,327
  • 9
  • 53
  • 91
  • +1 very close to what I was looking for. It would be an improvement would be see it in a single table. – Homer6 Jul 27 '13 at 06:34
1

This is probably the closest thing to what you're looking for:

What are the complexity guarantees of the standard containers?

Community
  • 1
  • 1
Karoly Horvath
  • 94,607
  • 11
  • 117
  • 176