Std::map, которые отслеживают порядок вставки?
У меня сейчас есть std::map<std::string,int> это хранит целочисленное значение в уникальный строковый идентификатор, и я ищу строку. Он делает в основном то, что я хочу, за исключением того, что он не отслеживает порядок вставки. Поэтому, когда я повторяю карту, чтобы распечатать значения, они сортируются в соответствии со строкой; но я хочу, чтобы они были отсортированы по порядку (первой) вставки.
Я думал об использовании vector<pair<string,int>> вместо этого, но мне нужно посмотреть строку и увеличить целочисленные значения примерно в 10 000 000 раз, поэтому я не знаю, std::vector будет значительно медленнее.
Есть ли способ использовать std::map или есть другой std контейнер, который лучше подходит для моих нужд?
[Я нахожусь на GCC 3.4, и у меня, вероятно, не более 50 пар значений в моем std::map].
Благодарю.
15 ответов
Если у вас есть только 50 значений в std::map, вы можете скопировать их в std:: vector перед печатью и отсортировать с помощью std:: sort, используя соответствующий функтор.
Или вы можете использовать boost:: 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;
Вы могли бы объединить std::vector с std::tr1::unordered_map (хеш-таблица). Вот ссылка на документацию Boost для 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';
}
У Tessil очень хорошая реализация упорядоченной карты (и набора), которая является лицензией 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;
}
}
Держи параллель list<string> insertionOrder,
Когда пришло время для печати, итерации по списку и поискать карту.
each element in insertionOrder // walks in insertionOrder..
print map[ element ].second // but lookup is in map
Если вам нужны обе стратегии поиска, вы получите два контейнера. Вы можете использовать vector с вашими фактическими значениями (ints) и положить map< string, vector< T >::difference_type> рядом с ним, возвращая индекс в вектор.
Чтобы завершить все это, вы можете заключить оба в один класс.
Но я считаю, что у Boost есть контейнер с несколькими индексами.
Вот решение, которое требует только стандартную библиотеку шаблонов без использования мультииндекса 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
}
То, что вы хотите (не прибегая к 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, не требуя, чтобы я зашел в огромную библиотеку. Я был разочарован. Поэтому я написал свой. И теперь я поделился этим.
Вы не можете сделать это с картой, но вы можете использовать две отдельные структуры - карту и вектор и сохранять их синхронизированными - то есть когда вы удаляете с карты, находите и удаляете элемент из вектора. Или вы могли бы создать map<string, pair<int,int>> - и в вашей паре сохраните размер () карты после вставки в положение для записи вместе со значением int, а затем при печати используйте элемент позиции для сортировки.
Еще один способ реализовать это с 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_. Но я оставляю эти вопросы дизайна в качестве упражнения:-).
Обновление: я полагаю, что я должен сказать что-то об эффективности использования карты против вектора для inserttion_order_
- поиск непосредственно в данных, в обоих случаях O(1)
- вставки в векторном подходе O(1), вставки в картографическом подходе O(logn)
- удаляет в векторном подходе O(n), потому что вы должны сканировать предмет для удаления. При подходе к карте они O(logn).
Может быть, если вы не собираетесь использовать удаления, вы должны использовать векторный подход. Подход к карте был бы лучше, если бы вы поддерживали другой порядок (например, приоритет) вместо порядка вставки.
Одна вещь, которую вы должны учитывать, это небольшое количество элементов данных, которые вы используете. Вполне возможно, что быстрее будет использовать только вектор. На карте есть некоторые издержки, которые могут сделать поиск в небольших наборах данных более дорогим, чем простой вектор. Итак, если вы знаете, что вы всегда будете использовать примерно одинаковое количество элементов, проведите некоторый сравнительный анализ и убедитесь, что производительность карты и вектора соответствует вашим ожиданиям. Вы можете найти поиск в векторе, в котором только 50 элементов примерно такие же, как на карте.
Это в некоторой степени связано с ответом Faisals. Вы можете просто создать класс-оболочку вокруг карты и вектора и легко синхронизировать их. Правильная инкапсуляция позволит вам контролировать метод доступа и, следовательно, какой контейнер использовать... вектор или карту. Это позволяет избежать использования Boost или чего-либо подобного.
Нет необходимости использовать отдельный или какой-либо другой контейнер для отслеживания порядка размещения. Вы можете делать все, что хотите, как показано ниже. Если вы хотите сохранить порядок вставки, вы можете использовать следующую программу (версия 1):
Версия 1 : для подсчета уникальных строк с помощью
std::map<std::string,int>в порядке размещения
#include <iostream>
#include <map>
#include <sstream>
int findExactMatchIndex(const std::string &totalString, const std::string &toBeSearched)
{
std::istringstream ss(totalString);
std::string word;
std::size_t index = 0;
while(ss >> word)
{
if(word == toBeSearched)
{
return index;
}
++index;
}
return -1;//return -1 when the string to be searched is not inside the inputString
}
int main() {
std::string inputString = "this is a string containing my name again and again and again ", word;
//this map maps the std::string to their respective count
std::map<std::string, int> wordCount;
std::istringstream ss(inputString);
while(ss >> word)
{
//std::cout<<"word:"<<word<<std::endl;
wordCount[word]++;
}
std::cout<<"Total unique words are: "<<wordCount.size()<<std::endl;
std::size_t i = 0;
std::istringstream gothroughStream(inputString);
//just go through the inputString(stream) instead of map
while( gothroughStream >> word)
{
int index = findExactMatchIndex(inputString, word);
if(index != -1 && (index == i)){
std::cout << word <<"-" << wordCount.at(word)<<std::endl;
}
++i;
}
return 0;
}
Результат вышеупомянутой программы выглядит следующим образом:
Total unique words are: 9
this-1
is-1
a-1
string-1
containing-1
my-1
name-1
again-3
and-2
Обратите внимание, что в приведенной выше программе, если у вас есть запятая или любой другой разделитель, он считается отдельным словом. Так, например, допустим, у вас есть строка
this is, my name is тогда строка имеет счетчик 1, а строка имеет счетчик 1. То есть
is, а также
isразные. Это потому, что компьютер не знает нашего определения слова .
Примечание
Вышеупомянутая программа является модификацией моего ответа на вопрос, как сделать char в выводе массива по порядку в этом вложенном цикле for?который представлен как версия 2 ниже:
Версия 2 : Для подсчета уникальных символов с помощью
std::map<char, int>в порядке размещения
#include <iostream>
#include <map>
int main() {
std::string inputString;
std::cout<<"Enter a string: ";
std::getline(std::cin,inputString);
//this map maps the char to their respective count
std::map<char, int> charCount;
for(char &c: inputString)
{
charCount[c]++;
}
std::size_t i = 0;
//just go through the inputString instead of map
for(char &c: inputString)
{
std::size_t index = inputString.find(c);
if(index != inputString.npos && (index == i)){
std::cout << c <<"-" << charCount.at(c)<<std::endl;
}
++i;
}
return 0;
}
В обоих случаях / версиях нет необходимости использовать отдельный
std::vector или любой другой контейнер для отслеживания порядка размещения.
// Должно быть, как этот человек!
// Это поддерживает сложность вставки 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_;
};
Использование boost::multi_index с картой и списком индексов.
Карта пары (str,int) и статического int, которая увеличивается при вызовах вставки, индексирует пары данных. Поместите в структуру, которая может возвращать статический int val с членом index (), возможно?