Вопрос по std, dictionary, c++, insertion-order – Std :: map, которые отслеживают порядок вставки?

93

У меня сейчас естьstd::map<std::string,int> который хранит целочисленное значение в уникальном строковом идентификаторе, и я действительно ищу строку. Он делает в основном то, что я хочу, за исключением того, что он не отслеживает порядок вставки. Поэтому, когда я повторяю карту, чтобы распечатать значения, они сортируются в соответствии со строкой; но я хочу, чтобы они были отсортированы по порядку (первой) вставки.

Я думал об использованииvector<pair<string,int>> вместо этого, но мне нужно найти строку и увеличить целочисленные значения примерно в 100000000 раз, поэтому я не знаю,std::vector будет значительно медленнее.

Есть ли способ использоватьstd::map или есть другойstd контейнер, который лучше подходит для моих нужд?

[Я в GCC 3.4, и у меня, вероятно, не более 50 пар значений в моемstd::map].

Благодарю.

Что вы в конечном итоге использовали тогда? aggsol
Ну и часть времени быстрого поиска для std :: map связана с тем фактом, что он отсортирован по порядку, поэтому он может выполнять бинарный поиск. Просто не могу съесть свой торт и съесть его тоже! bobobobo

Ваш Ответ

14   ответов
1

что вы хотите (не прибегая к Boost), - это то, что я называю «упорядоченным хешем», который по сути представляет собой гибрид хеша и связанный список со строковыми или целочисленными ключами (или оба одновременно). Упорядоченный хэш поддерживает порядок элементов во время итерации с абсолютной производительностью хэша.

Я собирал относительно новую библиотеку фрагментов C ++, которая заполняет то, что я считаю дырами в языке C ++ для разработчиков библиотек C ++. Иди сюда:

https://github.com/cubiclesoft/cross-platform-cpp

Grab:

templates/detachable_ordered_hash.cpp
templates/detachable_ordered_hash.h
templates/detachable_ordered_hash_util.h

Если контролируемые пользователем данные будут помещены в хеш, вы также можете захотеть:

security/security_csprng.cpp
security/security_csprng.h

Вызвать это:

#include "templates/detachable_ordered_hash.h"
...
// The 47 is the nearest prime to a power of two
// that is close to your data size.
//
// If your brain hurts, just use the lookup table
// in 'detachable_ordered_hash.cpp'.
//
// If you don't care about some minimal memory thrashing,
// just use a value of 3.  It'll auto-resize itself.
int y;
CubicleSoft::OrderedHash<int> TempHash(47);
// If you need a secure hash (many hashes are vulnerable
// to DoS attacks), pass in two randomly selected 64-bit
// integer keys.  Construct with CSPRNG.
// CubicleSoft::OrderedHash<int> TempHash(47, Key1, Key2);
CubicleSoft::OrderedHashNode<int> *Node;
...
// Push() for string keys takes a pointer to the string,
// its length, and the value to store.  The new node is
// pushed onto the end of the linked list and wherever it
// goes in the hash.
y = 80;
TempHash.Push("key1", 5, y++);
TempHash.Push("key22", 6, y++);
TempHash.Push("key3", 5, y++);
// Adding an integer key into the same hash just for kicks.
TempHash.Push(12345, y++);
...
// Finding a node and modifying its value.
Node = TempHash.Find("key1", 5);
Node->Value = y++;
...
Node = TempHash.FirstList();
while (Node != NULL)
{
  if (Node->GetStrKey())  printf("%s => %d\n", Node->GetStrKey(), Node->Value);
  else  printf("%d => %d\n", (int)Node->GetIntKey(), Node->Value);

  Node = Node->NextList();
}

Я натолкнулся на этот поток SO во время своей исследовательской фазы, чтобы посмотреть, существует ли что-то вроде OrderedHash, не требуя, чтобы я бросил огромную библиотеку. Я был разочарован. Поэтому я написал свой. И теперь я поделился этим.

10

Держи параллельlist<string> insertionOrder.

Когда пришло время для печати, итерации наlist и искать вmap.

each element in insertionOrder  // walks in insertionOrder..
    print map[ element ].second // but lookup is in map
6

которая является лицензией MIT. Вы можете найти это здесь:упорядоченная карта

Пример карты

#include <iostream>
#include <string>
#include <cstdlib>
#include "ordered_map.h"

int main() {
tsl::ordered_map<char, int> map = {{'d', 1}, {'a', 2}, {'g', 3}};
map.insert({'b', 4});
map['h'] = 5;
map['e'] = 6;

map.erase('a');


// {d, 1} {g, 3} {b, 4} {h, 5} {e, 6}
for(const auto& key_value : map) {
    std::cout << "{" << key_value.first << ", " << key_value.second << "}" << std::endl;
}


map.unordered_erase('b');

// Break order: {d, 1} {g, 3} {e, 6} {h, 5}
for(const auto& key_value : map) {
    std::cout << "{" << key_value.first << ", " << key_value.second << "}" << std::endl;
}
}
,
18

Вы могли бы объединитьstd::vector сstd::tr1::unordered_map (хеш-таблица). Здесь ссылка наПовысить документацию заunordered_map, Вы можете использовать вектор для отслеживания порядка вставки и хэш-таблицы для частых поисков. Если вы выполняете сотни тысяч поисков, разница между поиском O (log n) дляstd::map и O (1) для хеш-таблицы может быть значительным.

std::vector<std::string> insertOrder;
std::tr1::unordered_map<std::string, long> myTable;

// Initialize the hash table and record insert order.
myTable["foo"] = 0;
insertOrder.push_back("foo");
myTable["bar"] = 0;
insertOrder.push_back("bar");
myTable["baz"] = 0;
insertOrder.push_back("baz");

/* Increment things in myTable 100000 times */

// Print the final results.
for (int i = 0; i < insertOrder.size(); ++i)
{
    const std::string &s = insertOrder[i];
    std::cout << s << ' ' << myTable[s] << '\n';
}
Это лучший способ сделать это. Очень дешевая память (всего 50 строк!), Позволяетstd::map работать так, как он должен (т.е. сортировать себя при вставке), и имеет быстрое время выполнения. (Я прочитал это после написания моей версии, где я использовал std :: list!)
@xtofl, как это делает мой ответ бесполезным и, следовательно, достойным понижения? Мой код неверен каким-то образом?
но, конечно, вы не можете получить доступ к счетчикам по порядку вставки ...
4

вы получите два контейнера. Вы можете использоватьvector с вашими фактическими значениями (ints) и положитьmap< string, vector< T >::difference_type>  рядом с ним, возвращая индекс в вектор.

Чтобы завершить все это, вы можете заключить оба в один класс.

Но я верюBoost имеет контейнер с несколькими индексами.

52

: map, вы можете скопировать их в std :: vector перед распечаткой и отсортировать через std :: sort, используя соответствующий функтор.

Или вы могли бы использоватьповышение :: multi_index, Это позволяет использовать несколько индексов. В вашем случае это может выглядеть следующим образом:

struct value_t {
      string s;
      int    i;
};
struct string_tag {};
typedef multi_index_container<
    value_t,
    indexed_by<
        random_access<>, // this index represents insertion order
        hashed_unique< tag<string_tag>, member<value_t, string, &value_t::s> >
    >
> values_t;
Спасибо за публикацию этого. Есть ли «усиление мультииндекса для манекенов»? книга? Я мог бы использовать это ...
@ Kristo: речь идет не о размере контейнера, а о повторном использовании существующей реализации именно для этой проблемы. Это классно. Следует признать, что C ++ не является функциональным языком, поэтому синтаксис несколько сложен.
С каких это пор программировалось сохранение клавиш?
Да, multi_index - моя любимая функция в boost :)
Замечательно! У Boost даже есть член-селектор, чтобы сделать работу!
1

// Должно быть, как этот человек!

// Это поддерживает сложность вставки O (logN) и удаление также O (logN).

class SpecialMap {
private:
  int counter_;
  map<int, string> insertion_order_;
  map<string, int> insertion_order_reverse_look_up; // <- for fast delete
  map<string, Data> data_;
};
0

которую вы должны учитывать, это небольшое количество элементов данных, которые вы используете. Возможно, быстрее будет использовать только вектор. На карте есть некоторые издержки, которые могут сделать поиск в небольших наборах данных более дорогим, чем простой вектор. Итак, если вы знаете, что вы всегда будете использовать примерно одинаковое количество элементов, проведите некоторый сравнительный анализ и посмотрите, действительно ли вы считаете, что производительность карты и вектора. Вы можете найти поиск в векторе, в котором только 50 элементов примерно такие же, как на карте.

-1

int) и статического int, которая увеличивается при вызовах вставки, индексирует пары данных. Поместите в структуру, которая может возвращать статический int val с членом index (), возможно?

Вы должны добавить пример.
1

Это в некоторой степени связано с ответом Faisals. Вы можете просто создать класс-оболочку вокруг карты и вектора и легко синхронизировать их. Правильная инкапсуляция позволит вам контролировать метод доступа и, следовательно, какой контейнер использовать ... вектор или карту. Это позволяет избежать использования Boost или чего-либо подобного.

0

boost::multi_index с картой и списком индексов.

1

для которого требуется только стандартная библиотека шаблонов без использования мультииндекса boost:
Вы могли бы использоватьstd::map<std::string,int>; а такжеvector <data>; где на карте вы храните индекс местоположения данных в векторе, а вектор хранит данные в порядке вставки. Здесь доступ к данным имеет O (log n) сложность. отображение данных в порядке вставки имеет сложность O (n). вставка данных имеет сложность O (log n).

Например:

#include<iostream>
#include<map>
#include<vector>

struct data{
int value;
std::string s;
}

typedef std::map<std::string,int> MapIndex;//this map stores the index of data stored 
                                           //in VectorData mapped to a string              
typedef std::vector<data> VectorData;//stores the data in insertion order

void display_data_according_insertion_order(VectorData vectorData){
    for(std::vector<data>::iterator it=vectorData.begin();it!=vectorData.end();it++){
        std::cout<<it->value<<it->s<<std::endl;
    }
}
int lookup_string(std::string s,MapIndex mapIndex){
    std::MapIndex::iterator pt=mapIndex.find(s)
    if (pt!=mapIndex.end())return it->second;
    else return -1;//it signifies that key does not exist in map
}
int insert_value(data d,mapIndex,vectorData){
    if(mapIndex.find(d.s)==mapIndex.end()){
        mapIndex.insert(std::make_pair(d.s,vectorData.size()));//as the data is to be
                                                               //inserted at back 
                                                               //therefore index is
                                                               //size of vector before
                                                               //insertion
        vectorData.push_back(d);
        return 1;
    }
    else return 0;//it signifies that insertion of data is failed due to the presence
                  //string in the map and map stores unique keys
}
1

map вместоvector, Я покажу вам этот подход и обсудить различия:

Просто создайте класс, у которого есть две карты за сценой.

#include <map>
#include <string>

using namespace std;

class SpecialMap {
  // usual stuff...

 private:
  int counter_;
  map<int, string> insertion_order_;
  map<string, int> data_;
};

Затем вы можете выставить итератор на итераторdata_ в правильном порядке. То, как вы это делаете, это итерация поinsertion_order_и для каждого элемента, который вы получите из этой итерации, выполните поиск вdata_ со значением отinsertion_order_

Вы можете использовать более эффективныйhash_map для inserttion_order, поскольку вы не заботитесь о прямой итерацииinsertion_order_.

Чтобы сделать вставки, у вас может быть такой метод:

void SpecialMap::Insert(const string& key, int value) {
  // This may be an over simplification... You ought to check
  // if you are overwriting a value in data_ so that you can update
  // insertion_order_ accordingly
  insertion_order_[counter_++] = key;
  data_[key] = value;
}

Есть много способов улучшить дизайн и беспокоиться о производительности, но это хороший каркас, с которого вы можете начать реализовывать эту функцию самостоятельно. Вы можете сделать его шаблонным, и вы можете хранить пары как значения в data_, чтобы вы могли легко ссылаться на запись в inserttion_order_. Но я оставляю эти вопросы дизайна в качестве упражнения :-).

Update: Я полагаю, что я должен сказать кое-что об эффективности использования карты против вектора для inserttion_order_

lookups directly into data, in both cases are O(1) inserts in the vector approach are O(1), inserts in the map approach are O(logn) deletes in the vector approach are O(n) because you have to scan for the item to remove. With the map approach they are O(logn).

Может быть, если вы не собираетесь использовать удаления, вы должны использовать векторный подход. Подход карты был бы лучше, если бы вы поддерживали другой порядок (например, приоритет) вместо порядка вставки.

Картографический подход также лучше, если вам нужно получить элементы по «идентификатору вставки». Например, если вы хотите, чтобы элемент, который был вставлен пятым, вы выполняете поиск в inserttion_order с ключом 5 (или 4, в зависимости от того, где вы начинаете counter_). При векторном подходе, если 5-й элемент был удален, вы фактически получили бы 6-й элемент, который был вставлен.
1

но вы можете использовать две отдельные структуры - карту и вектор и сохранять их синхронизированными - то есть когда вы удаляете с карты, находите и удаляете элемент из вектора. Или вы могли бы создатьmap<string, pair<int,int>> - и в вашей паре сохраните размер () карты после вставки в положение для записи вместе со значением типа int, а затем при печати используйте элемент position для сортировки.

Похожие вопросы