CODEWITHSUNDEEP
c++stl
Alex Strickland
Alex Strickland

Reputation:

index or position in std::set

I have a std::set of std::string. I need the "index" or "position" of each string in the set, is this a meaningful concept in the context?

I guess find() will return an iterator to the string, so my question might be better phrased as : "How do I convert an iterator to a number?".

Upvotes: 11

Views: 23555

Answers (4)

Unmitigated
Unmitigated

Reputation: 89414

GCC provides a library of policy-based data structures which includes an order statistic tree implementation that behaves like a std::set that also allows finding the index of an element or the element at a specific index in logarithmic time.

Example usage:

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <functional>
template<typename K, typename V, typename C = std::less<>>
using ordered_map = __gnu_pbds::tree<K, V, C, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>;
template<typename T, typename C = std::less<>>
using ordered_set = ordered_map<T, __gnu_pbds::null_type, C>;

#include <iostream>
int main() {
    ordered_set<int> os;
    os.insert(7);
    os.insert(3);
    std::cout << os.order_of_key(7) << '\n'; // 7 is at index 1 in sorted order
    /* if the value doesn't exist in the set, order_of_key still counts 
       the number of elements less than the given argument */
    std::cout << *os.find_by_order(0) << '\n'; // element at index 0 is 3
}

Upvotes: 0

laura
laura

Reputation: 7332

std::distance is what you need. You will want, I guess std::distance(set.begin(), find_result)

Upvotes: 22

seh
seh

Reputation: 15269

Despite what others have written here, I don't think that "index" or "position" has meaning with respect to a set. In mathematical terms, a set exposes only its members and maybe its cardinality. The only meaningful operations involve testing whether an item is a member of the set, and combining or subtracting sets to yield new sets.

Some people talk about sets as data structures in looser terms, by facets of being "ordered" or "unordered", and whether they permit duplicates or enforce uniqueness. The former facet distinguishes an array with an O(n) insertion guard, where an attempt to insert an item first scans the existing members to see if the new item exists and, if not, inserts the new item at the end, and a hash table, that might retain such order only within a bucket's chain. A tree such as the Red-Black Tree used by std::set is somewhere in between; its traversal order is deterministic with respect to the strict weak order imposed by the comparator predicate, but, unlike the array sketched above, it doesn't retain insertion order.

The other facet — whether the set permits duplicate elements — is meaningless in mathematics, and is more accurately described as a bag. Such a structure acknowledges the difference between identity and value-based "sameness."

Your problem may involve caring about some position; it's not clear what that position means, but I expect you're going to need some data structure separate from std::set to model this properly. Perhaps a std::map mapping from your set of elements to each position would do. That would not guarantee that the positions are unique.

It may also help clarify the problem to think how you'd model it as relations, such as in a relational database. What comprises the key? What portions of the entities can vary independently?

Upvotes: 1

Gray-M
Gray-M

Reputation: 302

I don't think it is meaningful - set's are 'self keyed' and sorted thus the 'index' would be invalidated when the set is modified.

Of course it depends upon how you intend to use the index and if the set is essentially static (say a dictionary).

Upvotes: 1

Related Questions