I have been using the Java documentation for OpenJDK 1.7, but I am not seeing a lot of information on Big-Oh notation in terms of complexities of operations between different container types, which is making it harder to know which is the most performance collection to use for my task at hand; for example, implementing a stack or a queue.  I have been using an ArrayDeque for both just following my C++ instincts. The basics are there, such as ArrayList is faster than LinkedList, but there doesn't seem to be a consistent section for this. In C++ documentation, there is a section like the one below. Any Javadoc references that speak about complexities between containers would be helpful.  C++ example:      Complexity      Average case constant, worst case linear in the size of the container.   Java Example: Embedded in the ArrayList documentation I found the following     The size, isEmpty, get, set, iterator, and listIterator operations run in constant time. The add operation runs in amortized constant time, that is, adding n elements requires O(n) time. All of the other operations run in linear time (roughly speaking). The constant factor is low compared to that for the LinkedList implementation.
46764
I may be teaching a "Java crash-course" soon.  While it is probably safe to assume that the audience members will know Big-O notation, it is probably not safe to assume that they will know what the order of the various operations on various collection implementations is.  I could take time to generate a summary matrix myself, but if it's already out there in the public domain somewhere, I'd sure like to reuse it (with proper credit, of course.)  Anyone have any pointers?
113958
I've heard many people say that if the number of expected elements in the container is relatively small, it is better to use std::vector instead of std::map even if you were to use the container for lookups only and not iterating.  What is the real reason behind this?  Obviously the lookup performance of std::map cannot be worse than std::vector (although it may differ in nanoseconds/microseconds) so does it have something to do with memory usage?  Does std::vector fare any better/worse than std::map in fragmenting the virtual address space?  I am using the STL library that comes along with Visual Studio (i.e. Microsoft's implementation).  Does that make any difference compared to other implementations?
122587
I am trying to find a generic way of accessing a set of containers. I have a standard vector and list in addition to another custom list.  The custom list defines an iterator;  class Iterator: public std::iterator&lt;std::forward_iterator_tag, T&gt; {     // ... }  Iterator begin() {     return (Iterator(root)); }  Iterator end() {     return (Iterator(NULL)); }   with the appropriate operators overloaded.   Ideally, I would like to do this;  class Foo { public:     Foo() {         std::list&lt;int&gt; x;         std::vector&lt;int&gt; y;         custom_list&lt;int&gt; z;          iter = x.begin(); // OR         iter = y.begin(); // OR         iter = z.begin();          // ...     }; private:     std::iterator&lt;int&gt; iter; };   But obviously these are all iterators of different types. I can assume all the containers are of the same type however.  Is there an elegant way to solve this problem?
282
Conditions: do not modify the original lists; JDK only, no external libraries. Bonus points for a one-liner or a JDK 1.3 version. Is there a simpler way than: List&lt;String&gt; newList = new ArrayList&lt;String&gt;(); newList.addAll(listOne); newList.addAll(listTwo);
40034
Coming from C++ to Java, the obvious unanswered question is why didn't Java include operator overloading?  Isn't Complex a, b, c; a = b + c; much simpler than Complex a, b, c; a = b.add(c);?  Is there a known reason for this, valid arguments for not allowing operator overloading? Is the reason arbitrary, or lost to time?
827
If I have an object implementing the Map interface in Java and I wish to iterate over every pair contained within it,  what is the most efficient way of going through the map?  Will the ordering of elements depend on the specific map implementation that I have for the interface?
77207
I would like to write a function GetHashCodeOfList() which returns a hash-code of a list of strings regardless of order. Given 2 lists with the same strings should return the same hash-code.   ArrayList list1 = new ArrayList()     list1.Add("String1"); list1.Add("String2"); list1.Add("String3");      ArrayList list2 = new ArrayList()     list2.Add("String3");     list2.Add("String2");  list2.Add("String1");  GetHashCodeOfList(list1) = GetHashCodeOfList(list2) //this should be equal.   I had a few thoughts:    I can first sort the list, then combine the sorted list into 1 long string and then call GetHashCode(). However sorting is a slow operation. I can get the hash of each individual string (by calling string.GetHashCode()) in the list, then multiplying all hashes and calling Mod UInt32.MaxValue.  For example: "String1".GetHashCode() * "String2".GetHashCode * … MOD UInt32.MaxValue. But this results in a number overflow.   Does anyone have any thoughts?  Thanks in advance for your help.
53155
Anyone have a good rule of thumb for choosing between different implementations of Java Collection interfaces like List, Map, or Set?  For example, generally why or in what cases would I prefer to use a Vector or an ArrayList, a Hashtable or a HashMap?
113923
What (if any) performance advantages are offered by using iterators. It seems like the 'Right Way' to solve many problems, but does it create faster/more memory-conscious code? I'm thinking specifically in Python, but don't restrict answers to just that.
51785
I'd like to implement a big int class in C++ as a programming exercise&mdash;a class that can handle numbers bigger than a long int.  I know that there are several open source implementations out there already, but I'd like to write my own.  I'm trying to get a feel for what the right approach is.  I understand that the general strategy is get the number as a string, and then break it up into smaller numbers (single digits for example), and place them in an array.  At this point it should be relatively simple to implement the various comparison operators.  My main concern is how I would implement things like addition and multiplication.  I'm looking for a general approach and advice as opposed to actual working code.
40045
I wonder whether there is any automatic way of determining (at least roughly) the Big-O time complexity of a given function?  If I graphed an O(n) function vs. an O(n lg n) function I think I would be able to visually ascertain which is which; I'm thinking there must be some heuristic solution which enables this to be done automatically.  Any ideas?  Edit: I am happy to find a semi-automated solution, just wondering whether there is some way of avoiding doing a fully manual analysis.
54815
I'm looking for a class in java that has key-value association, but without using hashes.  Here is what I'm currently doing:   Add values to a Hashtable. Get an iterator for the Hashtable.entrySet(). Iterate through all values and:   Get a Map.Entry for the iterator. Create an object of type Module (a custom class) based on the value. Add the class to a JPanel.  Show the panel.   The problem with this is that I do not have control over the order that I get the values back, so I cannot display the values in the a given order (without hard-coding the order).  I would use an ArrayList or Vector for this, but later in the code I need to grab the Module object for a given Key, which I can't do with an ArrayList or Vector.  Does anyone know of a free/open-source Java class that will do this, or a way to get values out of a Hashtable based on when they were added?  Thanks!
79598
I wonder if there is a counterpart to java.util.LinkedHashMap in .NET? (ie. the elements are (re)ordered automatically if I access an element. (boolean accessOrder) ).
100259
Is std::string size() a O(1) operation?  The implementation of STL I'm using is the one built into VC++
46616
Currently I am . Having never used a library for working with large integers before, this seems slow, on the order of 10 times slower, even for ulong length numbers. Does anyone have any better (preferably free) libraries, or is this level of performance normal?
80355
I have this struct:  struct Map {     public int Size;      public Map ( int size )     {         this.Size = size;     }      public override string ToString ( )     {         return String.Format ( "Size: {0}", this.Size );     } }   When using array, it works:  Map [ ] arr = new Map [ 4 ] {     new Map(10),     new Map(20),     new Map(30),     new Map(40)};  arr [ 2 ].Size = 0;   But when using List, it doesn't compile:  List&lt;Map&gt; list = new List&lt;Map&gt; ( ) {     new Map(10),     new Map(20),     new Map(30),     new Map(40)};  list [ 2 ].Size = 0;   Why?
55385
This is one of the possible ways I come out:  struct RetrieveKey {     template &lt;typename T&gt;     typename T::first_type operator()(T keyValuePair) const     {         return keyValuePair.first;     } };  map&lt;int, int&gt; m; vector&lt;int&gt; keys;  // Retrieve all keys transform(m.begin(), m.end(), back_inserter(keys), RetrieveKey());  // Dump all keys copy(keys.begin(), keys.end(), ostream_iterator&lt;int&gt;(cout, "\n"));   Of course, we can also retrieve all values from the map by defining another functor RetrieveValues.  Is there any other way to achieve this easily? (I'm always wondering why std::map does not include a member function for us to do so.)