# map, set, multimap, and multiset

These are implemented using a &lt;a href=&quot;http://en.wikipedia.org/wiki/Red-black_tree&quot;&gt;red-black tree&lt;/a&gt;, a type of &lt;a href=&quot;http://en.wikipedia.org/wiki/Balanced_binary_search_tree&quot;&gt;balanced binary search tree&lt;/a&gt;.  They have the following asymptotic run times:

Insertion: O(log n)  
Lookup: O(log n)  
Deletion: O(log n)

# hash\_map, hash\_set, hash\_multimap, and hash\_multiset

These are implemented using &lt;a href=&quot;http://en.wikipedia.org/wiki/Hash_table&quot;&gt;hash tables&lt;/a&gt;.  They have the following runtimes:

Insertion: O(1) expected, O(n) worst case  
Lookup: O(1) expected, O(n) worst case  
Deletion: O(1) expected, O(n) worst case

If you use a proper hash function, you&#39;ll almost never see the worst case behavior, but it is something to keep in mind — see [Denial of Service via Algorithmic Complexity Attacks](http://www.usenix.org/events/sec03/tech/full_papers/crosby/crosby.pdf) by Crosby and Wallach for an example of that.

For **set**, **multiset**, **map**, **multimap** the time complexity for insertion, deletion and retrieving information is **O(logn)** as they follow the balance binary tree to structure the data.

 For **unordered_set** and **unordered_map**, **hashing** method is utilize to structure the data. So the time complexity for this is **O(1)**. This is perfect way to perform any operation on information in case your prerequisite is not to have data in sorted order.

I want to generate some formatted output of data retrieved from an MS-Access database and stored in a _DataTable_ object/variable, myDataTable. However, some of the fields in myDataTable cotain _dbNull_ data. So, the following VB.net code snippet will give errors if the value of any of the fields _lastname_, _intials_, or _sID_ is _dbNull_.
       
       dim myDataTable as DataTable
       dim tmpStr as String
       dim sID as Integer = 1

       ...
       myDataTable = myTableAdapter.GetData() &#39; Reads the data from MS-Access table
       ...

       For Each myItem As DataRow In myDataTable.Rows

        tmpStr = nameItem(&quot;lastname&quot;) + &quot; &quot; + nameItem(&quot;initials&quot;)
        
        If myItem(&quot;sID&quot;)=sID Then
            &#39; Do something
        End If
        
        &#39; print tmpStr

       Next

So, how do i get the above code to work when the fields may contain _dbNull_ without having to check each time if the data is dbNull as in [this question](https://stackoverflow.com/questions/105671/any-systemdbnullvalue-vs-any-is-systemdbnull)?

handling dbnull data in vb.net

The following code

    number=1
    if [[ $number =~ [0-9] ]]
    then
      echo matched
    fi

works. If I try to use quotes in the regex, however, it stops:

    number=1
    if [[ $number =~ &quot;[0-9]&quot; ]]
    then
      echo matched
    fi

I tried `&quot;\[0-9\]&quot;`, too. What am I missing?

Funnily enough, [bash advanced scripting guide][1] suggests this should work.

Bash version 3.2.39.


  [1]: http://www.tldp.org/LDP/abs/html/abs-guide.html#REGEXMATCHREF

bash regex with quotes?

I would like to know the complexity in Big O notation of the STL multiset, map and hash map classes when:

 - inserting entries
 - accessing entries
 - retrieving entries
 - comparing entries

multiset, map and hash map complexity

<p>I would like to know the complexity in Big O notation of the STL multiset, map and hash map classes when:</p>
<ul>
<li>inserting entries</li>
<li>accessing entries</li>
<li>retrieving entries</li>
<li>comparing entries</li>
</ul>


I&#39;m using the &#39;using&#39; declaration in C++ to add std::string and std::vector to the local namespace (to save typing unnecessary &#39;std::&#39;s).

    using std::string;
    using std::vector;

    class Foo { /*...*/ };


What is the scope on this declaration?  If I do this in a header, will it inject these &#39;using&#39; declarations into every cpp file that includes the header?

What&#39;s the scope of the &quot;using&quot; declaration in C++?

I was taking a look through some open-source C++ code and I noticed a lot of double underscores used within in the code, mainly at the start of variable names.

    return __CYGWIN__;

Just wondering: Is there a reason for this, or is it just some people&#39;s code styles?  I would think that it makes it hard to read.


Why do people use __ (double underscore) so much in C++

What is the difference between `private` and `protected` members in C++ classes?
   
I understand from best practice conventions that variables and functions which are not called outside the class should be made `private`&amp;mdash;but looking at my MFC project, MFC seems to favor `protected`.

What&#39;s the difference and which should I use?

What is the difference between private and protected members of C++ classes?

I have some numbers of different length (like 1, 999, 76492, so on) and I want to convert them all to strings with a common length (for example, if the length is 6, then those strings will be: &#39;000001&#39;, &#39;000999&#39;, &#39;076492&#39;). 

In other words, I need to add correct amount of leading zeros to the number.

    int n = 999;
    string str = some_function(n,6);
    //str = &#39;000999&#39;

Is there a function like this in C++?



Convert a number to a string with specified length in C++

With VS2005, I want to create a DLL and automatically export all symbols without adding `__declspec(dllexport)` everywhere, and without hand-creating `.def` files. Is there a way to do this?

Export all symbols when creating a DLL

Recently, I noticed some people mentioning that `std::list::size()` has a linear complexity.&lt;br&gt;
According to [some][1] [sources][2], this is in fact implementation dependent as the standard doesn&#39;t say what the complexity has to be.&lt;br&gt;
The comment [in this blog entry][3] says:

&gt; Actually, it depends on which STL you
&gt; are using. Microsoft Visual Studio V6
&gt; implements size() as {return (_Size);
&gt; } whereas gcc (at least in versions
&gt; 3.3.2 and 4.1.0) do it as { return std::distance(begin(), end()); } The
&gt; first has constant speed, the second
&gt; has o(N) speed

  [1]: http://www.cplusplus.com/reference/stl/list/size.html
  [2]: http://bytes.com/forum/thread60248.html
  [3]: http://ahlamnote.blogspot.com/2006/11/stl-list-size-method-is-slow.html


 1. So my guess is that for the VC++ crowd `size()` has constant complexity as Dinkumware
    probably won&#39;t have changed that fact since VC6. Am I right there?&lt;br&gt;
 2. What does it look like currently in `gcc`? If it is really O(n), why did the
    developers choose to do so?

Is list::size() really O(n)?

I understand Big-O notation, but I don&#39;t know how to calculate it for many functions. In particular, I&#39;ve been trying to figure out the computational complexity of the naive version of the Fibonacci sequence:

    int Fibonacci(int n)
    {
        if (n &lt;= 1)
            return n;
        else
            return Fibonacci(n - 1) + Fibonacci(n - 2);
    }

What is the computational complexity of the Fibonacci sequence and how is it calculated?

Computational complexity of Fibonacci Sequence

I&#39;d prefer as little formal definition as possible and simple mathematics.


What is a plain English explanation of &quot;Big O&quot; notation?

I need to calculate the time complexity of the following code:

    for (i = 1; i &lt;= n; i++)
    {
      for(j = 1; j &lt;= i; j++)
      {
       // Some code
      }
    }

Is it *O(n^2)*?

Time complexity of nested for-loop

Are there any O(1/n) algorithms?

Or anything else which is less than O(1)? 


Are there any O(1/n) algorithms?

I believe there&#39;s a way to find the kth largest element in an unsorted array of length n in O(n).  Or perhaps it&#39;s &quot;expected&quot; O(n) or something.  How can we do this?



How to find the kth largest element in an unsorted array of length n in O(n)?

What is the Big-O time complexity of the following nested loops:


&lt;!-- language: lang-cpp --&gt;

    for (int i = 0; i &lt; N; i++) {
        for (int j = i + 1; j &lt; N; j++) {
            System.out.println(&quot;i = &quot; + i + &quot; j = &quot; + j);
        }
    }

Would it be *O(N^2)* still?  

What is the Big-O of a nested loop, where number of iterations in the inner loop is determined by the current iteration of the outer loop?

With the reference of this [answer](https://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it#3368), what is Theta (tight bound)?

Omega is lower bound, quite understood, the minimum time an algorithm may take. And we know Big-O is for upper bound, means the maximum time an algorithm may take.  But I have no idea regarding the Theta.


Content Type	Original Author	Original Content on Stackoverflow
Question	Harry	View Question on Stackoverflow
Solution 1 - C++	Adam Rosenfield	View Answer on Stackoverflow
Solution 2 - C++	Aniket Babhulkar	View Answer on Stackoverflow

multiset, map and hash map complexity

C++ Problem Overview

C++ Solutions

Solution 1 - C++

map, set, multimap, and multiset

hash_map, hash_set, hash_multimap, and hash_multiset

Solution 2 - C++

bash regex with quotes?

handling dbnull data in vb.net

Attributions