Structured Associative Container Concept

(a preliminary sketch of the formal technical concept description)

A Structured Associative Container is a specialization of the C++ 98 standard concept Sorted Associative Container, with extended interface.

The template parameters are similar to that of the Associated Containers:

structured_set<Key, Comp, Alloc>;
structured_map<Key, Value, Comp, Alloc>;

where:

• Key type is itself a container (eg a std::string or std::wstring)
• Comp is a comparison operator that imposes a sort order on Key::value_type elements
  (so if Key is string, Comp compares char, if Key is wstring, Comp applies to wchar_t).
• Value can be any Assignable type
• Alloc is an allocator that manages all memory allocation for the container.

The Comp and the Alloc types have default template arguments.

In other words Structured containers are like Sorted Associative Containers, BUT

• add the requirement on Key template type to be a Forward Container.
  For example, std::basic_string<CharT> is compatible with this requirement.
• change the requirement on the Comp (comparator) template argument to operate on key_type::value_type elements (rather than on key_type itself). Like Sorted Associative comparator, the Comp type shall define a less-like comparison, a Strict Weak Ordering of key-elements.

Associated types

• char_compare: less-like comparison of key elements (establishing a Strict Weak Ordering). The Associative Container key_compare type is also provided, but is defined in terms of char_compare.
  
• subkey_iterator: Used in structure searches. Convertible to iterator (TBD).

In consequence it allows searches involving subparts of keys, ie with shared prefix and/or with shared middle parts.

---

Deprecated search interface

In the first iteration, additional searches are provided as methods on the containers. This will be changed to use free functions operating on subkey_iterator. The deprecated search methods will still be provided as convenience functions; to migrate your code from present version to the new interface, will mean moving the object name to the first argument, but also to respecify the search_results_list type. (This sloppy-hackish type is by itself reason not to keep the method interface)

See Structured search overview and ternary_tree Structure search section.