Associative

Associative
Prev	Chapter 9. + Containers + +	Next

Insertion Hints

+ Section [23.1.2], Table 69, of the C++ standard lists this + function for all of the associative containers (map, set, etc): +

+      a.insert(p,t);
+

+ where 'p' is an iterator into the container 'a', and 't' is the + item to insert. The standard says that “t is + inserted as close as possible to the position just prior to + p.” (Library DR #233 addresses this topic, + referring to N1780. + Since version 4.2 GCC implements the resolution to DR 233, so + that insertions happen as close as possible to the hint. For + earlier releases the hint was only used as described below. +

+ Here we'll describe how the hinting works in the libstdc++ + implementation, and what you need to do in order to take + advantage of it. (Insertions can change from logarithmic + complexity to amortized constant time, if the hint is properly + used.) Also, since the current implementation is based on the + SGI STL one, these points may hold true for other library + implementations also, since the HP/SGI code is used in a lot of + places. +

+ In the following text, the phrases greater + than and less than refer to the + results of the strict weak ordering imposed on the container by + its comparison object, which defaults to (basically) + “<”. Using those phrases is semantically sloppy, + but I didn't want to get bogged down in syntax. I assume that if + you are intelligent enough to use your own comparison objects, + you are also intelligent enough to assign “greater” + and “lesser” their new meanings in the next + paragraph. *grin* +

+ If the hint parameter ('p' above) is equivalent to: +

+ begin(), then the item being inserted should + have a key less than all the other keys in the container. + The item will be inserted at the beginning of the container, + becoming the new entry at begin(). +
+ end(), then the item being inserted should have + a key greater than all the other keys in the container. The + item will be inserted at the end of the container, becoming + the new entry before end(). +
+ neither begin() nor end(), then: + Let h be the entry in the container pointed to + by hint, that is, h = *hint. Then + the item being inserted should have a key less than that of + h, and greater than that of the item preceding + h. The new item will be inserted between + h and h's predecessor. +

+ For multimap and multiset, the + restrictions are slightly looser: “greater than” + should be replaced by “not less than”and “less + than” should be replaced by “not greater + than.” (Why not replace greater with + greater-than-or-equal-to? You probably could in your head, but + the mathematicians will tell you that it isn't the same thing.) +

+ If the conditions are not met, then the hint is not used, and the + insertion proceeds as if you had called a.insert(t) + instead. (Note that GCC releases + prior to 3.0.2 had a bug in the case with hint == + begin() for the map and set + classes. You should not use a hint argument in those releases.) +

+ This behavior goes well with other containers' + insert() functions which take an iterator: if used, + the new item will be inserted before the iterator passed as an + argument, same as the other containers. +

+ Note also that the hint in this + implementation is a one-shot. The older insertion-with-hint + routines check the immediately surrounding entries to ensure that + the new item would in fact belong there. If the hint does not + point to the correct place, then no further local searching is + done; the search begins from scratch in logarithmic time. +

bitset

Size Variable

+ No, you cannot write code of the form +

+      #include <bitset>
+
+      void foo (size_t n)
+      {
+	  std::bitset<n>   bits;
+	  ....
+      }
+

+ because n must be known at compile time. Your + compiler is correct; it is not a bug. That's the way templates + work. (Yes, it is a feature.) +

+ There are a couple of ways to handle this kind of thing. Please + consider all of them before passing judgement. They include, in + no chaptericular order: +

A very large N in bitset<N>.
A container<bool>.
Extremely weird solutions.

+ A very large N in + bitset<N>. It has been + pointed out a few times in newsgroups that N bits only takes up + (N/8) bytes on most systems, and division by a factor of eight is + pretty impressive when speaking of memory. Half a megabyte given + over to a bitset (recall that there is zero space overhead for + housekeeping info; it is known at compile time exactly how large + the set is) will hold over four million bits. If you're using + those bits as status flags (e.g., + “changed”/“unchanged” flags), that's a + lot of state. +

+ You can then keep track of the “maximum bit used” + during some testing runs on representative data, make note of how + many of those bits really need to be there, and then reduce N to + a smaller number. Leave some extra space, of course. (If you + plan to write code like the incorrect example above, where the + bitset is a local variable, then you may have to talk your + compiler into allowing that much stack space; there may be zero + space overhead, but it's all allocated inside the object.) +

+ A container<bool>. The + Committee made provision for the space savings possible with that + (N/8) usage previously mentioned, so that you don't have to do + wasteful things like Container<char> or + Container<short int>. Specifically, + vector<bool> is required to be specialized for + that space savings. +

+ The problem is that vector<bool> doesn't + behave like a normal vector anymore. There have been + journal articles which discuss the problems (the ones by Herb + Sutter in the May and July/August 1999 issues of C++ Report cover + it well). Future revisions of the ISO C++ Standard will change + the requirement for vector<bool> + specialization. In the meantime, deque<bool> + is recommended (although its behavior is sane, you probably will + not get the space savings, but the allocation scheme is different + than that of vector). +

+ Extremely weird solutions. If + you have access to the compiler and linker at runtime, you can do + something insane, like figuring out just how many bits you need, + then writing a temporary source code file. That file contains an + instantiation of bitset for the required number of + bits, inside some wrapper functions with unchanging signatures. + Have your program then call the compiler on that file using + Position Independent Code, then open the newly-created object + file and load those wrapper functions. You'll have an + instantiation of bitset<N> for the exact + N that you need at the time. Don't forget to delete + the temporary files. (Yes, this can be, and + has been, done.) +

+ This would be the approach of either a visionary genius or a + raving lunatic, depending on your programming and management + style. Probably the latter. +

+ Which of the above techniques you use, if any, are up to you and + your intended application. Some time/space profiling is + indicated if it really matters (don't just guess). And, if you + manage to do anything along the lines of the third category, the + author would love to hear from you... +

+ Also note that the implementation of bitset used in libstdc++ has + some extensions. +

Type String

+ Bitmasks do not take char* nor const char* arguments in their + constructors. This is something of an accident, but you can read + about the problem: follow the library's “Links” from + the homepage, and from the C++ information “defect + reflector” link, select the library issues list. Issue + number 116 describes the problem. +

+ For now you can simply make a temporary string object using the + constructor expression: +

+      std::bitset<5> b ( std::string(“10110”) );
+

+ instead of +

+      std::bitset<5> b ( “10110” );    // invalid
+